Exam 2023 (A)

1a

\begin{matrix} \dots \end{matrix}

1b

\begin{matrix} Let n \geq 4 be an even number \\ Prove by induction: \exists tree T = (V, E) : | V | = n : \forall v \in V : d e g (v) \in {1, 3} \\ Proof: \\ Base case. Let n = 4 \end{matrix}

graph TD

1---2
1---3
1---4

\begin{matrix} Induction step. Let the statement hold for n \\ Let G = (V, E) be a tree with n vertices \\ Let \forall v \in V : d e g (v) \in {1, 3} \\ G is a tree ⟹ \exists v \in V : d e g (v) = 1 \\ Let u, w \notin V \\ Let G^{'} = (V \cup {u, w}, E \cup {{v, u}, {v, w}}) \\ d e g (v) = 3 in G^{'} \\ d e g (u) = d e g (w) = 1 in G^{'} \\ ⟹ \forall v \in V \cup {u, w} : d e g (v) \in {1, 3} \\ G^{'} has n + 2 vertices \\ ⟹ Proved by Induction \end{matrix}

2a

\begin{matrix} Prove or disprove: R, S are equivalence relations on A \\ ⟹ R △ S is an equivalence relation on A \\ Disproof: \\ \forall a \in A : (a, a) \in R, (a, a) \in S ⟹ (a, a) \notin R △ S \\ ⟹ R △ S is not reflexive ⟹ R △ S is not an equivalence relation \end{matrix}

2b

\begin{matrix} Let f : X \to Y \\ Let D, C \subseteq Y \\ Prove or disprove: f^{- 1} [C \cap D] = f^{- 1} [C] \cap f^{- 1} [D] \\ Proof: \\ x \in f^{- 1} [C \cap D] ⟺ \exists y \in C \cap D : f (x) = y ⟺ y \in C \land y \in D \\ ⟺ x \in f^{- 1} [C] \land x \in f^{- 1} [D] ⟺ x \in f^{- 1} [C] \cap f^{- 1} [D] \\ ⟹ f^{- 1} [C \cap D] = f^{- 1} [C] \cap f^{- 1} [D] \end{matrix}

3

\begin{matrix} Let A be a set such that | A | \geq 2 \\ Let f : A \times P (A) \to P (P (A)), f (x, B) = {D \subseteq B | x \in D} \end{matrix}

3a

\begin{matrix} Prove: f is not injective \\ Proof: \\ | A | \geq 2 ⟹ \exists a \neq b \in A \\ Let a \neq b \in A \\ a \neq b ⟹ (a, \emptyset) \neq (b, \emptyset) \\ f (a, \emptyset) = f (b, \emptyset) = \emptyset \\ ⟹ f is not injective \end{matrix}

3b

\begin{matrix} Prove: \forall x \in A : \forall B_{1}, B_{2} \in P (A) : f (x, B_{1} \cap B_{2}) = f (x, B_{1}) \cap f (x, B_{2}) \\ Proof: \\ Let x \in A \\ Let B_{1}, B_{2} \in P (A) \\ f (x, B_{1} \cap B_{2}) = {D \subseteq B_{1} \cap B_{2} | x \in D} \\ f (x, B_{1}) \cap f (x, B_{2}) = {D \subseteq B_{1} | x \in D} \cap {D \subseteq B_{2} | x \in D} \\ Let x \notin B_{1} \cap B_{2} \\ ⟹ x \notin B_{1} (symmetric, WLOG) \\ ⟹ f (x, B_{1} \cap B_{2}) = \emptyset and f (x, B_{1}) = \emptyset \\ ⟹ f (x, B_{1} \cap B_{2}) = f (x, B_{1}) \cap f (x, B_{2}) = \emptyset \\ Let x \in B_{1} \cap B_{2} \\ Let C \in f (x, B_{1} \cap B_{2}) \\ ⟹ x \in C \land C \subseteq B_{1} \cap B_{2} ⟹ C \subseteq B_{1} \land C \subseteq B_{2} \\ ⟹ C \in f (x, B_{1}) \land C \in f (x, B_{2}) ⟹ C \in f (x, B_{1}) \cap f (x, B_{2}) \\ ⟹ f (x, B_{1} \cap B_{2}) \subseteq f (x, B_{1}) \cap f (x, B_{2}) \\ Let C \in f (x, B_{1}) \cap f (x, B_{2}) \\ ⟹ x \in C \land C \subseteq B_{1} \land C \subseteq B_{2} ⟹ C \subseteq B_{1} \cap B_{2} ⟹ C \in f (x, B_{1} \cap B_{2}) \\ ⟹ f (x, B_{1}) \cap f (x, B_{2}) \subseteq f (x, B_{1} \cap B_{2}) \\ ⟹ f (x, B_{1} \cap B_{2}) = f (x, B_{1}) \cap f (x, B_{2}) \end{matrix}

3c

\begin{matrix} Prove: \exists x \in A, B_{1}, B_{2} \in P (A) : f (x, B_{1} \cup B_{2}) \neq f (x, B_{1}) \cup f (x, B_{2}) \\ Proof: \\ | A | \geq 2 ⟹ {a, b} \subseteq A \\ Let x = a \\ Let B_{1} = {a}, B_{2} = {b} \\ f (x, B_{1} \cup B_{2}) = f (x, {a, b}) = {{a}, {a, b}} \\ f (x, B_{1}) \cup f (x, B_{2}) = {{a}} \cup \emptyset = {{a}} \\ ⟹ f (x, B_{1} \cup B_{2}) \neq f (x, B_{1}) \cup f (x, B_{2}) \end{matrix}

4a

\begin{matrix} There are 30 students and two buses (red, green) with 15 places \\ How many ways are there to split 30 students into two groups of 15? \\ Solution: \\ No order, no repetition, buses are distinct \\ ⟹ (\binom{30}{15}) \end{matrix}

4b

\begin{matrix} How many ways are there to seat 30 students in a 50-place bus with numbered seats? \\ Solution: \\ Let us first choose 30 places \\ And then arrange children in them, as places are distinct \\ ⟹ (\binom{50}{30}) \cdot 30! = \frac{50!}{30! 20!} \cdot 30! = \frac{50!}{20!} \end{matrix}

4c

\begin{matrix} Teacher wants to assign one of the two tasks to some students \\ No student can do two tasks. How many ways to assign tasks are there? \\ Solution: \\ Let i \in [0, 30] \\ Let i students be assigned with first task \\ Which is (\binom{30}{i}) \\ Let some of 30 - i students be assigned with second task \\ Which is 2^{30 - i} \\ ⟹ \sum_{i = 0}^{30} (\binom{30}{i}) \cdot (2^{30 - i}) \cdot 1^{i} = 3^{30} \end{matrix}

4d

\begin{matrix} 30 students stand in a queue \\ How many ways are there to rearrange them such that \\ no student stands after the student he was before \\ Solution: \\ Let us choose 1 \leq i \leq 29 \\ Let A_{i} = {orders where (i, i + 1) stand as they were} \\ There are | A_{i} | = (\binom{29}{1}) \cdot (30 - 1)! such orders \\ Let us now choose k such indices \\ | A_{i_{1}} \cap A_{i_{2}} \cap \dots \cap A_{i_{k}} | = (\binom{29}{k}) \cdot (30 - k)! \\ ⟹ By Inclusion-Exclusion principle: | ⋃_{i = 1}^{29} A_{i} | = \sum_{k = 1}^{29} (- 1)^{k - 1} (\binom{29}{k}) (30 - k)! \\ The total number of orders is 30! \\ The number of "bad" orders is | ⋃_{i = 1}^{29} A_{i} | \\ ⟹ The answer is: 30! - \sum_{k = 1}^{29} (- 1)^{k - 1} (\binom{29}{k}) (30 - k)! = 30! + \sum_{k = 1}^{29} (- 1)^{k} (\binom{29}{k}) (30 - k)! = \\ = \sum_{k = 0}^{29} (- 1)^{k} (\binom{29}{k}) (30 - k)! \end{matrix}

5

\begin{matrix} R is a relation on A \\ R is called "well-established" if \\ \forall X \neq \emptyset \subseteq A : \exists z \in X : \forall x \in X : (x, z) \in R ⟹ x = z \\ z is then called minimal element of X \end{matrix}

5a

\begin{matrix} Is R an order relation on A ? \\ Solution: \\ Let A = {a} \\ Let R = \emptyset \\ R is well-established, as for all other X subsets of A the implication is vacuously-true \\ (a, a) \notin R ⟹ R is not reflexive \\ ⟹ R is not an order relation \end{matrix}

5b

\begin{matrix} Let A, B sets \\ Let R be a well-established relation on A \\ Let S be a well-established relation on B \\ Let T be a lexicographic order of R, S \\ Meaning T is a relation on A \times B \\ (a_{1}, b_{1}) T (a_{2}, b_{2}) ⟺ [(a_{1} \neq a_{2}) \land (a_{1} R a_{2})] \lor [(a_{1} = a_{2}) \land (b_{1} S b_{2})] \\ Prove: T is well-established on A \times B \\ Proof: \\ Let X \neq \emptyset \subseteq A \times B \\ Let X_{1} = {a | \exists b \in B : (a, b) \in X} \\ X \neq \emptyset ⟹ X_{1} \neq \emptyset ⟹ \exists z_{1} \in X_{1} : \forall a \in X_{1} : (a, z_{1}) \in R ⟹ a = z_{1} \\ Let X_{2} = {b | (z_{1}, b) \in X} \\ X_{1} \neq \emptyset ⟹ X_{2} \neq \emptyset ⟹ \exists z_{2} \in X_{2} : \forall b \in X_{2} : (b, z_{2}) \in S ⟹ b = z_{2} \\ z_{1} \in X_{1}, z_{2} \in X_{2} ⟹ (z_{1}, z_{2}) \in X \\ Let (a, b) \in X \\ (a, b) T (z_{1}, z_{2}) ⟹ [(a \neq z_{1}) \land (a R z_{1})] \lor [(a = z_{1}) \land (b S z_{2})] \\ Let a \neq z_{1} \\ ⟹ a R z_{1} ⟹ a = z_{1} - Contradiction! \\ ⟹ a = z_{1} ⟹ b S z_{2} ⟹ b = z_{2} \\ ⟹ (a, b) = (z_{1}, z_{2}) \\ ⟹ \forall (a, b) \in X : (a, b) T (z_{1}, z_{2}) ⟹ (a, b) = (z_{1}, z_{2}) \end{matrix}

5c

\begin{matrix} Let A be a set \\ Let \subseteq be a relation on P (A) \\ Prove: \subseteq is well-established on P (A) ⟹ A is finite \\ Proof: \\ Let X = {B \subseteq A | B is infinite} \\ X \subseteq P (A) \\ Let X \neq \emptyset \\ \subseteq is well-established on P (A) \\ ⟹ \exists Y \in X : \forall B \in X : B \subseteq Y ⟹ B = Y \\ Y is infinite ⟹ Y \neq \emptyset ⟹ \exists y \in Y \\ Y is infinite ⟹ Y ∖ {y} is also infinite ⟹ Y ∖ {y} \in X \\ Y ∖ {y} \subseteq Y \land Y ∖ {y} \neq Y - Contradiction! \\ ⟹ X = \emptyset ⟹ A is finite \end{matrix}