Discrete-math 25

Exam 2023(A)

\begin{matrix} Prove: for any simple acyclic graph G = (V, E) \\ there is a coloring of vertices in 2 colors such that no adjacent vertices have the same color \\ Proof: \\ Base case. Let n = 1 \\ We can color 1 vertex black and we are done \\ Induction step. Let there be such a coloring for any graph with n vertices \\ Let G = (V, E) be a graph with n + 1 vertices \\ G^{'} is a forest ⟹ Any connected component of G^{'} is a tree \\ Case 1. All connected components each have 1 vertex \\ ⟹ Any vertex can be colored either black or white, there are no adjacent ones \\ Case 2. At least one connected component has 2 vertices or more \\ Any tree with n \geq 2 vertices has at least 1 leaf \\ Let this leaf be vertex v with one neighbor u \\ G^{'} = G ∖ {v} has n vertices ⟹ there is such a coloring for G^{'} \\ Let us use the coloring of G^{'} and let the color of v be different from the color of u \\ ⟹ There is such a coloring for G \\ Proved by induction \end{matrix}

\begin{matrix} Let G = (V, E) be a simple graph \\ Define the complement \overset{―}{G} of graph G \\ To be \overset{―}{G} = (V, \overset{―}{E}) : \overset{―}{E} = {{u, v} | u, v \in V, {u, v} \notin E} \\ Prove: for any simple graph with n \geq 5 vertices either G or \overset{―}{G} has a cycle \\ Proof: \\ | \overset{―}{E} | = \frac{n (n - 1)}{2} - | E | \\ Let | E | \geq n ⟹ G has a cycle \\ Let | E | < n ⟹ | \overset{―}{E} | > \frac{n (n - 1)}{2} - n = \frac{n^{2} - n - 2 n}{2} = \frac{n (n - 3)}{2} \\ n \geq 5 ⟹ \frac{n - 3}{2} \geq \frac{2}{2} = 1 \\ ⟹ \frac{n (n - 3)}{2} \geq n ⟹ | \overset{―}{E} | > n ⟹ \overset{―}{G} has a cycle \end{matrix}

\begin{matrix} Dani has 10 different fruits \\ In how many ways can he arrange them such that 3 apples (green, red, yellow) \\ are next to each other, but banana and orange are not next to each other \\ Solution: \\ There are 3! ways to arrange three apples \\ Let us treat 3 apples as 1 item \\ ⟹ There are 3! \cdot 8! ways to arrange all the fruits \\ Let us subtract the number of ways to arrange the fruits such that \\ apples are next to each other and banana and orange are next to each other \\ Let us treat banana and orange as 1 item \\ There are 3! \cdot 2! \cdot 7! ways to do so \\ ⟹ The final answer is: 3! \cdot 8! - 3! \cdot 2! \cdot 7! \end{matrix}

\begin{matrix} Now Dani needs to plan 3 of his school lunches with these 10 different fruits \\ His mom allows him to take at most 5 fruits per day \\ Solution: \\ Let us count the total number of options without the limit of 5: \\ Each fruit can be taken in one of three days \\ ⟹ the number of such options is 3^{10} \\ Let us now count the number of options where Dani took exactly 6 \leq k \leq 10 \\ fruits in one day \\ It is \sum_{k = 6}^{10} (\binom{10}{k}) \cdot 2^{10 - k} \\ Dani can take more than 5 fruits in only one day \\ ⟹ The answer is: 3^{10} - (\binom{3}{1}) \sum_{k = 6}^{10} (\binom{10}{k}) \cdot 2^{10 - k} \end{matrix}

\begin{matrix} Prove combinatorially: \sum_{i = 0}^{n - 1} 9^{i} (\binom{n - 1}{i}) = 10^{n - 1} \\ Proof: \\ On the right side we are making a (n - 1) -long string of decimal digits \\ ⟹ 10^{n - 1} \\ On the left side we first choose (n - 1 - i) places for digit 0 which is (\binom{n - 1}{i}) \\ And then choose i places for 9 digits left which is 9^{i} \\ ⟹ The left side is \sum_{i = 0}^{n - 1} 9^{i} (\binom{n - 1}{i}) \\ ⟹ \sum_{i = 0}^{n - 1} 9^{i} (\binom{n - 1}{i}) = 10^{n - 1} \end{matrix}

\begin{matrix} Park has 4 stations: crafting, ice skating, water fight and science \\ The day is divided into 10 hours, each visit to the station takes 1 hour \\ After water-fight children are not allowed to do ice-skating \\ In how many ways can the child plan his day? \\ Solution: \\ Case 1. There are no water-fights in the plan \\ ⟹ There are 3^{10} options \\ Case 2. There is a first water-fight in the i -th position in the plan \\ There are 3^{i - 1} options before water-fight and 3^{10 - i} options after it \\ ⟹ number of such options is: 3^{9} \\ There are 10 options for i \\ ⟹ There are a total of 10 \cdot 3^{9} such options \\ ⟹ The final answer is: 3^{10} + 10 \cdot 3^{9} \end{matrix}

\begin{matrix} Prove combinatorially: \sum_{k = 0}^{n} (\binom{2 n + 1}{k}) = 2^{2 n} \\ Proof: \\ Let us choose two disjoint groups of numbers from [2 n + 1] \\ This is \sum_{k = 0}^{n} (\binom{2 n + 1}{k}) \\ Let us now take number 1 to be a first group \\ Let us now separate 2 n elements left into two groups: \\ Group of 1 and the other one \\ There are 2^{2 n} ways to do so \\ ⟹ \sum_{k = 0}^{n} (\binom{2 n + 1}{k}) = 2^{2 n} \end{matrix}