19.02.2020 08:06
DeathCookies 20 10400 Источник
Привет! Меня зовут Азат, я студент 3 курса Факультета Компьютерных Наук ВШЭ. На днях ко мне обратился знакомый с Экономики ВШЭ и попросил помочь с решением задач вступительного экзамена в ШАД. Мы с однокурсником Даниилом посмотрели на задания, они показались нам довольно сложными, но очень интересными, захотелось поломать над ними голову. В итоге мы прорешали 1 из вариантов 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$ сходится (а) абсолютно, (б) условно?

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

$ 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' $ сходится, противоречие.

Задача 3


Алёна очень любит алгебру. Каждый день, заходя на свой любимый алгебраический форум, она с вероятностью $\frac14$ находит там новую интересную задачу про группы, а с вероятностью $\frac{1}{10}$ интересную задачку про кольца. С вероятностью $\frac{13}{20}$ новых задач на форуме не окажется. Пусть $X$ — это минимальное число дней, за которые у Алёны появится хотя бы одна новая задача про группы и хотя бы одна про кольца. Найдите распределение случайной величины $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} $.

Рассмотрим $ \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 $




Заключение


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

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

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