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

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

Задача 1

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

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

Решение

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

Нам необязательно считать 2 и 3 столбец, информации в первом достаточно для решения, на экзамене так можно было бы сэкономить время.

Получаем тривиальную систему:

Таким образом, мы заполнили 3 столбец, получив в итоге матрицу

Задача 2

Что вы можете сказать о сходимости (абсолютной или условной) ряда , если известно, что ряд сходится (а) абсолютно, (б) условно?

Решение

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

Докажем вспомогательное утверждение (1).

Ряд сходится сходится .

Для этого представим второй ряд как (кроме, может быть, выколотой точки -a).

Заметим, что ряд можно представь как , где . Отбросим члены до , это не повлияет на сходимость. Тогда выполнены все условия признака Дирихле сходимости ряда. А именно:

1. Последовательность частичных сумм ограничена, так как ряд сходится.
2.
3.

Значит, ряд сходится. Хорошо, теперь приступим к заданию.

a) T сходится абсолютно, то есть ряд сходится. Разобьём эту сумму:

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

Отсюда, пользуясь утверждением (1), получаем что сходится.

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

А мы уже знаем, что ряд сходится. Тогда получается, что ряд — это сумма 2 сходящихся рядов. Ну значит и он сам сходящийся.

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

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

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

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

так как .

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

Задача 3

Алёна очень любит алгебру. Каждый день, заходя на свой любимый алгебраический форум, она с вероятностью находит там новую интересную задачу про группы, а с вероятностью интересную задачку про кольца. С вероятностью новых задач на форуме не окажется. Пусть — это минимальное число дней, за которые у Алёны появится хотя бы одна новая задача про группы и хотя бы одна про кольца. Найдите распределение случайной величины . В ответе должны участвовать только компактные выражения (не содержащие знаков суммирования, многоточий и пр.).

Решение

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

Задача 4

Дан массив вещественных чисел, отсортированный по возрастанию, а также числа , , . Предложите алгоритм, строящий массив , состоящий из чисел , где , также отсортированный по возрастанию. Ограничение по времени — , по дополнительной памяти — .

Решение

, .

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

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



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

1. после применения порядок остаётся прежним.
2. после применения порядок будет обратным.

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

Тогда бинпоиском за найдём место в , в котором массив делится на эти самые доли. Сделаем reverse левой части. Применим ко всем элементам функцию . Получили 2 отсортированных массива. С помощью процедуры merge за по времени и по памяти получим целиком отсортированный массив.

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

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

1.
2.

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

Задача 5

Вещественнозначная функция определена на отрезке и дифференцируема на нём. Докажите, что найдётся точка , для которой

Решение

Давайте докажем от противного. Пусть .

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

Обозначим эту функцию как . Заметим, что . То есть мы пользуемся тем, что функция растёт не менее быстро, получаем, что и разница с изначальной точкой будет не меньше, чем у .

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

Мы знаем, что . Тогда на существует хотя бы одна точка такая, что (потому что шаг ). В этой точке . При этом мы знаем, что .

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

Задача 6

Квадратная вещественная матрица такова, что , где — многочлен с ненулевым свободным членом. Докажите, что обратима. Верно ли, что для любого оператора найдётся многочлен и некоторый базис, в котором матрица удовлетворяет условию ?

Решение

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

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

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

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

Но мы знаем, что . Получили противоречие.

2. Рассмотрим линейный оператор с матрицей в стандартном базисе.

Тогда в любом другом базисе матрица будет иметь вид , где — матрица перехода.

Заметим, что , значит . Тогда .

Пусть . Так как все степени выше 1 обнуляются, .

При этом , так как иначе, пользуясь первым пунктом, можем получить, что матрица обратима, а это не так (т.к. ).

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

Распишем: .

Теперь рассмотрим несколько случаев:

1. :

Подставим в другое место:

Наша матрица размерности всего 2, поэтому вполне можем расписать поэлементно:

Но мы знаем что . Распишем определитель:

.
Получили противоречие. Матрица оператора в стандартном базисе ненулевая, она не может быть нулевой в другом базисе.

2. :

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

При этом

И снова получаем противоречие.

3. .

Здесь тогда тоже получаем, что .

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

Задача 7

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

Решение

Сначала покажем, что диаметр графа .

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



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



Будем доказывать от противного. Пусть есть вершины . Возьмём ещё одну произвольную вершину . Снова, эти вершины составляют цикл. Но тогда, как бы мы ни разместили вершины в этом цикле, расстояние от до хотя бы одной из вершин , или будет равно 1, получили противоречие.



Получили, , то есть каждая вершина имеет степень не меньше .

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

Рассмотрим . Если в изначальном графе у нас степень вершины , то в обратном .

Тогда обратный граф состоит из набора «цепей» (1) и «циклов» (2). Другие структуры невозможны из-за жёсткого ограничения .



В компонентах вида (1) можно найти независимое множество размера , вида (2) — .

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

Понятно, что это число будет минимальным, если мы по возможности будем округлять вниз, при этом с наибольшими потерями. Этого можно добиться, например, взяв 10 компонент размера 3. Тогда получим нижнюю оценку.

То есть мы показали, что в обратном графе максимальное независимое множество имеет размер 10 или больше, то есть в графе существует клика размера 10 или больше. Что и требовалось доказать.

Задача 8

Найдите предел

Решение

Здесь нужно по виду формулы догадаться о теории вероятностей.

Введём случайную величину:

Пусть монетка неправильная — орёл выпадает с вероятностью .

Тогда это в точности значение под знаком суммирования:

— это количество возможных размещений орлов (ещё 1 выпадает в конце).
— это вероятность выпадения орлов на выбранных позициях.
— это вероятность выпадения решек на оставшихся позициях.

Тогда наш предел превращается в

Заметим, что вероятность события можно интерпретировать по-другому. Это вероятность того, что за бросков выпадет орлов.

Введём новую случайную величину:

При этом величину можно представить как сумму элементарных:

Тогда

Применим центральную предельную теорему к . Получим:

Вспоминаем, что у нас нормальное распределение симметрично относительно матожидания и получаем итоговый ответ:

Заключение

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

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

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