Привет! Меня зовут Азат, я студент 3 курса Факультета Компьютерных Наук ВШЭ. На днях ко мне обратился знакомый с Экономики ВШЭ и попросил помочь с решением задач вступительного экзамена в ШАД. Мы с однокурсником Даниилом посмотрели на задания, они показались нам довольно сложными, но очень интересными, захотелось поломать над ними голову. В итоге мы прорешали 1 из вариантов 2019 года и хотим показать наши решения миру.
Заполните третий столбец матрицы
если известно, что это матрица ортогональной проекции на некоторую плоскость.
Что вы можете сказать о сходимости (абсолютной или условной) ряда , если известно, что ряд сходится (а) абсолютно, (б) условно?
Алёна очень любит алгебру. Каждый день, заходя на свой любимый алгебраический форум, она с вероятностью находит там новую интересную задачу про группы, а с вероятностью интересную задачку про кольца. С вероятностью новых задач на форуме не окажется. Пусть — это минимальное число дней, за которые у Алёны появится хотя бы одна новая задача про группы и хотя бы одна про кольца. Найдите распределение случайной величины . В ответе должны участвовать только компактные выражения (не содержащие знаков суммирования, многоточий и пр.).
Дан массив вещественных чисел, отсортированный по возрастанию, а также числа , , . Предложите алгоритм, строящий массив , состоящий из чисел , где , также отсортированный по возрастанию. Ограничение по времени — , по дополнительной памяти — .
Вещественнозначная функция определена на отрезке и дифференцируема на нём. Докажите, что найдётся точка , для которой
Квадратная вещественная матрица такова, что , где — многочлен с ненулевым свободным членом. Докажите, что обратима. Верно ли, что для любого оператора найдётся многочлен и некоторый базис, в котором матрица удовлетворяет условию ?
Дан граф с вершинами. Известно, что для любых вершин в графе есть цикл длины , содержащий эти вершины. Докажите, что найдётся вершин, попарно соединённых рёбрами друг с другом.
Найдите предел
В целом экзамен довольно сложный. Мой знакомый пожаловался, что подготовиться непросто. Это действительно так — нужно не только знать обширную математическую теорию, но и иметь навык решения олимпиадных задачек, в ШАДе дают именно такие. Поэтому для подготовки нужно много тренироваться, вспоминать теорию и набивать руку.
Если у вас есть другие идеи решения задач или какие-то замечания, смело пишите мне в телеграм @Azatik1000. Всегда рад ответить!
Азат Калмыков, куратор ШАД Helper
Задача 1
Заполните третий столбец матрицы
если известно, что это матрица ортогональной проекции на некоторую плоскость.
Решение
Назовём эту матрицу , воспользуемся свойством ортогональных проекторов:
и займёмся арифметикой:
Нам необязательно считать 2 и 3 столбец, информации в первом достаточно для решения, на экзамене так можно было бы сэкономить время.
Получаем тривиальную систему:
Таким образом, мы заполнили 3 столбец, получив в итоге матрицу
и займёмся арифметикой:
Нам необязательно считать 2 и 3 столбец, информации в первом достаточно для решения, на экзамене так можно было бы сэкономить время.
Получаем тривиальную систему:
Таким образом, мы заполнили 3 столбец, получив в итоге матрицу
Задача 2
Что вы можете сказать о сходимости (абсолютной или условной) ряда , если известно, что ряд сходится (а) абсолютно, (б) условно?
Решение
Введём обозначения:
Докажем вспомогательное утверждение (1).
Ряд сходится сходится .
Для этого представим второй ряд как (кроме, может быть, выколотой точки -a).
Заметим, что ряд можно представь как , где . Отбросим члены до , это не повлияет на сходимость. Тогда выполнены все условия признака Дирихле сходимости ряда. А именно:
1. Последовательность частичных сумм ограничена, так как ряд сходится.
2.
3.
Значит, ряд сходится. Хорошо, теперь приступим к заданию.
a) T сходится абсолютно, то есть ряд сходится. Разобьём эту сумму:
Мы можем без влияния на сходимость заменить первые элементов, тогда получим:
Отсюда, пользуясь утверждением (1), получаем что сходится.
Выкинем первые членов каждого из этих рядов (опять же, это не влияет на их сходимость) и рассмотрим разность:
А мы уже знаем, что ряд сходится. Тогда получается, что ряд — это сумма 2 сходящихся рядов. Ну значит и он сам сходящийся.
б) сходится условно, то есть ряд сходится, а ряд — нет.
Докажем, что тогда ряд тогда тоже сходится условно.
Опять же, из сходимости ряда с помощью утверждения (1) следует сходимость ряда . Из тех же соображений о разности, что и в предыдущем пункте, применённых теперь к и , получим, что ряд сходится. Осталось лишь доказать, что ряд не сходится.
Будем действовать от противного. Пусть сходится. Тогда, отбросив первые членов и , поймём, что:
так как .
Но эти ряды положительные, поэтому если сходится больший из них, то сходится и меньший. Значит сходится, противоречие.
Докажем вспомогательное утверждение (1).
Ряд сходится сходится .
Для этого представим второй ряд как (кроме, может быть, выколотой точки -a).
Заметим, что ряд можно представь как , где . Отбросим члены до , это не повлияет на сходимость. Тогда выполнены все условия признака Дирихле сходимости ряда. А именно:
1. Последовательность частичных сумм ограничена, так как ряд сходится.
2.
3.
Значит, ряд сходится. Хорошо, теперь приступим к заданию.
a) T сходится абсолютно, то есть ряд сходится. Разобьём эту сумму:
Мы можем без влияния на сходимость заменить первые элементов, тогда получим:
Отсюда, пользуясь утверждением (1), получаем что сходится.
Выкинем первые членов каждого из этих рядов (опять же, это не влияет на их сходимость) и рассмотрим разность:
А мы уже знаем, что ряд сходится. Тогда получается, что ряд — это сумма 2 сходящихся рядов. Ну значит и он сам сходящийся.
б) сходится условно, то есть ряд сходится, а ряд — нет.
Докажем, что тогда ряд тогда тоже сходится условно.
Опять же, из сходимости ряда с помощью утверждения (1) следует сходимость ряда . Из тех же соображений о разности, что и в предыдущем пункте, применённых теперь к и , получим, что ряд сходится. Осталось лишь доказать, что ряд не сходится.
Будем действовать от противного. Пусть сходится. Тогда, отбросив первые членов и , поймём, что:
так как .
Но эти ряды положительные, поэтому если сходится больший из них, то сходится и меньший. Значит сходится, противоречие.
Задача 3
Алёна очень любит алгебру. Каждый день, заходя на свой любимый алгебраический форум, она с вероятностью находит там новую интересную задачу про группы, а с вероятностью интересную задачку про кольца. С вероятностью новых задач на форуме не окажется. Пусть — это минимальное число дней, за которые у Алёны появится хотя бы одна новая задача про группы и хотя бы одна про кольца. Найдите распределение случайной величины . В ответе должны участвовать только компактные выражения (не содержащие знаков суммирования, многоточий и пр.).
Решение
Нам нужно найти . Для этого надо понять на пальцах, в каком случае . Первый случай — когда в каждый из предыдущих дней либо не было задач, либо были только про группы, а в -ый попалась задача про кольца. Второй случай — когда в каждый из предыдущих дней либо не было задач, либо были только про кольца, а в -ый попалась задача про группы. На самом деле мы оба раза учли не подходящий случай, когда все предыдущие дней задач не было вообще. С поправкой на это ответ будет таким:
Задача 4
Дан массив вещественных чисел, отсортированный по возрастанию, а также числа , , . Предложите алгоритм, строящий массив , состоящий из чисел , где , также отсортированный по возрастанию. Ограничение по времени — , по дополнительной памяти — .
Решение
, .
Сначала предположим, что .
Изобразим нашу функцию.
Заметим, что:
1. после применения порядок остаётся прежним.
2. после применения порядок будет обратным.
То есть для «правой» части после применения к каждому значению функции подпоследовательность остаётся правильно отсортированной, для левой части она становится отсортированной в обратном порядке.
Тогда бинпоиском за найдём место в , в котором массив делится на эти самые доли. Сделаем reverse левой части. Применим ко всем элементам функцию . Получили 2 отсортированных массива. С помощью процедуры merge за по времени и по памяти получим целиком отсортированный массив.
В случае решим задачу для , а затем сделаем reverse всего массива и домножим каждое значение на -1. Получим правильный результат.
В случае порядок зависит от знака .
1.
2.
И построение в этом случае сводится к применению функции ко всем значениям. Только в случае за надо ещё сделать reverse. В случае когда порядок уже правильный.
Сначала предположим, что .
Изобразим нашу функцию.
Заметим, что:
1. после применения порядок остаётся прежним.
2. после применения порядок будет обратным.
То есть для «правой» части после применения к каждому значению функции подпоследовательность остаётся правильно отсортированной, для левой части она становится отсортированной в обратном порядке.
Тогда бинпоиском за найдём место в , в котором массив делится на эти самые доли. Сделаем reverse левой части. Применим ко всем элементам функцию . Получили 2 отсортированных массива. С помощью процедуры merge за по времени и по памяти получим целиком отсортированный массив.
В случае решим задачу для , а затем сделаем reverse всего массива и домножим каждое значение на -1. Получим правильный результат.
В случае порядок зависит от знака .
1.
2.
И построение в этом случае сводится к применению функции ко всем значениям. Только в случае за надо ещё сделать reverse. В случае когда порядок уже правильный.
Задача 5
Вещественнозначная функция определена на отрезке и дифференцируема на нём. Докажите, что найдётся точка , для которой
Решение
Давайте докажем от противного. Пусть .
Сначала посмотрим, что будет происходить при равенстве:
Обозначим эту функцию как . Заметим, что . То есть мы пользуемся тем, что функция растёт не менее быстро, получаем, что и разница с изначальной точкой будет не меньше, чем у .
Функция у нас имеет константу . Примем значение этой константы таким, что . Тогда:
Мы знаем, что . Тогда на существует хотя бы одна точка такая, что (потому что шаг ). В этой точке . При этом мы знаем, что .
Получили, что в какой-то из точек функция уходит на бесконечность. А значит функция терпит разрыв, то есть не является непрерывной, а это дано нам в условии. Получили противоречие.
Сначала посмотрим, что будет происходить при равенстве:
Обозначим эту функцию как . Заметим, что . То есть мы пользуемся тем, что функция растёт не менее быстро, получаем, что и разница с изначальной точкой будет не меньше, чем у .
Функция у нас имеет константу . Примем значение этой константы таким, что . Тогда:
Мы знаем, что . Тогда на существует хотя бы одна точка такая, что (потому что шаг ). В этой точке . При этом мы знаем, что .
Получили, что в какой-то из точек функция уходит на бесконечность. А значит функция терпит разрыв, то есть не является непрерывной, а это дано нам в условии. Получили противоречие.
Задача 6
Квадратная вещественная матрица такова, что , где — многочлен с ненулевым свободным членом. Докажите, что обратима. Верно ли, что для любого оператора найдётся многочлен и некоторый базис, в котором матрица удовлетворяет условию ?
Решение
В начале, покажем, что , распишем подробно:
Отсюда можно получить, что .
1. Будем доказывать от противного. Пусть матрица необратима. Тогда существует вектор такой, что . Тогда ещё можно сказать, что . Теперь распишем это:
Теперь пользуемся тем, что :
Но мы знаем, что . Получили противоречие.
2. Рассмотрим линейный оператор с матрицей в стандартном базисе.
Тогда в любом другом базисе матрица будет иметь вид , где — матрица перехода.
Заметим, что , значит . Тогда .
Пусть . Так как все степени выше 1 обнуляются, .
При этом , так как иначе, пользуясь первым пунктом, можем получить, что матрица обратима, а это не так (т.к. ).
Вспомним, что .
Распишем: .
Теперь рассмотрим несколько случаев:
1. :
Подставим в другое место:
Наша матрица размерности всего 2, поэтому вполне можем расписать поэлементно:
Но мы знаем что . Распишем определитель:
.
Получили противоречие. Матрица оператора в стандартном базисе ненулевая, она не может быть нулевой в другом базисе.
2. :
Тогда после подстановки получаем . Тогда .
При этом
И снова получаем противоречие.
3. .
Здесь тогда тоже получаем, что .
Значит нет многочлена и базиса в котором матрица оператора представима, как . Что и требовалось доказать.
Отсюда можно получить, что .
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 или больше. Что и требовалось доказать.
Выберем 2 самые удалённые друг от друга вершины и и 3 произвольные. По условию дано, что любые 5 вершин составляют цикл. Значит есть и цикл, состоящий из этих 5 вершин. В этом цикле путь от до будет максимум 2 (видно на картинке). Значит .
Теперь зафиксируем произвольную вершину . Мы уже сделали вывод, что до любой другой вершины графа расстояние от равно либо 1, либо 2. Покажем, что на «втором уровне» не больше вершин:
Будем доказывать от противного. Пусть есть вершины . Возьмём ещё одну произвольную вершину . Снова, эти вершины составляют цикл. Но тогда, как бы мы ни разместили вершины в этом цикле, расстояние от до хотя бы одной из вершин , или будет равно 1, получили противоречие.
Получили, , то есть каждая вершина имеет степень не меньше .
Теперь попробуем с этой информацией найти клику (вершины, попарно соединённые рёбрами — то, что требуется в условии) длины 10. Найти клику размера 10 в графе — это то же самое, что найти независимое множество (то есть вершины, между которыми вообще нет рёбер) того же размера 10 в обратном графе .
Рассмотрим . Если в изначальном графе у нас степень вершины , то в обратном .
Тогда обратный граф состоит из набора «цепей» (1) и «циклов» (2). Другие структуры невозможны из-за жёсткого ограничения .
В компонентах вида (1) можно найти независимое множество размера , вида (2) — .
Пусть — общее количество компонент в обратном графе, а — количество «цепочек». Тогда размер максимального независимого множества будет равен:
Понятно, что это число будет минимальным, если мы по возможности будем округлять вниз, при этом с наибольшими потерями. Этого можно добиться, например, взяв 10 компонент размера 3. Тогда получим нижнюю оценку.
То есть мы показали, что в обратном графе максимальное независимое множество имеет размер 10 или больше, то есть в графе существует клика размера 10 или больше. Что и требовалось доказать.
Задача 8
Найдите предел
Решение
Здесь нужно по виду формулы догадаться о теории вероятностей.
Введём случайную величину:
Пусть монетка неправильная — орёл выпадает с вероятностью .
Тогда это в точности значение под знаком суммирования:
— это количество возможных размещений орлов (ещё 1 выпадает в конце).
— это вероятность выпадения орлов на выбранных позициях.
— это вероятность выпадения решек на оставшихся позициях.
Тогда наш предел превращается в
Заметим, что вероятность события можно интерпретировать по-другому. Это вероятность того, что за бросков выпадет орлов.
Введём новую случайную величину:
При этом величину можно представить как сумму элементарных:
Тогда
Применим центральную предельную теорему к . Получим:
Вспоминаем, что у нас нормальное распределение симметрично относительно матожидания и получаем итоговый ответ:
Введём случайную величину:
Пусть монетка неправильная — орёл выпадает с вероятностью .
Тогда это в точности значение под знаком суммирования:
— это количество возможных размещений орлов (ещё 1 выпадает в конце).
— это вероятность выпадения орлов на выбранных позициях.
— это вероятность выпадения решек на оставшихся позициях.
Тогда наш предел превращается в
Заметим, что вероятность события можно интерпретировать по-другому. Это вероятность того, что за бросков выпадет орлов.
Введём новую случайную величину:
При этом величину можно представить как сумму элементарных:
Тогда
Применим центральную предельную теорему к . Получим:
Вспоминаем, что у нас нормальное распределение симметрично относительно матожидания и получаем итоговый ответ:
Заключение
В целом экзамен довольно сложный. Мой знакомый пожаловался, что подготовиться непросто. Это действительно так — нужно не только знать обширную математическую теорию, но и иметь навык решения олимпиадных задачек, в ШАДе дают именно такие. Поэтому для подготовки нужно много тренироваться, вспоминать теорию и набивать руку.
Если у вас есть другие идеи решения задач или какие-то замечания, смело пишите мне в телеграм @Azatik1000. Всегда рад ответить!
Азат Калмыков, куратор ШАД Helper
Только зарегистрированные пользователи могут участвовать в опросе. Войдите, пожалуйста.
Какое задание показалось вам наиболее интересным?
-
0,0%10
-
0,0%20
-
0,0%30
-
0,0%40
-
0,0%50
-
0,0%60
-
60,0%73
-
40,0%82