🏁 💛 🚐 ShAD考试中的离散数学 🛎️ 🔈 🌚

你好！我的名字叫Azat，我在SHAD中创建准备考试的课程。最近，我们开设了离散数学课程，因此我们的团队正在积极解决相关主题的问题。在SHAD 2019中检查了考试之后，我们看到了Habr用户对从考试中娱乐任务的兴趣。因此，我们在此发布离散数学的4个收藏夹。好好享受！

问题1（2018年5月26日，第5号）

随机值 $X$ 等于同时包含元素1和2的循环的长度，集合的随机排列 $\{1, 2, \ldots, n\}$ 。如果没有这样的周期，那么 $X = 0$ 。查找随机变量的分布 $X$ 和她的数学期望。

决断

, , . , $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}$

问题2（2016年6月4日，第3期）

随机变量 $X$ 和 $Y$ 取两个值 $cov(X, Y) = 0$ 。证明他们是独立的。

决断

, , , .

: 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$ , ...

问题3（2018年5月26日，第8号）

莱兰迪亚的神奇之地拥有100个城市，其中一些城市通过航空公司连接。众所周知，每个城市都有90多家航空公司出发。证明有11个城市成对地通过航空公司相互连接。

决断

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

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

问题4（2017年6月3日，第4号）

在Tyndex，每位员工至少有50位熟人。事实证明，只有两次握手后，就有两名员工彼此熟悉（也就是说，成对熟悉的人的最短连接链包含8个中间人）。证明该公司至少有200名员工。

决断

, 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$ , ...

如果您有其他解决问题的想法或任何意见，请随时通过电报@ Azatik1000给我写信。总是很乐意回答！

ShAD Helper的策展人Azat Kalmykov

ShAD考试中的离散数学

问题1（2018年5月26日，第5号）

问题2（2016年6月4日，第3期）

问题3（2018年5月26日，第8号）

问题4（2017年6月3日，第4号）

More articles: