Discrete-math 11

Pigeonhole principle

\begin{matrix} | A | > | B | \\ f : A \to B \\ ⟹ \exists a_{1} \neq a_{2} \in A : f (a_{1}) = f (a_{2}) \end{matrix}

\begin{matrix} A \subseteq Z, | A | = 6 \\ Prove: \exists a_{1}, a_{2} \in A : 5 ∣ (a_{1} - a_{2}) \\ Solution: \\ Let B = {Remainders of division by 5} = {0, 1, 2, 3, 4} \\ | A | > | B | \\ f : A \to B \\ f (a) = a \mod 5 \\ ⟹ \exists a_{1}, a_{2} \in A : f (a_{1}) = f (a_{2}) = x \\ ⟹ {\begin{matrix} a_{1} = 5 n + x \\ a_{2} = 5 m + x \end{matrix} \\ ⟹ a_{1} - a_{2} = 5 (n - m) ⟹ f (a_{1} - a_{2}) = 0 ⟹ 5 ∣ (a_{1} - a_{2}) \end{matrix}

\begin{matrix} n \geq 2 women shake hands \\ Prove: there are at least two women who shook the same number of hands \\ Proof: \\ Let A = {women}, | A | = n \\ Let B = {possible numbers of handshakes} \\ Case 1. One woman shook everybody’s hand \\ ⟹ No woman shook 0 hands \\ ⟹ Possible numbers of handshakes is from 1 to n - 1 \\ ⟹ | A | > | B | = n - 1 \\ Case 2. No woman shook everybody’s hand \\ ⟹ Possible numbers of handshakes is from 0 to n - 2 \\ ⟹ | A | > | B | = n - 1 \\ Both cases lead to pigeonhole principle \end{matrix}

\begin{matrix} A =\subseteq {1, \dots, 100}, | A | = 51 \\ Prove: \exists a, b \in A : a ∣ b \\ Proof: \\ \forall x \in A : x = a \cdot 2^{k}, 2 ∤ a \\ Let B = {1, 3, 5, \dots, 99} \\ f : A \to B, f (x) = f (a \cdot 2^{k}) = a \\ | A | > | B | \\ ⟹ \exists x_{1}, x_{2} \in A : f (x_{1}) = f (x_{2}) = a \\ ⟹ {\begin{matrix} x_{1} = a \cdot 2^{i} \\ x_{2} = a \cdot 2^{j} \end{matrix} \\ ⟹ \frac{x_{1}}{x_{2}} = 2^{i - j}, \frac{x_{2}}{x_{1}} = 2^{j - i} \\ ⟹ {\begin{cases} i \leq j ⟹ x_{1} ∣ x_{2} \\ j < i ⟹ x_{2} ∣ x_{1} \end{cases} \end{matrix}

\begin{matrix} | ⋃_{i = 1}^{n} A_{i} | = \sum_{k = 1}^{n} (- 1)^{k - 1} \sum_{1 \leq k_{1} < k_{2} < \dots < k_{k} \leq n} | ⋂_{i \in {k_{1}, k_{2}, \dots, k_{k}}} A_{i} | \\ ⋂_{i = 1}^{n} A_{i}^{c} = {(⋃_{i = 1}^{n} A_{i})}^{c} = U - ⋃_{i = 1}^{n} A_{i} \end{matrix}

\begin{matrix} 80 balls \\ 5 boxes \\ Each box has at most 24 balls \\ Solution: \\ Total number of ways to divide balls into boxes: \\ (\binom{80 + 5 - 1}{80}) \\ Let A = {At least one box has 25 balls} \\ Let A_{i} = {Box i has at least 25 balls} \\ | A_{i} | = (\binom{55 + 5 - 1}{55}) \\ | A_{i} \cap A_{j} | = (\binom{30 + 5 - 1}{30}) \\ | A_{i_{1}} \cap \dots \cap A_{i_{k}} | = (\binom{80 - 25 k + 5 - 1}{80 - 25 k}) = α_{k} \\ ⟹ | ⋃_{i = 1}^{5} A_{i} | = \sum_{k = 1}^{5} (- 1)^{k - 1} (\binom{5}{k}) α_{k} = \sum_{k = 1}^{3} (- 1)^{k - 1} (\binom{5}{k}) α_{k} \\ The final answer is: (\binom{80 + 5 - 1}{80}) - \sum_{k = 1}^{3} (- 1)^{k - 1} (\binom{5}{k}) (\binom{80 - 25 k + 5 - 1}{80 - 25 k}) \end{matrix}

\begin{matrix} A = {1, 2, \dots, n} \\ f : A \to A \\ x \in A is a called a fixed point of f if f (x) = x \\ How many invertible functions with no fixed points there are? \\ Solution: \\ Number of invertible functions on A is n! \\ Let A_{i} = {f \in A^{A} | i is a fixed point of f} \\ | A_{i} | = (n - 1)! \\ | A_{i} \cap A_{j} | = (n - 2)! \\ \dots \\ α_{k} = (n - k)! \\ ⟹ | ⋃_{i = 1}^{n} A_{i} | = \sum_{k = 1}^{n} (- 1)^{k - 1} (\binom{n}{k}) (n - k)! \\ ⟹ The final answer is: n! - \sum_{k = 1}^{n} (- 1)^{k - 1} (\binom{n}{k}) (n - k)! \end{matrix}