Полный разбор экзамена в ШАД 2024 года / Хабр

Перед тем, как смотреть решение обязательно попробуйте одолеть самостоятельно!

Автор решений: телеграм канал "Поступашки — ШАД, Стажировки и Магистратура".

Задача 1 (Линейность)

Рассмотрим линейное пространство многочленов степени не выше 3 над полем $\mathbb{R}.$ На нём задано отображение

$f(g(x))=\text{НОД}(x^2-1, g(x))+g'(x)$

где $\text{НОД}(x^2-1, g(x))$ - многочлен наивысшей степе��и, являющийся одновременно делителем и x^2-1 , и g(x) , у которого старший коэффициент совпадает со старшим коэффициентом g(x) . Дополнительно доопределим $\text{НОД}(x^2-1, 0)=0$ .

Пример: $\text{НОД}(x^2-1, 2)=2$

Является ли данное отображение линейным?

Подсказка

Вспомните определение линейного отображения L и проверьте его:

Для любых элементов векторного пространства a и b выполнено:

L(a + b) = L(a) + L(b)
L(ka) = kL(a), для любого скаляра k

Решение

По определению отображение называется линейным, если $1. L(a+b)=L(a)+L(b), \quad 2. L(\lambda a)=\lambda L(a)$ .

Из условия f(x+1)=x+1+1=x+2 . Представим x+1 в виде линейной комбинации двух других многочленов. $x+1=\alpha (x+2)+\beta (x-2)$ , откуда

$\begin{cases} \alpha + \beta = 1 \\ 2\alpha - 2\beta = 1 \end{cases}$

то есть $(\alpha, \beta) = (\frac{3}{4}, \frac{1}{4})$ .

По аналогии .

Предположив возможность линейности получим -

$f(x+1)=f(\alpha (x+2)+\frac{1}{4}(x-2))=\frac{3}{4}f(x+2)+\frac{1}{4}(x-2)=2$ , а значит

многочлены и x+2 - равны, что даёт противоречие.

Откуда

Ответ: не является линейным.

Задача 2 (Читеры)

Честные и принципиальные абитуриенты никогда не списывают чужие решения. Но иногда в группе из друзей, где все друг друга знают, образуется сговор.

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

$\mathbb{P}(C=k)=\frac{k^2}{100}I(0\le k \le 10) + I(k>10)$

Процент решённых задач группой из ребят распределён равномерно на отрезке:

$[\frac{min(k,5)}{8}, 1]$

Найдите оптимальный размер группы читеров. Это аргмаксимум задачи максимизации разности матожидания процента решённых задач и вероятности для группы быть пойманной.

Подсказка

Попробуйте задать функцию кусочно и исследовать ее на каждом промежутке.

Решение

Рассмотрим функцию

$f(k)=\frac{1}{2}(1+\frac{min(k,5)}{8})-\frac{k^2}{100}I(0\le k \le 10) - I(k>10)$

на трех разных промежутках

$0 \le k \le 5$
$f(k)=\frac{1}{2}(1+\frac{k}{8})-\frac{k^2}{100}$ .
Перед нами парабола с ветвями вниз. Ее максимум в вершине, вершина находится где-то между 3 и 4. Непосредственно проверим, что . Зная, что парабола с ветвями вниз до вершины возрастает, а после вершины убываем, заключаем, что на этом промежутке максимум достигается в k = 3.
$6 \le k \le 10$
$f(k)=\frac{1}{2}(1+\frac{5}{8})-\frac{k^2}{100}$ .
Непосредственно проверяем . Дальше рассуждаем как в прошлом пункте и приходим к выводу, что пока оптимальное значение k = 3.
$11 \le k$
$f(k)=\frac{1}{2}(1+\frac{5}{8})-1<f(3)$ .
То есть оптимальное значение при k = 3.
Ответ:

Задача 3 (Эквивалентно)

Найдите 3 константы $m,n \in \mathbb{Z}, C \in \mathbb{R}:$

$\lim_{t\to\infty} \frac{ \int_{0}^{1} sin(tx)ln(x) dx }{Ct^{n}(ln(t))^{m}} = 1$

В качестве ответа введите сумму модулей найденных констант.

Подсказка

Попробуйте найти асимптотику интеграла в числителе

Решение

Попробуем найти асимптотику интеграла в числителе

Задача 4 (Координаты в квадрате)

Мальчик Влад от скуки любит рисовать на клетчатой бумаге. Однажды он нарисовал квадрат $n \times n$ , границы которого проходят по сторонам клеток. Далее он ввел систему координат внутри квадрата: левый нижний квадратик $1\times 1$ получил координаты (1,1) , а правый верхний - (n,n) . Первая координата соответствует смещению по горизонтальной оси, а вторая - по вертикальной.

Затем он нарисовал квадрат $(n-1)\times (n-1)$ также по сторонам клеток, не выходя за пределы исходного квадрата. Затем он нарисовал квадрат $(n-2)\times (n-2)$ по сторонам клеток, не выходя за пределы предыдущего квадрата $1\times 1$ , и оказалось, что он совпадает с клеткой исходного квадрата с координатами (x,y) .

Когда это увидела мама мальчика, она заинтересовалась вопросом: а сколько существует различных последовательностей квадратов, удовлетворяющих вышеописанным свойствам?

Подсказка

Попробуйте рассмотреть частные случаи. Например, мыле значения n = 1, 2, 3, ....

Также для вдохновения можно начать с одномерной задачи.

Решение

Попробуем начать с одномерного аналога.

Из рисунка видно, что нам нужно удалить x -1 квадратиков слева и n - x квадратиков справа. Это можно сделать ровно $C_{n-1}^{x-1}$ способов.

Теперь подумаем, как подойти к изначальной двумерной задачи. На самом деле ее можно свести к "двум одномерным задачам"! Чтобы добраться до квадратика с координатами (x, x), нужно удалить квадратики по оси х и по оси y (вместе с ними буду удаляться и "полоски квадратиков").

В итоге по комбинаторного правила произведения получаем ответ $C_{n-1}^{x-1}\cdot C_{n-1}^{y-1}$

Задача 5 (Давай поиграем)

Рассмотрим случайный многомерный нормальный вектор $\psi$ в $\mathbb{R}^{n}$ с нулевым средним и единичной матрицей дисперсии. Артём и Лёша играют в игру с нулевой суммой (число очков у одного игрока всегда равно минус числу очков у другого). Каждый игрок зафиксировал до начала игры по одному вектору (Артём) и (Лёша) в $\mathbb{R}^{n}$ . В начале игры у каждого 0 очков.

Лёша получает очко в раунде , если $sign\langle \psi_k, a \rangle sign\langle \psi_k, l \rangle >0$

а Артём, если меньше, иначе просто происходит переход к следующему раунду.

Здесь

и $\langle \bullet, \bullet \rangle$ - стандартное скалярное произведение в $\mathbb{R}^{n}$ .

$\{\psi_i\}_{i=1}^{\infty}$ - реализации случайного вектора $\psi$ , полученные независимо друг от друга.

В каждом раунде рассмотрим число очков у Артёма, делённое на . К чему оно стремится при $k \mapsto \infty$ ? В качестве ответа укажите искомую величину при a=(1,2,3) и l=(1,0,1) .

Подсказка

Попробуйте просто "поиграть" в такую игру, рассмотреть случаи. Если нас просят найти предел суммы случайных величин, то здесь ��корее всего придется вспомнить про предельные теоремы, например, закон больших чисел.

Решение

Попробуем рассмотреть случаи, нарисуем рисунок

Голубая область - та область, при попадании реализации вектора очко достается Леше. Розовая область - та область, при попадании реализации вектора очко достается Артему. — Голубая область - та область, при попадании реализации вектора $\psi_k$ очко достается Леше. Розовая область - та область, при попадании реализации вектора $\psi_k$ очко достается Артему.

Посчитаем предел, воспользовавшись законом больших чисел:

$\frac{\xi_1 + \xi_2 +\ldots +\xi_k}{k} \mapsto M[\frac{\xi_1 + \xi_2 +\ldots +\xi_k}{k}]$ (*)

в каждом раунде $\xi_k$ - распределена независимо, откуда предел стремится к матожиданию от среднего арифметического. Воспользуемся линейностью мат ожидания и посчитаем мат ожидание каждой случайной величины в отдельности:

$M[\xi_i]=P(+)-P(-)$ - для Артёма, где P(+) - вероятность присуждение очка Артёму, и P(-) - Лёше.

$M[\xi_i]=P(+)-P(-)=\frac{2(\pi -x)-2x}{2\pi}=\frac{\pi -2x}{\pi}$

То есть все мат ожидания равны и ответ $\frac{\pi -2x}{\pi}$

Случай, когда угол между вектором l и a тупой аналогичен и оставляется в качестве упражнения читателю.

Задача 6 (Алгебраично)

Пусть заданы матрицы $A \in \mathbb{R}^{m\times r}, C \in \mathbb{R}^{n\times m}$ . Для и выполнены следующие свойства: $A^{T}A=I$ и $B^{T}B=I$ .

Среди матриц $X \in \mathbb{R}^{n\times m}$ , таких что $Im(X) \subset Im(X^{T}), Im(X^T) \subset Im(B)$ ,

$\sum_{i,j} X_{i,j}^2 = 1$ ,

найдите такую, что $\sum_{i,j} X_{i,j}С_{i,j}$ - максимально.

$\forall M \in \mathbb{R}^{n \times m}$ , $Im(M) := \{Mx| x\in \mathbb{R}^{m \times 1}\}$

Решите задачу в общем виде, а в качестве ответа введите сумму следа и определителя искомой матрицы при n=r=m=4 , если A,B,C - единичные.

Подсказка

Попробуйте ввести базис и расписать $\sum_{i,j} X_{i,j}С_{i,j}$ через скалярное произведение и применить неравенство Коши-Буняковского-Шварца (КБШ) для оценки сверху. Далее остается лишь показать, что оценка достигается

Решение

Первое, что можно понять - образ лежит в образе . $x: Im(B) \to Im(A)$ , по

условию dim(Im(A))=r , $r \le rk(A^{T}A) \le rk(A) \le r$ .

Выберем базис - $Im(B) = <e_1, e_2, \ldots, e_r>$ .

Откуда $\sum x_{i,j}^2 = \sum (xe_i, xe_i)$ .

Тогда, вспоминая неравенство Коши-Буняквоского-Шварца, получаем оценки

$\sum x_{i,j}^2c_{i,j} = \sum (xe_i, proj_{Im(A)}(ce_i) \le \sum |xe_i||ce_i|$ $|xe_i||ce_i| \le \sqrt{\sum |xe_i|^2}\sqrt{\sum |ce_i|^2}\le \sqrt{\sum ce_i}$

Где $proj_{Im(A)}(ce_i)$ - проекция вектора на пространство .

Оценка достигается при $x=\frac{proj_{A}c}{\sqrt{\sum (proj_{A}ce_i) ^2}}$

Проекция же матрицы С - будет в нашем случае единичной.

Еще одно решение этой задачи можно посмотреть здесь

Задача 7 (Скоростной закон)

В моделировании движущихся объектов есть такая сущность как скоростной закон. Он представляет из себя последовательный набор полуинтервалов [l_i, r_i) , на которых объект движется вдоль прямой с ускорением $a_i \ge 0$ .

Экспериментаторам хочется узнать, в какое время объект окажется на расстоянии .

Так как интересных моментов времени много, вам предстоит помочь им.

Напишите программу, которая по данным скоростной закону и дистанциям найдет необходимые времена .

Изначально объект находится в положении x=0 с нулевой начальной скоростью.

Формат ввода:

В первой строке идет натуральное число $N(1 \le N \le 10^5)$ - число интервалов в скоростном законе.

Далее в строках идут по три целых числа l_i, r_i, a_i . Гарантируется, что $0\le l_i < r_i = l_{i+1} \le 10^7$ и $0\le a_i \le 10^2, a_1>0$ .

В следующей строке идет натуральное число $(1 \le Q \le 10^5)$ - число запросов времени по дистанции.

В следующих строках идет по одному целому числу $d_i (0 < d_i \le 10^18)$ - запросы дистанции, для которых надо ответить время.

Гарантируется, что запросы дистанции таковы, что они достижимы к моменту $r_{N}$ , а времена будут целочисленными.

Подсказка

Попробуйте воспользоваться формулой $S = vt +\frac{at^2}{2}$

Решение

Задача 8 (Важные дороги)

В одной из игр карта из городов, пронумерованных от до . Стартовым городом является город 1, назовем его столицей. Между некоторыми городами на карте проложены дороги, движение по которым разрешено в обоих направлениях. Каждая дорога имеет некоторую положительную длину. Дороги не обязательно проложены по прямой, поэтому перемещения по дорогам они пересекаются только в городах.

Отметим, что не все дороги нанесены на карту, поэтому некоторые просто перечислены на специальных дополнительных карточках в игре (автору игры пришлось так сделать, чтобы сохранить требования пересечения дорог только в городах). Система дорог спланирована таким образом, что из каждого города можно попасть в каждый, двигаясь по дорогам. Никакая дорога не соединяет город с самим собой.

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

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

Формат ввода:

В первой строке входных данных записаны два целых числа и $(2 \le n \le 100, 1\le m \le 1000)$ - количество городов и дорог в игре.

Далее в строках записаны описания дорог по одной в строке. Каждая из строк содержит три целых числа x_i, y_i и l_i $(1 \le x_i, y_i \le n, x_i \ne y_i, 1 \le l_i \le 10^6)$ - города, соединяемые дорогой, и длина дороги соответственно.