💑 🧖🏽 🧜🏽 Discrete mathematics in the exam at the ShAD 🤦 📛 🤐

Hello! My name is Azat, I create courses for preparing for the exam in the SHAD. Recently, we launched a course on discrete mathematics, so our team is actively solving problems on the relevant topic. After examining the exam in the SHAD 2019, we saw a great interest of Habr users in entertaining tasks from the exam. Therefore, we post here 4 favorites in discrete mathematics. Enjoy it!

Problem 1 (May 26, 2018, No. 5)

Random value $X$ equal to the length of the cycle containing simultaneously elements 1 and 2, with a random permutation of the set $\{1, 2, \ldots, n\}$ . If there is no such cycle, then $X = 0$ . Find the distribution of a random variable $X$ and her mathematical expectation.

Decision

, , . , $X$ — $P(X = k)$ $k$ . — , $k$ , , $n!$

. . (1 2), $k - 2$ $n - 2$ , $C_{n - 2}^{k - 2}$ . , , , $(n - k)!$ . , . , , . $a$ — $a_1 = b$ , $a_b$ , 1 $b$ ( ). , , $(k -1)!$ . :

P (X = k) = \frac{C_{n - 2}^{k - 2} \cdot (n - k)! \cdot (k - 1)!}{n!} = \frac{k - 1}{n (n - 1)}

$P(X = k) = \frac{C_{n - 2}^{k - 2} \cdot (n - k)! \cdot (k - 1)!}{n!} = \frac{k - 1}{n(n - 1)}$

, $k = 0$ $k = 1$ . $k = 1$ , , ( $P(X = 1) = 0$ , .. , ). , $k > n$ , $P(X = k) = 0$ ( ). , $P(X = 0)$ :

P (X = 0) = 1 - \sum_{k = 1}^{n} \frac{k - 1}{n (n - 1)} = 1 - \frac{1}{n (n - 1)} \cdot \frac{n (n - 1)}{2} = 1 - \frac{1}{2} = \frac{1}{2}

$P(X = 0) = 1 - \sum_{k = 1}^n \frac{k - 1}{n(n - 1)} = 1 - \frac{1}{n(n - 1)} \cdot \frac{n(n - 1)}{2} = 1 - \frac{1}{2} = \frac{1}{2}$

$X$ , :

E (X) = \sum_{k = 1}^{n} k \cdot \frac{k - 1}{n (n - 1)} = \frac{1}{n (n - 1)} (\sum_{k = 1}^{n} k^{2} - \sum_{k = 1}^{n} k) =

$E(X) = \sum_{k = 1}^n k \cdot \frac{k - 1}{n(n - 1)} = \frac{1}{n(n - 1)} \left( \sum_{k = 1}^n k^2 - \sum_{k = 1}^n k \right) =$

= \frac{1}{n (n - 1)} \cdot (\frac{1}{6} n (n + 1) (2 n + 1) - \frac{1}{2} n (n + 1)) = \frac{n + 1}{3}

$= \frac{1}{n(n - 1)} \cdot \left( \frac{1}{6}n(n + 1)(2n + 1) - \frac{1}{2}n(n + 1) \right) = \frac{n + 1}{3}$

Problem 2 (June 4, 2016, No. 3)

Random variables $X$ and $Y$ take two values and $cov(X, Y) = 0$ . Prove that they are independent.

Decision

, , , .

: 0 1, $P(X = 1) = p$ , $P(Y = 1) = q$ , $P(X = 1, Y = 1) = r$ . , $r = pq$ . , $E(X) = P(X = 0) \cdot 0 + P(X = 1) \cdot 1 = P(X = 1) = p$ , $E(Y) = P(Y = 0) \cdot 0 + P(Y = 1) \cdot 1 = P(Y = 1) = q$ , $E(XY) = P(X = 1, Y = 1) = r$ . $cov(X, Y) = E(XY) - E(X)E(Y) = 0$ , $E(XY) = E(X)E(Y)$ $r = pq$ .

, $X$ $Y$ : , ( , : $P(X = 1, Y = 0) = P(X = 1) - P(X = 1, Y = 1) = p - r$ , $P(X = 0, Y = 1) = P(Y = 1) - P(X = 1, Y = 1) = q - r$ , $P(X = 0, Y = 0) = 1 - P(X = 1, Y = 1) - P(X = 0, Y = 1) - P(X = 1, Y = 0)$ ). , , .

$P(X = a) = p, \ P(X = b) = 1 - p, \ P(Y = c) = q, \ P(Y = d) = 1 - q$ , $a < b$ $c < d$ . $X' = \dfrac{X - a}{b - a}$ $Y' = \dfrac{Y - c}{d - c}$ . , $X$ $a$ $b$ , $X'$ 0 1 , $Y$ . , $cov(X', Y') = 0$ , .

E (X^{'}) = \frac{E (X) - a}{b - a} E (Y^{'}) = \frac{E (Y) - c}{d - c}

$E(X') = \frac{E(X) - a}{b - a} \ \ \ E(Y') = \frac{E(Y) - c}{d - c}$

E (X^{'} Y^{'}) = E (\frac{X - a}{b - a} \cdot \frac{Y - c}{d - c}) = \frac{E (X Y) - c E (X) - a E (Y) + a c}{(b - a) (d - c)}

$E(X'Y') = E\left( \frac{X - a}{b - a} \cdot \frac{Y - c}{d - c} \right) = \frac{E(XY) - cE(X) - aE(Y) + ac}{(b - a)(d - c)}$

c o v (X^{'}, Y^{'}) = E (X^{'} Y^{'}) - E (X^{'}) E (Y^{'}) = \frac{E (X Y) - E (X) E (Y)}{(b - a) (d - c)} = \frac{c o v (X, Y)}{(b - a) (d - c)}

$cov(X', Y') = E(X'Y') - E(X')E(Y') = \frac{E(XY) - E(X)E(Y)}{(b - a)(d - c)} = \frac{cov(X, Y)}{(b - a)(d - c)}$

$cov(X, Y) = 0$ , $cov(X', Y') = 0$ , ...

Problem 3 (May 26, 2018, No. 8)

The magical land of Lelandia has 100 cities, some of which are connected by airlines. It is known that more than 90 airlines depart from each city. Prove that there are 11 cities in pairs connected by airlines with each other.

Decision

, — , — . , 91 , 8 . , , , .

( , ). , , , , .., . . 1 9 , , $\lfloor \frac{100}{9} \rfloor = 11$ , .

Problem 4 (June 3, 2017, No. 4)

At Tyndex, each employee has at least 50 acquaintances. It turned out that there are two employees who are familiar with each other only after 9 handshakes (that is, the shortest connecting chain of pairwise familiar people contains 8 intermediate people). Prove that this company has at least 200 employees.

Decision

, 10 . $A_i$ $i$ - , $\forall i \ |A_i| \geq 50$ .

, $A_1, \ A_4, \ A_7, \ A_{10}$ . , . , $|A_1 \cup A_4 \cup A_7 \cup A_{10}| = |A_1| + |A_4| + |A_7| + |A_{10}| \geq 200$ , ...

If you have other ideas for solving problems or any comments, feel free to write to me in telegrams @ Azatik1000. Always happy to answer!

Azat Kalmykov, curator at ShAD Helper

Discrete mathematics in the exam at the ShAD

Problem 1 (May 26, 2018, No. 5)

Problem 2 (June 4, 2016, No. 3)

Problem 3 (May 26, 2018, No. 8)

Problem 4 (June 3, 2017, No. 4)

More articles: