swaddling5212 19 фев 2020 в 11:06

Полный разбор экзамена ШАД-2019

6 мин

37K

Занимательные задачкиПрограммирование*Алгоритмы*Математика*

Привет! Меня зовут Азат, я студент 3 курса Факультета Компьютерных Наук ВШЭ. На днях ко мне обратился знакомый с Экономики ВШЭ и попросил помочь с решением задач вступительного экзамена в ШАД. Мы с однокурсником Даниилом посмотрели на задания, они показались нам довольно сложными, но очень интересными, захотелось поломать над ними голову. В итоге мы прорешали 1 из вариантов 2019 года и хотим показать наши решения миру.

Задача 1

Заполните третий столбец матрицы

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

если известно, что это матрица ортогональной проекции на некоторую плоскость.

Решение

Назовём эту матрицу $inline$ , воспользуемся свойством ортогональных проекторов:
$inline$ и займёмся арифметикой:

$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$ сходится (а) абсолютно, (б) условно?

Решение

Введём обозначения:

$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$ . Отбросим члены до $inline$ , это не повлияет на сходимость. Тогда выполнены все условия признака Дирихле сходимости ряда. А именно:

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$

Мы можем без влияния на сходимость заменить первые $inline$ элементов, тогда получим:

$\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|$ сходится.

Выкинем первые $inline$ членов каждого из этих рядов (опять же, это не влияет на их сходимость) и рассмотрим разность:

$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|$ сходится. Тогда получается, что ряд $inline$ — это сумма 2 сходящихся рядов. Ну значит и он сам сходящийся.

б) $inline$ сходится условно, то есть ряд $inline$ сходится, а ряд $inline$ — нет.

Докажем, что тогда ряд $inline$ тогда тоже сходится условно.

Опять же, из сходимости ряда $inline$ с помощью утверждения (1) следует сходимость ряда $inline$ . Из тех же соображений о разности, что и в предыдущем пункте, применённых теперь к $inline$ и $inline$ , получим, что ряд $inline$ сходится. Осталось лишь доказать, что ряд $inline$ не сходится.

Будем действовать от противного. Пусть $inline$ сходится. Тогда, отбросив первые $inline$ членов $inline$ и $inline$ , поймём, что:

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

Но эти ряды положительные, поэтому если сходится больший из них, то сходится и меньший. Значит $inline$ сходится, противоречие.

Задача 3

Алёна очень любит алгебру. Каждый день, заходя на свой любимый алгебраический форум, она с вероятностью $\frac14$ находит там новую интересную задачу про группы, а с вероятностью $\frac{1}{10}$ интересную задачку про кольца. С вероятностью $\frac{13}{20}$ новых задач на форуме не окажется. Пусть $inline$ — это минимальное число дней, за которые у Алёны появится хотя бы одна новая задача про группы и хотя бы одна про кольца. Найдите распределение случайной величины $inline$ . В ответе должны участвовать только компактные выражения (не содержащие знаков суммирования, многоточий и пр.).

Решение

Нам нужно найти $inline$ . Для этого надо понять на пальцах, в каком случае $inline$ . Первый случай — когда в каждый из предыдущих $inline$ дней либо не было задач, либо были только про группы, а в $inline$ -ый попалась задача про кольца. Второй случай — когда в каждый из предыдущих $inline$ дней либо не было задач, либо были только про кольца, а в $inline$ -ый попалась задача про группы. На самом деле мы оба раза учли не подходящий случай, когда все предыдущие $inline$ дней задач не было вообще. С поправкой на это ответ будет таким:

$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]}$ вещественных чисел, отсортированный по возрастанию, а также числа $inline$ , $inline$ , $inline$ . Предложите алгоритм, строящий массив $\text{B[1:n]}$ , состоящий из чисел $inline$ , где $x \in \text{A}$ , также отсортированный по возрастанию. Ограничение по времени — $inline$ , по дополнительной памяти — $inline$ .

Решение

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

Сначала предположим, что $inline$ .

Изобразим нашу функцию.

Заметим, что:

1. $\forall x: x > -\frac{q}{2p}$ после применения $inline$ порядок остаётся прежним.
2. $\forall x: x \leq -\frac{q}{2p}$ после применения $inline$ порядок будет обратным.

То есть для «правой» части после применения к каждому значению функции $inline$ подпоследовательность остаётся правильно отсортированной, для левой части она становится отсортированной в обратном порядке.

Тогда бинпоиском за $O(\log{n})$ найдём место в $inline$ , в котором массив делится на эти самые доли. Сделаем reverse левой части. Применим ко всем элементам функцию $inline$ . Получили 2 отсортированных массива. С помощью процедуры merge за $inline$ по времени и по памяти получим целиком отсортированный массив.

В случае $inline$ решим задачу для $inline$ , а затем сделаем reverse всего массива и домножим каждое значение $inline$ на -1. Получим правильный результат.

В случае $inline$ порядок зависит от знака $inline$ .

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$

И построение в этом случае сводится к применению функции ко всем значениям. Только в случае $inline$ за $inline$ надо ещё сделать reverse. В случае когда $q \geq 0$ порядок уже правильный.

Задача 5

Вещественнозначная функция $inline$ определена на отрезке $inline$ $(b-a \geqslant 4)$ и дифференцируема на нём. Докажите, что найдётся точка $x_0 \in (a;b)$ , для которой

$display$

Решение

Давайте докажем от противного. Пусть $\forall x \in (a; b): f'(x) \geq 1 + f^2(x)$ .

Сначала посмотрим, что будет происходить при равенстве:

$display$

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

Обозначим эту функцию как $inline$ . Заметим, что $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)$ . То есть мы пользуемся тем, что функция $inline$ растёт не менее быстро, получаем, что и разница с изначальной точкой будет не меньше, чем у $inline$ .

Функция $inline$ у нас имеет константу $inline$ . Примем значение этой константы таким, что $inline$ . Тогда:

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

Мы знаем, что $b - a \geq 4$ . Тогда на $inline$ существует хотя бы одна точка $inline$ такая, что $x'+C = \frac{\pi}{2} + \pi k$ (потому что шаг $\pi < 4$ ). В этой точке $g(x') = +\infty$ . При этом мы знаем, что $f(x') \geq g(x') \Rightarrow f(x') = +\infty$ .

Получили, что в какой-то из точек $inline$ функция уходит на бесконечность. А значит функция терпит разрыв, то есть не является непрерывной, а это дано нам в условии. Получили противоречие.

Задача 6

Квадратная вещественная матрица $inline$ такова, что $A^\text{T} = p(A)$ , где $inline$ — многочлен с ненулевым свободным членом. Докажите, что $inline$ обратима. Верно ли, что для любого оператора $\varphi : \mathbb{R}^n \to \mathbb{R}^n$ найдётся многочлен $inline$ и некоторый базис, в котором матрица $\varphi$ удовлетворяет условию $A^\text{T} = p(A)$ ?

Решение

В начале, покажем, что $inline$ , распишем подробно:

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

Отсюда можно получить, что $inline$ .

1. Будем доказывать от противного. Пусть матрица $inline$ необратима. Тогда существует вектор $x \neq 0$ такой, что $inline$ . Тогда ещё можно сказать, что $inline$ . Теперь распишем это:

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

Теперь пользуемся тем, что $inline$ :

$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$ , где $inline$ — матрица перехода.

Заметим, что $inline$ , значит $A^n = 0 \; \forall n \geq 2$ . Тогда $B^n = C^{-1} A^n C = 0 \; \forall n \geq 2$ .

Пусть $inline$ . Так как все степени выше 1 обнуляются, $B^T = \alpha B + \beta E$ .

При этом $\beta = 0$ , так как иначе, пользуясь первым пунктом, можем получить, что матрица $inline$ обратима, а это не так (т.к. $\operatorname{det} B = \operatorname{det} A = 0$ ).

Вспомним, что $inline$ .

Распишем: $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$ :

Тогда после подстановки получаем $inline$ . Тогда $inline$ .

При этом

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

Значит нет многочлена и базиса в котором матрица $inline$ оператора $\phi$ представима, как $inline$ . Что и требовалось доказать.

Задача 7

Дан граф с $inline$ вершинами. Известно, что для любых $inline$ вершин в графе есть цикл длины $inline$ , содержащий эти вершины. Докажите, что найдётся $inline$ вершин, попарно соединённых рёбрами друг с другом.

Решение

Сначала покажем, что диаметр графа $\operatorname{diam} G \leq 2$ .

Выберем 2 самые удалённые друг от друга вершины $inline$ и $inline$ и 3 произвольные. По условию дано, что любые 5 вершин составляют цикл. Значит есть и цикл, состоящий из этих 5 вершин. В этом цикле путь от $inline$ до $inline$ будет максимум 2 (видно на картинке). Значит $\operatorname{diam} G \leq 2$ .

Теперь зафиксируем произвольную вершину $v \in G$ . Мы уже сделали вывод, что до любой другой вершины графа расстояние от $inline$ равно либо 1, либо 2. Покажем, что на «‎втором уровне»‎ не больше $inline$ вершин:

Будем доказывать от противного. Пусть есть вершины $a, b, c \in L_2$ . Возьмём ещё одну произвольную вершину $x \in G$ . Снова, эти вершины составляют цикл. Но тогда, как бы мы ни разместили вершины в этом цикле, расстояние от $inline$ до хотя бы одной из вершин $inline$ , $inline$ или $inline$ будет равно 1, получили противоречие.

Получили, $|L_2| \leq 2 \Rightarrow |L_1| \geq 30 - 1 - 2 = 27$ , то есть каждая вершина имеет степень не меньше $inline$ .

Теперь попробуем с этой информацией найти клику (вершины, попарно соединённые рёбрами — то, что требуется в условии) длины 10. Найти клику размера 10 в графе $inline$ — это то же самое, что найти независимое множество (то есть вершины, между которыми вообще нет рёбер) того же размера 10 в обратном графе $\overline{G}$ .

Рассмотрим $\overline{G}$ . Если в изначальном графе $inline$ у нас степень вершины $inline$ $\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$ .

Пусть $inline$ — общее количество компонент в обратном графе, а $inline$ — количество «цепочек». Тогда размер максимального независимого множества будет равен:

$| 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 или больше, то есть в графе $inline$ существует клика размера 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}$ — это количество возможных размещений $inline$ орлов (ещё 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$ можно интерпретировать по-другому. Это вероятность того, что за $inline$ бросков выпадет $\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$

Заключение

В целом экзамен довольно сложный. Мой знакомый пожаловался, что подготовиться непросто. Это действительно так — нужно не только знать обширную математическую теорию, но и иметь навык решения олимпиадных задачек, в ШАДе дают именно такие. Поэтому для подготовки нужно много тренироваться, вспоминать теорию и набивать руку.

Если у вас есть другие идеи решения задач или какие-то замечания, смело пишите мне в телеграм @Azatik1000. Всегда рад ответить!

Азат Калмыков, куратор в «ШАД Helper»

Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.

Какое задание показалось вам наиболее интересным?

13.33% 14

13.33% 24

10% 33

10% 43

13.33% 54

20% 66

46.67% 714

46.67% 814

Проголосовали 30 пользователей. Воздержались 43 пользователя.

Теги:

Хабы:

Полный разбор экзамена ШАД-2019

Задача 1

Задача 2

Задача 3

Задача 4

Задача 5

Задача 6

Задача 7

Задача 8

Заключение

Публикации

Истории

Ближайшие события