❗️ 🏂🏻 👩🏽‍🎓 Analyse complète de l'examen ShAD-2019 🐽 👩🏽‍🤝‍👨🏿 👩‍🎤

salut! Je m'appelle Azat, je suis étudiant en 3e année à la Faculté d'Informatique HSE. Il y a quelques jours, un ami de la HSE Economics m'a contacté et m'a demandé de l'aide pour résoudre les problèmes de l'examen d'entrée à la School of Economics. Mon camarade de classe Daniil et moi avons regardé les tâches, elles nous semblaient plutôt compliquées, mais très intéressantes, je voulais me casser la tête. En conséquence, nous avons résolu 1 des options pour 2019 et voulons montrer nos solutions au monde.

Tache 1

Remplissez la troisième colonne de la matrice

$\frac{1}{6} \left( \begin{array}{ccc} 5&-2&?\\-2&2&?\\-1&-2&? \end{array} \right)$

s'il est connu qu'il s'agit de la matrice de projection orthogonale sur un plan.

Décision

$A$ , :

$A^2=A$ :

$A^2 = \frac{1}{36} \left( \begin{array}{ccc} 5&-2&x\\-2&2&y\\-1&-2&z \end{array} \right) \left( \begin{array}{ccc} 5&-2&x\\-2&2&y\\-1&-2&z \end{array} \right) = \frac{1}{36} \left( \begin{array}{ccc} 29-x & * & * \\ -14-y & * & * \\ -1 - z & * & * \end{array} \right)$

$= \frac{1}{6} \left( \begin{array}{ccc} 5&-2&x\\-2&2&y\\-1&-2&z \end{array} \right) = A$

2 3 , , .

:

$\left\{ \begin{array}{l} 29-x = 5 \cdot 6 \\ -14-y = -2 \cdot 6 \\ -1-z = -1 \cdot 6 \end{array} \right. \Leftrightarrow \left\{ \begin{array}{l} 29 - x=30 \\ -14 -y = -12 \\ -1-z = -6 \end{array} \right. \Leftrightarrow \left\{ \begin{array}{l} x = -1 \\ y=-2 \\ z = 5 \end{array} \right.$

, 3 ,

$A = \frac{1}{6} \left( \begin{array}{ccc} 5&-2&-1\\-2&2&-2\\-1&-2&5 \end{array} \right)$

Tâche 2

Que pouvez-vous dire de la convergence (absolue ou conditionnelle) d'une série

$\sum_{n=1}^{\infty} (n+2019)a_n$ si l'on sait que la série

$\sum_{n=1}^{\infty} (n-2019)a_n$ converge (a) absolument, (b) conditionnellement?

Décision

$S = \sum_{n=1}^{\infty} (n+2019)a_n, T = \sum_{n=1}^{\infty} (n-2019)a_n.$

$S' = \sum_{n=1}^{\infty} |n+2019| |a_n|, \; T' = \sum_{n=1}^{\infty} |n-2019| |a_n|$

$A = \sum_{n=1}^{\infty} a_n, \; A' = \sum_{n=1}^{\infty} |a_n|$

(1).

$\sum_{n=1}^{\infty}(n + a)a_{n}$

$\Rightarrow A' = \sum_{n=1}^{\infty}a_{n}$

$\forall a \in \mathbb{Z}$ .

$\sum_{n=1}^{\infty} \frac{(n+a)a_{n}}{n+a}$ (, , -a).

,

$\sum_{n=1}^\infty \alpha_n \beta_n$ ,

$\alpha_n = \frac{1}{n+a}, \beta_n =(n + a)a_n$ .

$n = max(1, -a + 1)$ , . . :

1.

$B_n = \sum_{k=1}^n \beta_k$ ,

$\sum_{n=1}^\infty \beta_n$ .
2.

$\alpha_n \geqslant \alpha_{n+1}$
3.

$\lim_{n\to\infty} \alpha_n = 0$

, . , .

a) T ,

$T' = \sum_{n=1}^{\infty} |n - 2019| |a_n|$ . :

$T' = \sum_{n=1}^{2018} |n - 2019| |a_n| + \sum_{n=2019}^{\infty} |n-2019| |a_n| = \ldots$

$2018$ , :

$\ldots = \sum_{n=1}^{2018} (n - 2019) |a_n| + \sum_{n=2019}^{\infty} (n-2019) |a_n| = \sum_{n=1}^{\infty} (n - 2019) |a_n|$

, (1),

$\sum_{n=1}^{\infty} |a_n|$ .

$2018$ ( , ) :

$S'-T' = \sum_{n=2019}^{\infty} ((n+2019) - (n-2019))|a_n| = 4038 \sum_{n=2019}^{\infty} |a_n|$

$A' = \sum_{n=1}^{\infty} |a_n|$ . ,

$S' = T'+A'$ — 2 . .

)

$T$ ,

$T'$ — .

,

$S$ .

,

$T$ (1)

$A$ . , ,

$S$

$T$ , ,

$S$ . ,

$S'$ .

.

$S'$ . ,

$2018$

$S'$

$T'$ , , :

$\sum_{n=2019}^{\infty} |n-2019||a_n| \leq \sum_{n=2019}^{\infty} |n+2019||a_n|$

$|n+2019| \geq |n-2019| \; \forall n \geq 2019$ .

, , .

$T'$ , .

Tâche 3

Alena aime beaucoup l'algèbre. Chaque jour, en allant sur son forum algébrique préféré, elle est probablement

$\frac14$ y trouve un nouveau problème intéressant sur les groupes, et avec probabilité

$\frac{1}{10}$ Un puzzle intéressant sur les anneaux. Avec probabilité

$\frac{13}{20}$ les nouvelles tâches sur le forum ne seront pas. Laisser être

$X$ - c'est le nombre minimum de jours pour lesquels Alena aura au moins une nouvelle tâche sur les groupes et au moins une sur les anneaux. Trouver la distribution d'une variable aléatoire

$X$ . Seules les expressions compactes (ne contenant pas de signes de sommation, de points, etc.) devraient participer à la réponse.

Décision

$P[X = k]$ . ,

$X = k$ . —

$k - 1$ , ,

$k$ - . —

$k - 1$ , ,

$k$ - . ,

$k-1$ . :

$P[x=k] = \left( \left( \frac{13}{20} + \frac{1}{4} \right)^{k-1} - \left( \frac{13}{20} \right)^{k-1}\right) \cdot \frac{1}{10} +$

$\left( \left( \frac{13}{20} + \frac{1}{10} \right)^{k-1} - \left( \frac{13}{20} \right)^{k-1}\right) \cdot \frac{1}{4}$

Tâche 4

Tableau Dan

$\text{A[1:n]}$ nombres réels, triés par ordre croissant, ainsi que les nombres

$p$ ,

$q$ ,

$r$ . Suggérer un algorithme de construction d'un tableau

$\text{B[1:n]}$ composé de chiffres

$px^2 + qx + r$ où

$x \in \text{A}$ également triés par ordre croissant. Le délai est

$O(n)$ , pour plus de mémoire -

$O(n)$ .

Décision

$A = [x_1, \ldots, x_n]$ ,

$x_1 \leq \ldots \leq x_n$ .

,

$p > 0$ .

.

, :

1.

$\forall x: x > -\frac{q}{2p}$

$f(x)$ .
2.

$\forall x: x \leq -\frac{q}{2p}$

$f(x)$ .

«»

$f$ , .

$O(\log{n})$

$A$ , . reverse .

$f$ . 2 . merge

$O(n)$ .

$p < 0$

$-f$ , reverse

$f(x)$ -1. .

$p = 0$

$q$ .

1.

$q > 0 \Rightarrow f(x_i) \leq f(x_{i+1}) \, \forall i$
2.

$q < 0 \Rightarrow f(x_i) \geq f(x_{i+1}) \, \forall i$

.

$q < 0$

$O(n)$ reverse.

$q \geq 0$ .

Tâche 5

Fonction à valeur réelle

$f$ défini sur le segment

$[a;b]$

$(b-a \geqslant 4)$ et différenciable sur elle. Prouver qu'il y a un point

$x_0 \in (a;b)$ , Pour qui

$f'(x_0) < 1 + f^2(x_0).$

Décision

$\forall x \in (a; b): f'(x) \geq 1 + f^2(x)$ .

, :

$f'(x) = 1 + f^2(x)$

$\frac{df}{dx} = 1 + f^2 \Leftrightarrow \int \frac{df}{1+f^2} = \int dx$

$arctg(f) = x + C \Rightarrow f(x) = tg(x+C)$

$g(x) = tg(x+C)$ . ,

$f'(x) \geq g'(x) \; \forall x \in (a; b) \Rightarrow f(x) - f(a) \geq g(x) - g(a) \; \forall x \in (a; b)$ . ,

$f$ , , ,

$g$ .

$g$

$C$ . ,

$g(a) = f(a)$ . :

$f(x) - f(a) \geq g(x) - g(a) \Leftrightarrow f(x) \geq g(x)$

$b - a \geq 4$ .

$(a; b)$

$x'$ ,

$x'+C = \frac{\pi}{2} + \pi k$ (

$\pi < 4$ ).

$g(x') = +\infty$ . ,

$f(x') \geq g(x') \Rightarrow f(x') = +\infty$ .

, -

$(a; b)$ . , , . .

Tâche 6

Matrice réelle carrée

$A$ tel que

$A^\text{T} = p(A)$ où

$p(x)$ - polynôme à terme libre non nul. Prouve-le

$A$ réversible. Est-il vrai que pour tout opérateur

$\varphi : \mathbb{R}^n \to \mathbb{R}^n$ il y a un polynôme

$p(x)$ et une base dans laquelle la matrice

$\varphi$ satisfait à la condition

$A^\text{T} = p(A)$ ?

Décision

, ,

$A = p(A^T)$ , :

$A = (A^T)^T = (p(A))^T = (p_n A^n + \ldots + p_1 A + p_0 E)^T$

$= (p_n (A^n)^T + \ldots + A^T + p_0 E) = (p_n (A^T)^n + \ldots + A^T + p_0 E) = p(A^T)$

$A = p(A^T) = p(p(A))$ .

1. .

$A$ .

$x \neq 0$ ,

$Ax = 0$ . ,

$x^T Ax = 0$ . :

$0 = x^T A x = x^T p(A^T) x = x^T (p_n (A^T)^n + \ldots + p_1 A^T + p_0 E ) x$

$= p_n (x^T A^T) (A^T)^{n-1} x + \ldots + p_1 x^T A^T x + p_0 x^T E x$

$x^T A^T = (Ax)^T = 0$ :

$0 = \ldots = p_0 x^T x = p_0 \| x \|$

$p_0 \neq 0 \Rightarrow \| x \| = 0 \Rightarrow x = 0$ . .

2.

$\phi$

$A = \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix}$ .

$B = C^{-1} A C$ ,

$C$ — .

,

$A^2 = 0$ ,

$A^n = 0 \; \forall n \geq 2$ .

$B^n = C^{-1} A^n C = 0 \; \forall n \geq 2$ .

$B^T = p(B)$ . 1 ,

$B^T = \alpha B + \beta E$ .

$\beta = 0$ , , , ,

$B$ , (..

$\operatorname{det} B = \operatorname{det} A = 0$ ).

,

$B = p(B^T) = p(p(B))$ .

:

$B = \alpha (\alpha B) = \alpha^2 B \Rightarrow (1-\alpha^2) B = 0$ .

:

1.

$\alpha = -1$ :

:

$B^T = p(B) = -B \Rightarrow B + B^T = 0$

2, :

$\left\{ \begin{array}{l} b_{11} + b_{11} = 0 \\ b_{12} + b_{21} = 0 \\ b_{21} + b_{12} = 0 \\ b_{22} + b_{22} = 0 \end{array} \right. \Rightarrow \left\{ \begin{array}{l} b_{11} = b_{22} = 0 \\ b_{12} = -b_{21} \\ \end{array} \right.$

$\operatorname{det} B = \operatorname{det} A = 0$ . :

$\operatorname{det} B = 0 \cdot 0 - b_{12}(-b_{12}) = b_{12}^2 = 0 \Rightarrow b_{12} = b_{21} = 0 \Rightarrow B = 0$

.
.

$\phi$ , .

2.

$\alpha = 1$ :

$B^T = p(B) = B$ .

$B^T B = B^2 = 0$ .

$(B^T B)_{ii} = \sum_{k=1}^n (B_{ki})^2 = 0 \; \forall i \Rightarrow B_{ki} = 0 \; \forall k, i \Rightarrow B = 0$

.

3.

$\alpha \neq \pm 1$ .

,

$(1-\alpha)^2 B = 0 \Rightarrow B = 0$ .

$A$

$\phi$ ,

$A^T = p(A)$ . .

Tâche 7

Dan compte avec

$30$ pics. On sait que pour tout

$5$ sommets dans le graphique, il y a un cycle de longueur

$5$ contenant ces sommets. Prouver qu'il y a

$10$ pics reliés par paires les uns aux autres.

Décision

$\operatorname{diam} G \leq 2$ .

2

$u$

$v$ 3 . , 5 . , 5 .

$u$

$v$ 2 ( ).

$\operatorname{diam} G \leq 2$ .

$v \in G$ . ,

$v$ 1, 2. , «‎ »‎

$2$ :

$a, b, c \in L_2$ .

$x \in G$ . , . , ,

$v$

$a$ ,

$b$

$c$ 1, .

$|L_2| \leq 2 \Rightarrow |L_1| \geq 30 - 1 - 2 = 27$ ,

$27$ .

(, — , ) 10. 10

$G$ — , ( , ) 10

$\overline{G}$ .

$G$

$v$

$\operatorname{deg}v \geq 27 \; \forall v \in G$ ,

$\operatorname{deg}\overline{v} \leq 2 \; \forall \overline{v} \in \overline{G}$ .

«» (1) «» (2). -

$\operatorname{deg} \overline{v} \leq 2$ .

(1)

$\left \lceil{\frac{m}{2}}\right \rceil$ , (2) —

$\left \lfloor{\frac{m}{2}}\right \rfloor$ .

$k$ — ,

$k_1$ — «». :

$| I | = \sum_{i=1}^{k_1} \left \lceil{\frac{m_i}{2}}\right \rceil + \sum_{i=k_1 + 1}^{k} \left \lfloor{\frac{m_i}{2}}\right \rfloor \text{ } \sum_{i=1}^{k} m_i = 30$

, , , . , , 10 3. .

$| I | \geq \sum_{i=1}^{10} \left \lfloor{\frac{3}{2}}\right \rfloor = 10$

$\overline{G}$ 10 ,

$G$ 10 . .

Tâche 8

Trouvez la limite

$\lim_{n \to \infty} \sum_{k=n}^{5n} C_{k-1}^{n-1} \left( \frac15 \right)^n \left( \frac45 \right)^{k-n}.$

Décision

.

:

$\xi_{n} = \# \text{ } \; n \, \text{}$

—

$\frac{1}{5}$ .

$P[\xi_n = k]$ :

$P[\xi_n = k] = C_{k-1}^{n-1} \left( \frac15 \right)^n \left( \frac45 \right)^{k-n}$

$C_{k-1}^{n-1}$ —

$n - 1$ ( 1 ).

$\left( \frac{1}{5} \right)^n$ — .

$\left( \frac{4}{5} \right)^{k-n}$ — .

$\lim_{n \to \infty} P[\xi_n \leq 5n].$

$\xi_n \leq 5n$ -. ,

$5n$

$\geq n$ .

:

$S_{5n} = \# \text{ } \, 5n \, \text{}$

$S_{5n} = \sum_{i=1}^{5n} \eta_i, \eta_i = I\{\text{} \, i \, \text{ } \}$

$\mathbb{E} S_{5n} = \sum_{i=1}^{5n} \mathbb{E} \eta_i = 5n \cdot \frac15 = n$

$S_{5n}$ . :

$\lim_{n \to \infty} P[\xi_n \leq 5n] = \lim_{n \to \infty} P[S_{5n} \geq n] = \lim_{n \to \infty} P[S_{5n} - n \geq 0] =$

$\lim_{n \to \infty} P[\frac{S_{5n} - n}{\sigma\sqrt{n}} \geq 0] = P[\eta \geq 0], \eta \sim N(0, 1)$

, :

$\lim_{n \to \infty} P[\xi_n \leq 5n] = P[\eta \geq 0] = \frac12$

Conclusion

En général, l'examen est assez compliqué. Mon ami s'est plaint que la préparation n'est pas facile. C'est vraiment le cas - vous devez non seulement connaître la vaste théorie mathématique, mais également avoir les compétences pour résoudre les problèmes d'olympiades, dans le ShAD qu'ils donnent exactement. Par conséquent, pour vous préparer, vous devez vous entraîner beaucoup, souvenez-vous de la théorie et remplissez votre main.

Si vous avez d'autres idées pour résoudre des problèmes ou des commentaires, n'hésitez pas à m'écrire dans les télégrammes @ Azatik1000 . Toujours heureux de répondre!

Azat Kalmykov, conservateur chez ShAD Helper

Analyse complète de l'examen ShAD-2019

Tache 1

Tâche 2

Tâche 3

Tâche 4

Tâche 5

Tâche 6

Tâche 7

Tâche 8

Conclusion

More articles: