🐿️ 🦄 👨‍🎤 Matemáticas discretas en el examen en el ShAD 🖐️ ❗️ 🌥️

¡Hola! Mi nombre es Azat, creo cursos para prepararme para el examen en el SHAD. Recientemente, lanzamos un curso sobre matemáticas discretas, por lo que nuestro equipo está resolviendo problemas activamente sobre el tema relevante. Después de examinar el examen en el SHAD 2019, vimos un gran interés de los usuarios de Habr en entretener tareas del examen. Por lo tanto, publicamos aquí 4 favoritos en matemáticas discretas. ¡Disfrútala!

Problema 1 (26 de mayo de 2018, n. ° 5)

Valor aleatorio $X$ , 1 2, $\{1, 2, \ldots, n\}$ . , $X = 0$ . $X$ .

De hecho, la tarea se centra más en la combinatoria que en la teoría. Por definición, la distribución $X$ Son los valores $P(X = k)$ por todo lo posible $k$ . Cada uno de estos valores es la relación del número de permutaciones en las que hay un ciclo de longitud requerido $k$ al número de todas las permutaciones, que es igual a $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 (4 2016, №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)}$

Pero por condicion $cov(X, Y) = 0$ de donde $cov(X', Y') = 0$ y los valores requeridos son independientes,

3 (26 2018, №8)

100 , . , 90 . , 11 , .

Construiremos un gráfico donde los picos son ciudades y los bordes son aerolíneas. Considere un vértice arbitrario, está conectado a al menos 91 vértices y, por lo tanto, no pueden faltar más de 8 bordes. Eliminamos del gráfico todos los vértices que no están conectados al seleccionado y a sí mismo, después de lo cual seleccionamos otro vértice en el gráfico restante y repetimos el proceso.

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

4 (3 2017, №4)

«» 50 . , , 9 ( 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. !

, « Helper»

Matemáticas discretas en el examen en el ShAD

Problema 1 (26 de mayo de 2018, n. ° 5)

2 (4 2016, №3)

3 (26 2018, №8)

4 (3 2017, №4)

More articles: