Полный разбор экзамена в ШАД 2024 года09.09.2024 11:45

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

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

Задача 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

Решение

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

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

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

$\mathbb{P}(C=k)=\frac{k^2}{100}I(0\le k \le 10) + I(k>10)» src=«https://habrastorage.org/getpro/habr/formulas/4/47/479/47938a0c9e8e94790051aae65bbed817.svg» /> Процент решённых задач группой из <img alt=$ ребят распределён равномерно на отрезке:

$[\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)» src=«https://habrastorage.org/getpro/habr/upload_files/02e/385/6d1/02e3856d12bad1d2f075b2ea8640af11.svg» />на трех разных промежутках<ol><li><img alt=$

$f(k)=\frac{1}{2}(1+\frac{k}{8})-\frac{k^2}{100}$ .

Перед нами парабола с ветвями вниз. Ее максимум в вершине, вершина находится где-то между 3 и 4. Непосредственно проверим, что f(3)>f (4)» src=«https://habrastorage.org/getpro/habr/formulas/d/dc/dcd/dcd1ca904c63ad11e930e18b863e3d8c.svg» />. Зная, что парабола с ветвями вниз до вершины возрастает, а после вершины убываем, заключаем, что на этом промежутке максимум достигается в k = 3.</li><li><img alt=

$f(k)=\frac{1}{2}(1+\frac{5}{8})-\frac{k^2}{100}$ .

Непосредственно проверяем f(3)>f (6)» src=«https://habrastorage.org/getpro/habr/formulas/6/65/654/654a39934611797b7d7158eb07b04f87.svg» />. Дальше рассуждаем как в прошлом пункте и приходим к выводу, что пока оптимальное значение k = 3. </li><li><img alt=

$f(k)=\frac{1}{2}(1+\frac{5}{8})-1<f(3)$ .

То есть оптимальное значение при k = 3.

Ответ: f(3)

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

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

$\lim_{x\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» src=«https://habrastorage.org/getpro/habr/formulas/6/6c/6c7/6c7f59197951a9a01d158506b85cde2f.svg» /> а Артём, если меньше, иначе просто происходит переход к следующему раунду. Здесь <img src=$

и $\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}$ через скалярное произведение и применить неравенство Коши-Буняковского-Шварца (КБШ) для оценки сверху. Далее остается лишь показать, что оценка достигается

Решение

Задача 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» src=«https://habrastorage.org/getpro/habr/formulas/6/6c/6c8/6c8266300bfbfb3d0f0931293f7bfd70.svg» />. В следующей строке идет натуральное число <img alt=$ $(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)$ — города, соединяемые дорогой, и длина дороги соответственно.

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

В единственной строке выведите целое число, равное количеству дорог, каждая из которых обязательно сохранится в игре.

Подсказка

Попробуйте алгоритм Флойда или Дейкстры

Решение

Воспользуемся алгоритмом Дейкстры