Discrete-math 11

1

\begin{matrix} Let r_{1}, \dots, r_{n + 1} \in [0, 1) \subseteq R \\ Prove: \exists 1 \leq i < j \leq n + 1 : | r_{i} - r_{j} | < \frac{1}{n} \\ Proof: \\ Let’s divide [0, 1) into n half-closed intervals: \\ [0, \frac{1}{n}), [\frac{1}{n}, \frac{2}{n}), \dots, [\frac{n - 1}{n}, 1) \\ "Length" of each of these intervals is less than \frac{1}{n} \\ Let A = {r_{1}, \dots, r_{n + 1}} \\ Let B = {[0, \frac{1}{n}), [\frac{1}{n}, \frac{2}{n}), \dots, [\frac{n - 1}{n}, 1)} \\ Let f : A \to B, f determines in which half-closed interval x is \\ | A | = n + 1 > n = | B | \\ ⟹ By the pigeonhole principle, there are at least two numbers r_{i}, r_{j} (i < j) \\ in the same half-closed interval \\ ⟹ \frac{k}{n} \leq r_{i}, r_{j} < \frac{k + 1}{n} \\ ⟹ | r_{i} - r_{j} | < | \frac{k}{n} - \frac{k + 1}{n} | = \frac{1}{n} \end{matrix}

2a

\begin{matrix} Let k \in N \\ Let n = k^{2} + 1 \\ Let A be a set, | A | = n \\ Let {A_{i}}_{i = 1}^{k} be a partition of A into k sets \\ Prove: \exists j \in [1, k] : | A_{j} | \geq k + 1 \\ Proof: \\ Suppose \forall j \in [1, k] : | A_{j} | < k + 1 ⟹ | A_{j} | \leq k \\ {A_{i}}_{i = 1}^{k} is a partition ⟹ \forall i \neq j \in [1, k] : A_{i} \cap A_{j} = \emptyset \\ ⟹ | ⋃_{i = 1}^{k} A_{i} | = \sum_{i = 1}^{k} | A_{i} | \leq k^{2} \\ By definition of partition: ⋃_{i = 1}^{k} A_{i} = A \\ ⟹ | ⋃_{i = 1}^{k} A_{i} | = | A | = n = k^{2} + 1 \\ ⟹ k^{2} + 1 \leq k^{2} - Contradiction! \\ ⟹ \exists j \in [1, k] : | A_{j} | \geq k + 1 \end{matrix}

2b

\begin{matrix} Let L_{n} be a set of 2^{n} + 1 lattice points in R^{n} \\ Prove: \exists p, q \in L_{n} : p \neq q \land midpoint of p, q is also a lattice point \\ Proof: \\ Notation P (x) is used as a parity predicate of x \\ e.g. P (27) = F, P (2) = T \\ Let B = {(P (p_{1}), P (p_{2}), \dots, P (p_{n})) | (p_{1}, p_{2}, \dots, p_{n}) \in L_{n}} \\ In other words, B is a set of binary strings representing parity of a lattice point \\ Let f : L_{n} \to B \\ f (p) = (P (p_{1}), P (p_{2}), \dots, P (p_{n})) \\ e.g. for R^{4} : f ((0, 16, 2, 37)) = (T, T, T, F) \\ | L_{n} | = 2^{n} + 1 > 2^{n} = | B | \\ ⟹ By the pigeonhole principle there exists at least two lattice points p, q such that: \\ f (p) = f (q) \\ Meaning: \\ \exists p \neq q \in L_{n} : \forall i \in [1, n] : P (p_{i}) = P (q_{i}) ⟹ P (p_{i} + q_{i}) \equiv T ⟹ \frac{p_{i} + q_{i}}{2} \in Z \\ ⟹ Midpoint of p, q is a lattice point \end{matrix}

3

\begin{matrix} Alice wants to register for a university where each course has only one lecture per week at \\ the same time. She needs to choose 7 courses from among 30 courses without overlap. \\ Given that each day, from Sunday to Thursday, has 6 courses (for a total of 30) \\ How many ways can Alice register for courses such that \\ she has at least one course each day? \\ Solution: \\ Let Alice ignore some days when choosing courses \\ If she ignores at least one day, then the number of ways to choose courses is: (\binom{30 - 6}{7}) \\ If she ignores at least k days, then the number of ways to choose courses is: (\binom{30 - 6 k}{7}) \\ Alice can ignore at most 3 days ⟹ by the Inclusion-Exclusion principle \\ The answer is: \sum_{k = 0}^{3} (- 1)^{k} (\binom{5}{k}) (\binom{30 - 6 k}{7}) \end{matrix}

4

\begin{matrix} Let S = {1, 2, . . ., 500} \\ How many integers in S are divisible by 2 or 3 or 5? \\ Solution: \\ Let A = {s \in S | 2 ∣ s \lor 3 ∣ s \lor 5 ∣ s} \\ Number of integers in S divisible by 2 is: ⌊ \frac{500}{2} ⌋ = 250 \\ Number of integers in S divisible by 3 is: ⌊ \frac{500}{3} ⌋ = 166 \\ Number of integers in S divisible by 5 is: ⌊ \frac{500}{5} ⌋ = 100 \\ Number of integers in S divisible by 2 and 3 is: ⌊ \frac{500}{2 \cdot 3} ⌋ = 83 \\ Number of integers in S divisible by 2 and 5 is: ⌊ \frac{500}{2 \cdot 5} ⌋ = 50 \\ Number of integers in S divisible by 3 and 5 is: ⌊ \frac{500}{3 \cdot 5} ⌋ = 33 \\ Number of integers in S divisible by 2, 3 and 5 is: ⌊ \frac{500}{2 \cdot 3 \cdot 5} ⌋ = 16 \\ ⟹ By the inclusion-exclusion principle: \\ | A | = | A_{2} | + | A_{3} | + | A_{5} | - | A_{23} | - | A_{25} | - | A_{35} | + | A_{235} | = \\ = 250 + 166 + 100 - 83 - 50 - 33 + 16 \\ ⟹ | A | = 366 \end{matrix}

5a

\begin{matrix} How many ways can 50 identical balls be distributed into 10 different boxes such that \\ Each box has at most 4 balls \\ Solution: \\ If each box has at most 4 balls, then total is at most 40, which is less than 50 \\ ⟹ The answer is 0 \end{matrix}

5b

\begin{matrix} How many ways can 50 identical balls be distributed into 10 different boxes such that \\ Each box has at most 5 balls \\ Solution: \\ If each box has at most 5 balls, then the total is at most 50 \\ \sum_{i = 1}^{10} x_{i} = 50 \\ Let x_{1} < 5 WLOG \\ ⟹ \sum_{i = 2}^{10} x_{i} > 50 - 5 = 45 ⟹ Some box has more than 5 balls \\ ⟹ each box has exactly 5 balls \\ ⟹ The answer is 1 \end{matrix}

5c

\begin{matrix} How many ways can 50 identical balls be distributed into 10 different boxes such that \\ Each box has at most 10 balls \\ Solution: \\ {\begin{matrix} \sum_{i = 1}^{10} x_{i} = 50 \\ \forall i \in [1, 10] : x_{i} \leq 10 \end{matrix} \\ Let at least k boxes have more then 10 balls: \\ ⟹ (\binom{50 - 11 k + 10 - 1}{10 - 1}) = (\binom{59 - 11 k}{9}) \\ There are (\binom{10}{k}) ways to choose these k boxes \\ There are 50 balls ⟹ There are at least 0 and at most 4 boxes with 11 balls or more \\ ⟹ # of ways such that at least one box has more than 10 balls is: \\ By the inclusion-exclusion principle: \sum_{k = 1}^{4} (- 1)^{k + 1} (\binom{10}{k}) (\binom{59 - 11 k}{9}) \\ (- 1)^{k + 1} is due to an inverted sign, because we’re counting the opposites \\ The total # of ways to distribute 50 balls into 10 boxes is: \\ (\binom{50 + 10 - 1}{10 - 1}) = (\binom{59}{9}) \\ ⟹ The final answer is: (\binom{59}{9}) - \sum_{k = 1}^{4} (- 1)^{k + 1} (\binom{10}{k}) (\binom{59 - 11 k}{9}) \\ This can be rewritten as: \sum_{k = 0}^{4} (- 1)^{k} (\binom{10}{k}) (\binom{59 - 11 k}{9}) \end{matrix}

5d

\begin{matrix} How many ways can 50 identical balls be distributed into 10 different boxes such that \\ Each box has at most 12 balls and at least 2 balls \\ Solution: \\ Let’s factor out "at least 2": \sum_{i = 1}^{10} (x_{i} - 2) = 50 - 20 = 30 \\ Now there are 2 balls in each box, for some to have 13, they need 11 more \\ Let’s use the same rhetoric as in 5c \\ This time the total is 30 balls, not 50, so we can only get 2 boxes to have 11 balls or more \\ \sum_{k = 0}^{2} (- 1)^{k} (\binom{30 - 11 k + 10 - 1}{10 - 1}) (\binom{10}{k}) = \sum_{k = 0}^{2} (- 1)^{k} (\binom{39 - 11 k}{9}) (\binom{10}{k}) \\ ⟹ The final answer is: \sum_{k = 0}^{2} (- 1)^{k} (\binom{39 - 11 k}{9}) (\binom{10}{k}) \end{matrix}

6

\begin{matrix} Let n \in N \\ Suppose n people are standing in a line. \\ In how many ways can the people be arranged in line \\ such that no person stands in the same position they were in before? \\ Solution: \\ How many ways there are such that at least one person stays in his position? \\ One fixed position and n - 1 positions left to arrange: (n - 1)! \\ How many ways there are such that at least k people stay in their position? \\ (n - k)! \\ There are (\binom{n}{k}) ways to choose these k people \\ ⟹ By the inclusion-exclusion principle the answer is: \\ \sum_{k = 0}^{n} (- 1)^{k} (n - k)! (\binom{n}{k}) \end{matrix}

7

\begin{matrix} In the exam there are 15 questions numbered from 1 to 15. \\ Each question can either be answered correctly or incorrectly \\ We know that no student answered two consecutive questions correctly \\ There are 1600 students who took the exam \\ Must there be two students with identical answers or not? \\ Solution: \\ Consider a binary string of length 15 \\ How many such strings can we produce without two consecutive ones? \\ Let B be such a string \\ B = (b_{1}, b_{2}, \dots, b_{15}) \\ Let f : N \to N be a function, that counts the number of such strings \\ If b_{15} is a zero, then there are f (14) possibilities for binary string (b_{1}, b_{2}, \dots, b_{14}) \\ If b_{15} is a one, then b_{14} is a zero and there are \\ f (13) possibilities for binary string (b_{1}, b_{2}, \dots, b_{13}) \\ ⟹ f (15) = f (14) + f (13) \\ In other words f (n) = f (n - 1) + f (n - 2) or Fibonacci sequence \\ f (1) = 2 (strings 0 and 1), which is the 3rd Fibonacci number \\ f (2) = 3 (strings 00, 01 and 10), which is the 4th Fibonacci number \\ ⟹ f (n) is (n + 2)^{'} th Fibonacci number \\ ⟹ f (15) = F (17) = 1597 \\ ⟹ There are 1600 students and 1597 different exam answers \\ Let A be a set of students, | A | \\ Let C be a set of possible exam answers, | C | = 1597 < | A | = 1600 \\ Let g : A \to C be a function mapping students to their exam answers \\ | A | > | C | ⟹ By the pigeonhole principle: \exists a_{1}, a_{2} \in A : g (a_{1}) = g (a_{2}) \\ ⟹ There are at least two students with the same answers \end{matrix}

8

\begin{matrix} Let A, B be sets \\ | A | = n, | B | = k, k \leq n \end{matrix}

8a

\begin{matrix} How many injective functions f : A \to B exist? \\ Solution: \\ If k < n, then | A | > | B | ⟹ There are 0 injective functions in B^{A} \\ If k = n, then there are exactly n! injective functions in B^{A} \\ ⟹ The answer is: n! \end{matrix}

8b

\begin{matrix} How many surjective functions f : A \to B exist? \\ Solution: \\ There are a total of k^{n} functions in B^{A} \\ Let’s count functions that do not map to at least i elements: \\ B^{'} \subseteq B, | B^{'} | = k - i \\ f^{'} : A \to B^{'} \in B^{' A}, | B^{' A} | = (k - i)^{n} \\ There are (\binom{k}{i}) ways to choose these i elements \\ ⟹ By the exclusion-inclusion principle # of surjective functions is: \\ \sum_{i = 0}^{k} (- 1)^{i} (\binom{k}{i}) (k - i)^{n} \end{matrix}

9

\begin{matrix} Let p_{1}, \dots, p_{n} \in {T, F} be logical propositions \\ Solution: \\ There are a total of 2^{n} possible assignments for p_{1}, \dots, p_{n} \\ Only one of them has zero Truths, when all propositions are False \\ ⟹ The final answer is: 2^{n} - 1 \end{matrix}

10a

\begin{matrix} Convert (p \to (q \land \neg r)) \lor (r \land p) into CNF and DNF \\ Solution: \\ Let X = (p \to (q \land \neg r)) \lor (r \land p) \\ \begin{array}{ccccccc} p & q & r & q \land \neg r & p \to (q \land \neg r) & r \land p & X \\ 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 & 1 \\ 0 & 1 & 1 & 0 & 1 & 0 & 1 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 1 & 1 \end{array} \\ ⟹ CNF of X is: (\neg p \lor q \lor r) \\ ⟹ DNF of X is: (\neg p) \lor (q) \lor (r) \end{matrix}

10b

\begin{matrix} Convert ((p \to q) \lor \neg r) \land (p \leftrightarrow q) into CNF and DNF \\ Solution: \\ Let X = ((p \to q) \lor \neg r) \land (p \leftrightarrow q) \\ \begin{array}{ccccccc} p & q & r & p \to q & (p \to q) \lor \neg r & p \leftrightarrow q & X \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{array} \\ ⟹ CNF of X is: (p \lor \neg q \lor r) \land (p \lor \neg q \lor \neg r) \land (\neg p \lor q \lor r) \land (\neg p \lor q \lor \neg r) \\ Note that this can be simplified into: (p \lor \neg q) \land (\neg p \lor q) \\ ⟹ DNF of X is: (\neg p \land \neg q \land \neg r) \lor (\neg p \land \neg q \land r) \lor (p \land q \land \neg r) \lor (p \land q \land r) \\ Note that this can be simplified into: (\neg p \land \neg q) \lor (p \land q) \end{matrix}

11a

\begin{matrix} Prove: {\neg, \to} is complete \\ Proof: \\ {\land, \lor, \neg} is complete (there is a DNF for any proposition) \\ p \land q = \neg (\neg p \lor \neg q) \\ ⟹ {\lor, \neg} is also complete \\ p \lor q = \neg p \to q \\ ⟹ {\neg, \to} is also complete \end{matrix}

11b

\begin{matrix} Prove: {↑} is complete \\ Proof: \\ {\land, \lor, \neg} is complete (there is a DNF for any proposition) \\ p \lor q = \neg (\neg p \land \neg q) \\ ⟹ {\land, \neg} is also complete \\ \neg p = p ↑ p \\ p \land q = \neg (p ↑ q) = (p ↑ q) ↑ (p ↑ q) \\ ⟹ {↑} is also complete \end{matrix}

11c

\begin{matrix} Prove: {↓} is complete \\ Proof: \\ {\land, \lor, \neg} is complete (there is a DNF for any proposition) \\ p \land q = \neg (\neg p \lor \neg q) \\ ⟹ {\lor, \neg} is also complete \\ \neg p = p ↓ p \\ p \lor q = \neg (p ↓ q) = (p ↓ q) ↓ (p ↓ q) \\ ⟹ {↓} is also complete \end{matrix}