#import "@local/dtu-template:0.5.1":*
#import "@preview/cetz:0.4.2"
#import "@preview/cetz-venn:0.1.4": venn2, venn3
#import "@preview/auto-div:0.1.0": poly-div, poly-div-working

#let mark-circle = box(width: 0.8em, height: 0.8em, stroke: 0.5pt + black, radius: 50%)
#let ans(body) = grid(columns: (auto, 1fr), column-gutter: 0.5em, align: (center, left), mark-circle, body)

#let corr-circle = box(width: 0.8em, height: 0.8em, stroke: 0.5pt + black, fill: black, radius: 50%)
#let corr(body) = grid(columns: (auto, 1fr), column-gutter: 0.5em, align: (center, left), corr-circle, body)

#show heading: it => { pagebreak(weak: true); it }
== Question 1

If $p,q$ are prime numbers such that $100 < p < q$, then the number of positive integers less than $p q$ which are relative prime to $p q$ is:

#corr[$p q - p - q + 1$]
#ans[$p q - q + 1$]
#ans[$p q-p-q-1$]
#ans[$p q-p-q$]
#ans[$p q-1$]
#ans[None of these]

== Question 2

The number $(4^100 mod 6 )^100 mod 10$ equals

#ans[3]
#corr[6 (All's answer)]
#ans[2]
#ans[None of these]
#ans[5]
#ans[1]
#ans[4]

== Question 3

Consider the set of all 99 positive integers not exceeding 99.

#table(
  columns: (18%, auto, auto, auto, auto, auto, auto, auto, auto),
  align: (left, center, center, center, center, center, center, center, center),
  [],
  [$binom(99, 50)$],
  [$2^98$],
  [$2^97$],
  [$2^49$],
  [None of these],
  [$2^50$],
  [$binom(99,50) binom(99,49)$],
  [$binom(99,49) binom(99, 49)$],
  [How many subsets have an odd number of odd numbers, and an even number of even numbers?],
  mark-circle,
  mark-circle,
  corr-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  [How many subsets have an odd number of even numbers and an even number of odd numbers?],
  mark-circle,
  mark-circle,
  corr-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  [How many subsets have 49 elements?],
  corr-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  [How many subsets have an odd number of odd numbers?],
  mark-circle,
  corr-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
)

== Question 4

Consider the following system of congruences:

$
  x &equiv 1 mod 2 \
  x &equiv 1 mod 5 \
  x &equiv 7 mod 9
$

Indicate the set of all solutions to the above system of congruences.

#ans[None of these]
#ans[${90 + 7k | k in ZZ}$]
#ans[${1 + 2k | k in ZZ} union {1 + 5k | k in ZZ} union {7 + 9k | k in ZZ}$]
#ans[${9 + 90k | k in ZZ}$]
#corr[${61 + 90k | k in ZZ}$ (All's answer)]
#ans[${7 + 90k | k in ZZ}$]


== Question 5

Find a greatest common divisor of the polynomials $x^3 - 1$ and $x^3 + 2x^2 + 2x + 1$

#ans[$x+1$]
#ans[$1$(Mikkel's answer)]
#ans[$x-1$]
#corr[$x^2 + x + 1$]
#ans[$x^2 + x - 1$]
#ans[None of these]
#ans[$x^2 - x + 1$]
#ans[$x^2-x-1$]


== Question 6

Recall that $NN$ is the set of natural numbers, in other words the set of nonnegative integers. For all $n in NN$ define $f(n) = sum^n_(k=0) k dot k! = 0 dot 0! + 1 dot !+ dots + n dot n!$. It is possible to prove by induction that $f(n) = (n+1)! -1$ holds for all nonnegative integers $n$.

By choosing 4 of the following 8 text fragments and putting them in the correct order, a proof by induction for the above statement can be created.

A. To prove the induction step, we assume that $f(n+1) = ((n+1)+1)!-1$ holds for some $n in NN$. We will now prove that under this assumption, $f(n) = (n+1)!-1$

B. To prove the induction step we assume that $f(n) = (n+1)!-1$ holds for all $n in NN$. We will now prove that under this assumption, $f(n+1) = ((n+1)+1)!-1$ holds for all $n in NN$.

C. To prove the induction step we assume that $f(n) = (n+1)!-1$ holds for some $n in NN$. We will now prove that under this assumption, $f(n+1) = ((n+1)+1)!-1$.

D. The statement now follows from the principle of mathematical induction.

E. We prove the statement by induction. The base case is $n = 1$. For $n=1$, we see that $f(1) = sum^1_(k=0)k dot k! = 0 dot 0! + 1 dot 1! = 0 dot 1 + 1 dot 1 = 1$ and also that $(n+1)! -1 = (1+1)!-1 = 2!-1 = 2-1 =1$. This proves the base case.

F. We prove the statement by induction. The base case is $n=0$. For $n=0$, we see that $f(0) = sum^0_(k=0) k dot k! = 0 dot 0! = 0 dot 1 = 0$ and also that $(n+1)! -1 = (0+1)!-1 = 1!-1 = 1-1 =0$. This proves the base case.


G. We have that $
                  f(n) &= sum^n_(k=0) k dot k! \
                  &= (sum^(n+1)_(k=0) k dot k! ) - (n+1)(n+1)! \
                  &= f(n+1) - (n+1)(n+1)! \
                  &= ((n+1)+1)! - 1 - (n+1)(n+1)! "By the induction hypothesis" \
                  &= (n+2)! -(n+1)(n+1)!-1 \
                  &= (n+2)(n+1)!-(n+1)(n+1)!-1 \
                  &= (n+2 - (n+1))(n+1)!-1 \
                  &= (n+1)! -1
                 $ which is what we wanted to prove. This concludes the induction step.

H. We have that $
                  f(n+1) &= sum^(n+1)_(k=0) k dot k! \
                  &= (sum^n_(k=0) k dot k!) + (n+1)(n+1)! \
                  &= f(n)+(n+1)(n+1)! \
                  &= (n+1)!-1+(n+1)(n+1)! "By the induction hypothesis" \
                  &= (n+1)(n+1)!+(n+1)!-1 \
                  &= [(n+1)+1](n+1)!-1 \
                  &= (n+2)! - 1 = ((n+1)+1)!-1
                $ which is what we wanted to prove. This concludes the induction step.

#table(
  columns: (35%, 1fr, 1fr,1fr,1fr,1fr,1fr,1fr,1fr),
  align: (left, center, center, center, center, center, center, center, center),
  [],
  [A],
  [B],
  [C],
  [D],
  [E],
  [F],
  [G],
  [H],
  [The first fragment is:],
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  corr-circle,
  mark-circle,
  mark-circle,
  [The second fragment is:],
  mark-circle,
  mark-circle,
  corr-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  [The third fragment is:],
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  corr-circle,
  [The fourth fragment is:],
  mark-circle,
  mark-circle,
  mark-circle,
  corr-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
)

== Question 7

For all $n in NN$ define $a_n$ recursively as follows $a_0 = 2, a_1 = 3, a_n = cases(a_(n-1) + n "if" n "is even", a_(n-1) + 2a_(n-2) "if" n "is odd")$

#corr[37 (All's answer)]
#ans[38]
#ans[35]
#ans[40]
#ans[None of these]
#ans[36]
#ans[39]

== Question 8

We wish to construct a bipartite graph with bipartition $(V_1, V_2)$ such that $abs(V_1) = 4, abs(V_2) = 5$ (Note that a bipartite graph has no loops, but it may contain multiple edges.)
#table(
  columns: (40%, 1fr, 1fr, 1fr, 1fr, 1fr),
  align: (left, center, center, center, center, center),
  [],
  [The graph exists without multiple edges.],
  [The graph exists but only if we allow multiple edges.],
  [The graph does not exist, but it will exist if we are allowed to increase one of the degrees in $V_1$.],
  [The graph does not exist, but it will exist if we are allowed to increase one of the degrees in $V_2$.],
  [None of these are correct],
  [If the degrees in $V_1$ are $5,5,5,5$ and the degrees in $V_2$ are $4,4,4,4,4$ then],
  corr-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  [If the degrees in $V_1$ are $1,2,2,2$ and the degrees in $V_2$ are $1,2,2,2,2$ then],
  mark-circle,
  mark-circle,
  corr-circle,
  mark-circle,
  mark-circle,
  [If the degrees in $V_1$ are $4,4,4,4$, and the degrees in $V_2$ are $5,5,5,5,5$ then],
  mark-circle,
  mark-circle,
  mark-circle,
  corr-circle,
  mark-circle,
)


== Question 9

The formula $binom(m+n, r) = sum^r_(k=a) binom(m, r-k) binom(n,k)$ is true for all integers $m,n,r$ satisfying $0 < m < r < n$ if we let the summation start with:

#ans[$a = n$]
#ans[$a = r$]
#ans[None of these]
#ans[$a = n -r$]
#ans[$a = m$]
#corr[$a = r - m$]


== Question 10

Let $A = {0,1,2,4}, B = {0,1,3,5}, "and" C = {0,2,3,6}$. IF the universal set $U = {0,1,2,3,4,5,6,7}$, then which of the following is equal to $((A inter B) backslash C) union ((B inter C) backslash A) union ((C inter A) backslash B)$

#ans[${0,1,2,3}$]
#ans[All of these sets]
#ans[$emptyset$]
#ans[${4,5,6}$]
#ans[None of these ]
#ans[${0,4,5,6}$]
#corr[${1,2,3}$]

== Question 11

Consider the statement "for every positive rational number $x$ there are positive integers $a$ and $b$ such that $x = a/b$ and $gcd(a,b) = 1$." Which of the following statement in predicate logic is equivalent to this if we let $G(a,b)$ denote the statement " $a "and" b$ are relatively prime"?

#ans[It is not possible to translate the statement into predicate logic.]
#corr[$forall x in QQ^+ exists a in ZZ^+ exists b in ZZ^+ (x = a/b and G(a,b)) $]
#ans[$forall x in QQ^+ exists a in ZZ^+ exists b in ZZ^+ (G(a,b) -> x = a/b)$]
#ans[$forall x in QQ^+ forall a in ZZ^+ forall b in ZZ^+ (x = a/b and G(a,b))$]
#ans[$forall x in QQ^+ exists a in ZZ^+ exists b in ZZ^+ (x = a/b -> G(a,b))$]

== Question 12

Given a univerisal set $U$, which of the following is equal to the set $A inter overline((B backslash C))$?

#ans[None of these]
#ans[$A inter B inter overline(C)$]
#ans[$(A union B) inter (A union overline(C))$]
#corr[$(A inter overline(B)) union (A inter C)$]
#ans[$A inter overline(B) inter C$]
#ans[$A inter (C backslash B)$]


== Question 13

The empty set is an element of which of the following sets?

#ans[${{emptyset}}$]
#ans[None of these]
#ans[$emptyset$]
#ans[${x in RR : x < x}$]
#corr[${emptyset}$]
#ans[All of these sets]

== Question 14

Which of the following are tautologies?

#ans[$(p -> q) or (not q -> not p)$]
#ans[None of these]
#ans[$p <-> q$]
#ans[All of these]
#corr[$(not p or not q) -> (not (p and q))$]
#ans[$(p or q or r) and (p or not q or not r)$]

== Question 15

Consider all possible seatings of $3n$ people around two tables, one with $n$ seats and one with $2n$ seats. Find the number of seatings when
#table(
  columns: (20%, 1fr, 1fr, 1fr, 1fr, 1fr, 1fr, 1fr, 1fr, 1fr),
  align: (left, center, center, center, center, center, center, center, center, center),
  [],
  [$((3n)!)/(2(n!))$],
  [$((3n)!)/(4(n!))$],
  [$((3n)!)/(4n)$],
  [$2 binom(3n,n)$],
  [$((3n)!)/(2n^2)$],
  [$((3n)!)/(4n^2)$],
  [$((3n)!)/(8n^2)$],
  [$4 binom(3n,n)$],
  [None of these],
  [Two seatings are considered the same when each person has the same left and right neighbor.],
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  corr-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  [Two seatings are considered the same when each person has the same neighbors (and we do not care about right or left)],
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  corr-circle,
  mark-circle,
  mark-circle,
)

== Question 16

For each of the following, determine whether it is surjective/injective, or not a well defined function. Recall that $NN$ is the set of natural numbers, in other words the set of nonnegative integers.

#table(
  columns: (35%, 1fr, 1fr, 1fr, 1fr, 1fr),
  align: (left, center, center, center, center, center),
  [],
  [Not a well defined function],
  [Well defined but neither injective nor surjective],
  [Surjective but not injective],
  [Injective but not surjective],
  [Both injective and surjective],
  [$ f: RR -> ZZ $ given by $f(x) = 2 floor(x/2)$],
  mark-circle,
  corr-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  [$f : RR -> {x  in RR : x >= 0}$ given by $f(x) = sqrt(x^2)$],
  mark-circle,
  mark-circle,
  corr-circle,
  mark-circle,
  mark-circle,
  [$f: NN -> NN$ given by $f(x) = 2x +7$],
  mark-circle,
  mark-circle,
  mark-circle,
  corr-circle,
  mark-circle,
  [$f: NN -> NN$ given by $f(x) = x-x^2$],
  corr-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  [$f: RR -> RR$ given by $f(x) = cases(x "if" x in QQ, -x "if" x in.not QQ)$],
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  corr-circle,
)

== Question 17

Consider all permutations of ABCDE
#table(
  columns: (20%, 1fr, 1fr, 1fr, 1fr, 1fr, 1fr, 1fr),
  align: (left, center, center, center, center, center, center, center),
  [],
  [12],
  [24],
  [36],
  [48],
  [50],
  [64],
  [None of these],
  [How many contain none of AB, BC, CD],
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  corr-circle,
  mark-circle,
  [How many contain ACE],
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  corr-circle,
  [How many contain precisely one of AB, CD],
  mark-circle,
  mark-circle,
  corr-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle
)

== Question 18

For each relation on the set of four distinct elements $a,b,c,d$ below, decide which property it has.

#table(
  columns: (30%, 1fr, 1fr, 1fr, 1fr, 1fr, 1fr, 1fr),
  align: (left, center, center, center, center, center, center, center),
  [],
  [The edges of a hasse diagram],
  [Partial order],
  [Total order but not well ordered],
  [Well-order],
  [None of these],
  [Total order but not partial order],
  [Equivalence relation],
  [$(a,a),(a,b),(a,c)(a,d)$],
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  corr-circle,
  mark-circle,
  mark-circle,
  [$(a,b),(b,c),(c,d)$],
  corr-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  [$(a,a),(b,b),(c,c),\ (d,d),(a,d),(d,a)$],
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  corr-circle,
  [$(a,a),(b,b),(c,c),\ (d,d),(d,c)$],
  mark-circle,
  corr-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  [$(a,a),(b,b),(c,c),(d,d),\ (a,b),(a,c),(a,d),(b,c),\ (b,d),(c,d)$],
  mark-circle,
  mark-circle,
  corr-circle,
  corr-circle,
  mark-circle,
  mark-circle,
  mark-circle
)
Note: AI'er var uenige om den sidste, så har markeret de to svar jeg fik.


== Question 19

Which of the following is a recursively defined function for the number of ways to tile an $n times 2$ board using $2 times 1$ tiles.

#corr[$f(0) = 1, f(1) = 1, f(n) = f(n - 1) + f(n - 2) "for" n >= 2$]
#ans[$f(0) = 0, f(1) = 1, f(n) = 2f(n - 2) "for" n >= 2$]
#ans[$f(0) = 1, f(1) = 1, f(n) = 2f(n - 2) "for" n >= 2$]
#ans[$f(0) = 1, f(1) = 1, f(n) = f(n - 1)f(n - 2) "for" n >= 2$]
#ans[All of these]
#ans[$f(0) = 0, f(1) = 1, f(n) = f(n - 1) + f(n - 2) "for" n >= 2$]
#ans[None of these ]


== Question 20

Find the coefficient of $x^15 y^20$ in the polynomials below.

#table(
  columns: (20%, 1fr, 1fr, 1fr, 1fr, 1fr, 1fr, 1fr),
  align: (left, center, center, center, center, center, center, center),
  [],
  [$- binom(10,5)2^5$],
  [$binom(10,5) 2^15$],
  [$- binom(10,5)2^15$],
  [0],
  [None of these],
  [$-binom(10,5)2^10$],
  [$- binom(10,3)2^5$],
  [$(2x^3-y^4)^10$],
  corr-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  [$(1-2x^3y^4)^10$],
  corr-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  [$(x^3-2y^4)^10$],
  corr-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
  mark-circle,
)


== Question 21

Which of the following is equivalent to the statement " $a$ and $b$ are relatively prime"? The domain for each statement is
the set of all positive integers

#ans[None of these three are equivalent to the statement.]
#ans[$not (exists c (c divides a and c divides b and c > 1) )$ is equivalent to the statement, and the other two are not.]
#ans[$forall c (not (c divides a) or not (c divides b) or (c <= 1))$ is equivalent to the statement, and the other two are not.]
#corr[All of these three are equivalent to the statement.]
#ans[$forall c ( (c divides a and c divides b) -> (c <= 1))$ is equivalent to the statement, and other two are not.]