🎣 📕 👺 Análise completa do exame ShAD-2019 👨🏽‍🎓 🔪 📊

Olá! Meu nome é Azat, sou estudante do 3º ano da Faculdade de Ciências da Computação da HSE. Alguns dias atrás, um amigo da HSE Economics entrou em contato comigo e pediu ajuda para resolver os problemas do exame de admissão na School of Economics. Meu colega Daniil e eu olhamos para as tarefas, elas nos pareciam bastante difíceis, mas muito interessantes, eu queria quebrar a cabeça sobre elas. Como resultado, resolvemos uma das opções para 2019 e queremos mostrar nossas soluções para o mundo.

Tarefa 1

Preencha a terceira coluna da matriz

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

se for sabido que esta é a matriz de projeção ortogonal em algum plano.

Decisão

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

Tarefa 2

O que você pode dizer sobre a convergência (absoluta ou condicional) de uma série

$\sum_{n=1}^{\infty} (n+2019)a_n$ se é sabido que a série

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

Decisão

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

Tarefa 3

Alena ama muito álgebra. Todos os dias, indo ao seu fórum algébrico favorito, ela provavelmente

$\frac14$ encontra um novo problema interessante sobre grupos e com probabilidade

$\frac{1}{10}$ Um quebra-cabeça interessante sobre anéis. Com probabilidade

$\frac{13}{20}$ novas tarefas no fórum não serão. Deixe ser

$X$ - este é o número mínimo de dias pelos quais Alena terá pelo menos uma nova tarefa sobre grupos e pelo menos uma sobre anéis. Encontre a distribuição de uma variável aleatória

$X$ . Somente expressões compactas (sem sinais de soma, pontos, etc.) devem participar da resposta.

Decisão

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

Tarefa 4

Dan array

$\text{A[1:n]}$ números reais, classificados em ordem crescente, bem como números

$p$ ,

$q$ ,

$r$ . Sugira um algoritmo construindo uma matriz

$\text{B[1:n]}$ constituído por números

$px^2 + qx + r$ Onde

$x \in \text{A}$ também classificados em ordem crescente. O prazo é

$O(n)$ , para memória adicional -

$O(n)$ .

Decisão

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

Tarefa 5

Função com valor real

$f$ definido no segmento

$[a;b]$

$(b-a \geqslant 4)$ e diferenciável. Prove que existe um ponto

$x_0 \in (a;b)$ , para qual

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

Decisão

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

Tarefa 6

Matriz quadrada real

$A$ de tal modo que

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

$p(x)$ - polinômio com termo livre diferente de zero. Prove que

$A$ reversível. É verdade que para qualquer operador

$\varphi : \mathbb{R}^n \to \mathbb{R}^n$ existe um polinômio

$p(x)$ e alguma base em que a matriz

$\varphi$ satisfaz a condição

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

Decisão

, ,

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

Tarefa 7

Dan conta com

$30$ picos. Sabe-se que para qualquer

$5$ vértices no gráfico, há um ciclo de comprimento

$5$ contendo esses vértices. Prove que existe

$10$ picos conectados em pares por arestas entre si.

Decisão

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

Tarefa 8

Encontre o limite

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

Decisão

.

:

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

Conclusão

Em geral, o exame é bastante complicado. Meu amigo reclamou que a preparação não é fácil. Isso é realmente verdade - você precisa não apenas conhecer a vasta teoria matemática, mas também ter a habilidade de resolver problemas das olimpíadas, na SHAD que eles fornecem exatamente isso. Portanto, para se preparar, você precisa treinar muito, lembre-se da teoria e preencha sua mão.

Se você tiver outras idéias para resolver problemas ou comentários, sinta-se à vontade para me escrever nos telegramas @ Azatik1000 . Sempre feliz em responder!

Azat Kalmykov, curador do ShAD Helper

Análise completa do exame ShAD-2019

Tarefa 1

Tarefa 2

Tarefa 3

Tarefa 4

Tarefa 5

Tarefa 6

Tarefa 7

Tarefa 8

Conclusão

More articles: