09.09.2024 08:40
postupashki 6 4100 Источник

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

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

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

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

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 выполнено:

  1. L(a + b) = L(a) + L(b)

  2. 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+2)=1+1=2, f(x-2)=1+1=2.

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

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

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

Откуда

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

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

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

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

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

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

[\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)

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

  1. 0 \le k \le 5

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

    Перед нами парабола с ветвями вниз. Ее максимум в вершине, вершина находится где-то между 3 и 4. Непосредственно проверим, что f(3)>f(4). Зная, что парабола с ветвями вниз до вершины возрастает, а после вершины убываем, заключаем, что на этом промежутке максимум достигается в k = 3.

  2. 6 \le k \le 10

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

    Непосредственно проверяем f(3)>f(6). Дальше рассуждаем как в прошлом пункте и приходим к выводу, что пока оптимальное значение k = 3.

  3. 11 \le k

    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_{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} с нулевым средним и единичной матрицей дисперсии. Артём и Лёша играют в игру с нулевой суммой (число очков у одного игрока всегда равно минус числу очков у другого). Каждый игрок зафиксировал до начала игры по одному вектору a (Артём) и l (Лёша) в \mathbb{R}^{n}. В начале игры у каждого 0 очков.

Лёша получает очко в раунде k, если 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 рассмотрим число очков у Артёма, делённое на k. К чему оно стремится при 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 и B выполнены следующие свойства: 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 лежит в образе A. 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)- проекция вектора сe_iна пространство Im(A).

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

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

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

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

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

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

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

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

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

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

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

Далее в N строках идут по три целых числа 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.

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

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

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

Подсказка

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

Решение

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

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

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

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

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

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

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

Далее в m строках записаны описания дорог по одной в строке. Каждая из m строк содержит три целых числа 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) - города, соединяемые дорогой, и длина дороги соответственно.

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

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

Подсказка

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

Решение

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

Комментарии (6)


  1. belch84
    09.09.2024 10:09
    #27266374
    +4

    Мне одному кажется, что что-то в этой записи не так? И это не только запятая в подынтегральном выражении. Как можно брать предел по переменной, по которой происходит интегрирование? Глубоко не разбирался, но должен или предел быть для t, или интегрирование должно вестись по dt

    Ну, по смыслу скорее первое ...


    1. Imaginarium
      09.09.2024 10:09
      #27269950
      +1

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


  1. webhamster
    09.09.2024 10:09
    #27267292
    +3

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

    • Что подразумевается под полем R? Это просто некое абстрактное поле или имеется в виду множество всех действительных чисел?

    • Почему в определении не сказано, что g(x) - это многочлен степени не выше 3? Косвенно об этом можно догадаться, но почему в "дано" об этом явно не сказано?

    • Что такое g'(x)? Это какой-то другой многочлен? А это вообще многочлен? Для g со штрихом известна зависимость от x? Может быть это производная многочлена g(x)? Может быть что-нибудь еще?

    • Почему на вопрос "Является ли данное отображение линейным?" в скрытом тексте написан ответ: 2024?

    В очередной раз убеждаюсь, что математика - неизучаемая наука.


    1. Seraphimt
      09.09.2024 10:09
      #27267354
      +3

      1) Жирное R - стандартное обозначение вещественных чисел. Если вы этого не знаете, то извините, такие задачки явно не вашу уровень.
      2) Как это не сказано?

      На нём задано отображение

      3) Это производная, опять таки стандартнейшее обозначение.
      4) Похоже на косяк автора, при чём тут математика?


  1. wolkodav96
    09.09.2024 10:09
    #27269816
    +1

    А почему во 2 задаче так странно:

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

    Не очевидно, что надо такую функцию максимизировать, разве не логичнее считать

    \frac{100-k^2}{100} \; \frac{min(k,5)+8}{2} \rightarrow \max_{k}; k\in0...10

    т.е. максимизировать ожидаемую оценку? разница между % правильных ответов и вероятностью обнаружения это какая-то стремная величина безразмерная.


  1. kovserg
    09.09.2024 10:09
    #27272424

    Напишите функцию среднего арифметического для трёх чиcел на C++ без UB:

    typedef long long T;
T mean3(T a,T b,T c); // mean3=(a+b+c)/3