😟 ❕ ♐️ 全面分析ShAD-2019考试 👩🏽‍💼 📴 🥤

你好！我的名字叫Azat，我是HSE计算机科学学院的三年级学生。几天前，来自HSE经济学的一位朋友与我联系，并寻求帮助来解决经济学院的入学考试问题。我和我的同学丹尼尔（Daniil）看着这些任务，对我们来说，它们似乎很困难，但非常有趣，我想对它们付诸行动。结果，我们解决了2019年的一种选择，并希望向世界展示我们的解决方案。

任务1

填写矩阵的第三列

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

如果已知这是正交投影到某个平面上的矩阵。

决断

称这个矩阵

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

任务2

关于序列的收敛（绝对或条件），您能说什么

$\sum_{n=1}^{\infty} (n+2019)a_n$ ，如果已知该系列

$\sum_{n=1}^{\infty} (n-2019)a_n$ 收敛的（a）绝对地，（b）中有条件？

决断

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

任务3

Alena非常喜欢代数。每天，都有可能去她最喜欢的代数论坛

$\frac14$ 发现关于群体的新的有趣问题，并且很有可能

$\frac{1}{10}$ 关于戒指的一个有趣的难题。很有可能

$\frac{13}{20}$ 论坛上的新任务将不会。让

$X$ -这是Alena至少要完成一项关于组的新任务并且至少要完成关于环的新任务的最少天数。查找随机变量的分布

$X$ 。只有紧凑的表达式（不包含求和符号，点等）才可以参与答案。

决断

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

任务4

丹阵

$\text{A[1:n]}$ 实数（按升序排列）以及数字

$p$ ，

$q$ ，

$r$ 。建议建立阵列的算法

$\text{B[1:n]}$ 由数字组成

$px^2 + qx + r$ 哪里

$x \in \text{A}$ 也按升序排序。时限为

$O(n)$ ，以增加内存-

$O(n)$ 。

决断

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

任务5

实值函数

$f$ 在细分上定义

$[a;b]$

$(b-a \geqslant 4)$ 并在此方面与众不同。证明有一点

$x_0 \in (a;b)$ ，为此

$f'(x_0) < 1 + f^2(x_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)$ . , , . .

任务6

平方实数矩阵

$A$ 这样

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

$p(x)$ -具有非零自由项的多项式。证明

$A$ 可逆的。对任何操作员来说都是真的吗

$\varphi : \mathbb{R}^n \to \mathbb{R}^n$ 有一个多项式

$p(x)$ 以及矩阵的基础

$\varphi$ 满足条件

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

决断

, ,

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

任务7

丹数

$30$ 高峰。众所周知，对于任何

$5$ 图中的顶点有一个长度的循环

$5$ 包含这些顶点。证明有

$10$ 峰通过边缘彼此成对连接。

决断

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

任务8

找到极限

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

决断

.

:

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

结论

一般来说，考试相当复杂。我的朋友抱怨说准备并不容易。确实如此-您不仅需要了解广泛的数学理论，而且还需要具有解决奥林匹克竞赛问题的技能，而在ShAD中，他们给出的正是这样。因此，准备工作需要大量训练，请记住理论并充实自己的手。

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

ShAD Helper的策展人Azat Kalmykov

全面分析ShAD-2019考试

任务1

任务2

任务3

任务4

任务5

任务6

任务7

任务8

结论

More articles: