Full analysis of the ShAD-2019 exam

$$$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)$$

:

$$

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

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

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

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

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

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

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

.

:

$$ $$\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$$