# Sample Exam Solutions Spring 2026 # Discrete Mathematics — Lecture Exam Sample (Spring 2026) — Worked Solutions All notation matches the lecture slides. Answers chosen to be the simplest correct ones for the exam. --- ## Part 1 — Short questions (18 marks) ### 1. Two properties of inclusive or (∨) — (1 mark) Any two of the following (definition excluded): - **Commutativity:** $p \lor q \Leftrightarrow q \lor p$ - **Associativity:** $p \lor (q \lor r) \Leftrightarrow (p \lor q) \lor r$ - **Idempotence:** $p \lor p \Leftrightarrow p$ - **De Morgan:** $\lnot(p \lor q) \Leftrightarrow \lnot p \land \lnot q$ - **Distributivity:** $p \lor (q \land r) \Leftrightarrow (p \lor q) \land (p \lor r)$ --- ### 2. Cartesian product — (2 marks) **(a)** The Cartesian product of two sets $A$ and $B$ is the set of all ordered pairs whose first component is from $A$ and whose second component is from $B$: $$A \times B = \{(a,b) \mid a \in A \land b \in B\}.$$ **(b)** For $A = \{1,2,3\}$, $B = \{a,b,c\}$: $$A \times B = \{(1,a),(1,b),(1,c),(2,a),(2,b),(2,c),(3,a),(3,b),(3,c)\}.$$ --- ### 3. Composition of two binary relations — (1 mark) Let $R$ and $S$ be binary relations. Their composition $S \circ R$ is the relation defined by $$(x,z) \in S \circ R \iff \exists y:\ (x,y) \in R \ \land\ (y,z) \in S.$$ (That is, $R$ is applied first, then $S$.) --- ### 4. Transitivity — (2 marks) **(a)** A binary relation $R \subseteq X \times X$ is **transitive** if for all $x,y,z \in X$: $$\big((x,y) \in R \ \land\ (y,z) \in R\big) \Rightarrow (x,z) \in R.$$ **(b)** Example on $A = \{a,b,c,d,e\}$: the empty relation $R = \varnothing$ is transitive; or, for a non-trivial one, $$R = \{(a,b),(b,c),(a,c)\}.$$ Check: the only "chained" pair is $(a,b),(b,c)$, and indeed $(a,c) \in R$. (The identity relation $\{(a,a),(b,b),(c,c),(d,d),(e,e)\}$ also works.) --- ### 5. Equivalence relation — (2 marks) **(a)** A binary relation $\sim$ on a set is an **equivalence relation** if it is **reflexive, symmetric and transitive**. **(b)** Example: $X = \mathbb{Z}$ and $a \sim b \iff a - b$ is even (i.e. congruence mod 2). This is reflexive, symmetric and transitive. (Simpler finite example: $X = \{1,2,3\}$ with $\sim$ = equality, $\sim = \{(1,1),(2,2),(3,3)\}$.) --- ### 6. Surjective function — (2 marks) **(a)** A function $f: X \to Y$ is **surjective (onto)** if every element of $Y$ is the image of at least one element of $X$: $$\forall y \in Y\ \exists x \in X:\ f(x) = y.$$ **(b)** Example $f: \{a,b,c,d\} \to \{1,2,3\}$ hitting all of $\{1,2,3\}$: $$f(a)=1,\quad f(b)=2,\quad f(c)=3,\quad f(d)=3.$$ --- ### 7. Complex numbers — (2 marks) **(a)** Any four (definitions excluded), e.g.: - $\overline{\overline{z}} = z$ - $\overline{z+w} = \overline{z} + \overline{w}$ - $\overline{z \cdot w} = \overline{z}\cdot\overline{w}$ - $z \cdot \overline{z} = |z|^2$ - $|\overline{z}| = |z|$ - $|z \cdot w| = |z|\cdot|w|$ - $z + \overline z = 2\,\mathrm{Re}(z)$ **(b)** For $z = -3 - 2i$: $$|z| = \sqrt{(-3)^2 + (-2)^2} = \sqrt{9+4} = \sqrt{13}, \qquad \overline{z} = -3 + 2i.$$ --- ### 8. Permutations with repetition (statement) — (1 mark) The number of permutations with repetition of $m$ different kinds of objects, with repetition numbers $k_1, k_2, \ldots, k_m$ (i.e. $k_i$ copies of the $i$-th kind), is $$\frac{n!}{k_1!\, k_2! \cdots k_m!}, \qquad \text{where } n = k_1 + k_2 + \cdots + k_m \text{ is the total number of objects.}$$ --- ### 9. Binomial theorem — (2 marks) **(a)** For any real numbers $x, y$ and any $n \in \mathbb{N}$: $$(x+y)^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{\,n-k},$$ where $\binom{n}{k}$ is the binomial coefficient "$n$ choose $k$". **(b)** $$(x+y)^6 = \binom{6}{0}y^6 + \binom{6}{1}x y^5 + \binom{6}{2}x^2 y^4 + \binom{6}{3}x^3 y^3 + \binom{6}{4}x^4 y^2 + \binom{6}{5}x^5 y + \binom{6}{6}x^6$$ $$= y^6 + 6x y^5 + 15 x^2 y^4 + 20 x^3 y^3 + 15 x^4 y^2 + 6 x^5 y + x^6.$$ --- ### 10. Two properties of binomial coefficients — (1 mark) Any two of: - **Symmetry:** $\dbinom{n}{k} = \dbinom{n}{n-k}$ - **Pascal's identity:** $\dbinom{n+1}{k+1} = \dbinom{n}{k} + \dbinom{n}{k+1}$ - $\displaystyle\sum_{k=0}^{n}\binom{n}{k} = 2^n$ --- ### 11. Pigeonhole principle — (1 mark) If $n+1$ items are put into $n$ containers, then there is at least one container that contains at least two items. --- ### 12. Definition of an undirected graph — (1 mark) A triple $G = (\varphi, E, V)$ is an **(undirected) graph** if $E$ and $V$ are sets with $V \neq \varnothing$, $V \cap E = \varnothing$, and $$\varphi: E \to \big\{\{v,v'\} \mid v, v' \in V\big\}.$$ Here $V$ is the set of **vertices**, $E$ the set of **edges**, and $\varphi$ the **incidence function**, which assigns to each edge an unordered pair of vertices. --- ## Part 2 — Proof questions (16 marks) *Scoring: statement 1 mark, proof 3 marks. For two/three statements the marks split evenly.* ### P1. Three properties of set union, with proofs — (4 marks) I prove **idempotence**, **associativity** and **the empty-set property**. Each set proof reduces the statement to the corresponding logical law via the definition of $\cup$. **(i) Idempotence:** $A \cup A = A$. $$x \in A \cup A \overset{(1)}{\Leftrightarrow} (x \in A \lor x \in A) \overset{(2)}{\Leftrightarrow} x \in A.$$ (1) definition of $\cup$; (2) idempotence of $\lor$. **(ii) Associativity:** $A \cup (B \cup C) = (A \cup B) \cup C$. $$ \begin{aligned} x \in A \cup (B \cup C) &\overset{(1)}{\Leftrightarrow} x \in A \lor x \in (B \cup C) \overset{(1)}{\Leftrightarrow} x \in A \lor (x \in B \lor x \in C)\\ &\overset{(2)}{\Leftrightarrow} (x \in A \lor x \in B) \lor x \in C \overset{(1)}{\Leftrightarrow} x \in (A \cup B) \lor x \in C\\ &\overset{(1)}{\Leftrightarrow} x \in (A \cup B) \cup C. \end{aligned} $$ (1) definition of $\cup$; (2) associativity of $\lor$. **(iii) Empty set:** $A \cup \varnothing = A$. $$x \in A \cup \varnothing \overset{(1)}{\Leftrightarrow} (x \in A \lor x \in \varnothing) \overset{(2)}{\Leftrightarrow} (x \in A \lor F) \overset{(3)}{\Leftrightarrow} x \in A.$$ (1) definition of $\cup$; (2) definition of $\varnothing$ (no element lies in $\varnothing$, so $x \in \varnothing$ is false $F$); (3) property of $\lor$ ($p \lor F \Leftrightarrow p$). *(Commutativity $A \cup B = B \cup A$ via commutativity of $\lor$ is an equally valid third choice.)* --- ### P2. Associativity of the composition of binary relations — (4 marks) **Statement.** Let $R, S, T$ be binary relations. Then composition is associative: $$T \circ (S \circ R) = (T \circ S) \circ R,$$ where for relations $P, Q$ the composition is $(x,z) \in Q \circ P \iff \exists y:\ (x,y)\in P \land (y,z)\in Q$. **Proof.** We show that an ordered pair belongs to the left-hand side exactly when it belongs to the right-hand side. $$ \begin{aligned} (x,w) \in T \circ (S \circ R) &\overset{(1)}{\Leftrightarrow} \exists v:\ (x,v) \in S\circ R \ \land\ (v,w) \in T\\ &\overset{(1)}{\Leftrightarrow} \exists v:\ \big(\exists u:\ (x,u)\in R \land (u,v)\in S\big) \land (v,w)\in T\\ &\overset{(2)}{\Leftrightarrow} \exists u\,\exists v:\ (x,u)\in R \ \land\ (u,v)\in S \ \land\ (v,w)\in T\\ &\overset{(2)}{\Leftrightarrow} \exists u:\ (x,u)\in R \ \land\ \big(\exists v:\ (u,v)\in S \land (v,w)\in T\big)\\ &\overset{(1)}{\Leftrightarrow} \exists u:\ (x,u)\in R \ \land\ (u,w) \in T\circ S\\ &\overset{(1)}{\Leftrightarrow} (x,w) \in (T\circ S)\circ R. \end{aligned} $$ (1) definition of composition; (2) reordering and regrouping the existential quantifiers and conjunctions (the order of the independent "intermediate" elements $u,v$ does not matter, and $\land$ is associative/commutative). Since the two relations contain exactly the same pairs, $T \circ (S \circ R) = (T \circ S) \circ R$. $\blacksquare$ --- ### P3. Formula for the $n^{\text{th}}$ roots of a complex number — (4 marks) **Statement.** Let $z = |z|(\cos\varphi + i\sin\varphi)$ be a complex number given in polar form and $n \in \mathbb{N}^+$. The $n^{\text{th}}$ roots of $z$ (the numbers $w$ with $w^n = z$) are exactly $$w_k = \sqrt[n]{|z|}\left(\cos\!\Big(\tfrac{\varphi}{n} + \tfrac{2k\pi}{n}\Big) + i\sin\!\Big(\tfrac{\varphi}{n} + \tfrac{2k\pi}{n}\Big)\right), \qquad k = 0,1,\ldots,n-1.$$ **Proof.** Write a candidate root in polar form as $w = |w|(\cos\psi + i\sin\psi)$. By **De Moivre's formula**, $$w^n = |w|^n(\cos n\psi + i\sin n\psi).$$ Hence $w^n = z$ is equivalent to $$|w|^n(\cos n\psi + i\sin n\psi) = |z|(\cos\varphi + i\sin\varphi).$$ Two complex numbers in polar form are equal **iff** their absolute values are equal and their arguments differ by an integer multiple of $2\pi$. Therefore this holds iff $$|w|^n = |z| \ \Leftrightarrow\ |w| = \sqrt[n]{|z|}, \qquad\text{and}\qquad n\psi = \varphi + 2k\pi \ \text{ for some } k\in\mathbb{Z} \ \Leftrightarrow\ \psi = \frac{\varphi}{n} + \frac{2k\pi}{n}.$$ The values $k = 0, 1, \ldots, n-1$ give $n$ distinct arguments (they differ by less than $2\pi$), and any other integer $k$ reproduces one of these (since the arguments repeat with period $2\pi$ in $\psi$). Thus there are exactly the $n$ roots $w_0, \ldots, w_{n-1}$ given above. $\blacksquare$ --- ### P4. Number of combinations with repetition — (4 marks) **Statement.** Let $n \in \mathbb{N}^+$ and $k \in \mathbb{N}$. The number of $k$-combinations with repetition of an $n$-element set (selections of $k$ elements, repetition allowed, order irrelevant) is $$\binom{n+k-1}{k}.$$ **Proof.** Let $A = \{a_1, a_2, \ldots, a_n\}$. Any $k$-combination with repetition is determined solely by **how many times** each element is chosen, so we may encode it as a $0$–$1$ sequence: $$\underbrace{1,1,\ldots,1}_{\text{number of } a_1\text{'s}},\,0,\,\underbrace{1,\ldots,1}_{\text{number of } a_2\text{'s}},\,0,\ \ldots\ ,0,\,\underbrace{1,\ldots,1}_{\text{number of } a_n\text{'s}}.$$ The block of $1$'s before the first $0$ tells how many $a_1$'s were chosen, the next block how many $a_2$'s, and so on. This sequence contains exactly $k$ ones (one per chosen element) and $n-1$ zeros (the separators between the $n$ groups), so it has length $n - 1 + k$. Conversely, every such sequence corresponds to exactly one combination with repetition. The number of such sequences equals the number of ways to choose the $k$ positions for the $1$'s among the $n+k-1$ positions, which is $\dbinom{n+k-1}{k}$. Hence the number of $k$-combinations with repetition of $A$ is $\dbinom{n+k-1}{k}$. $\blacksquare$ --- ## Mark check - **Part 1:** 18 marks available — all answered (need ≥ 9 to pass). - **Part 2:** 16 marks available — all four proofs answered (need ≥ 7 to pass). - Reaching ≥ 29 total qualifies for grade **5**.