15.10.2021 13:26
rk-helper 3 4300 Источник

Задачи прошлых лет, отсортированные по сложности и предметам можно посмотреть на сайте: https://shadhelper.notion.site

Автор решения: Лыков Александр, кандидат физико-математических наук.

Задача 1

Пусть A — квадратная матрица n \times n. Докажите, что n-\operatorname{rk} A \geqslant \operatorname{rk} A-\operatorname{rk} A^{2}

Подсказка

Использовать связь ранга матрицы с образом соответствующего линейного оператора.

Решение

  • Решение

    Обозначим \mathcal{A} оператор с матрицей A. Напомним, что \operatorname{Im}(\mathcal{A}) обозначает образ оператора, \operatorname{Ker}(\mathcal{A}) — ядро.

    Определим оператор \tilde{\mathcal{A}}, действующий на \operatorname{Im}(\mathcal{A}) как ограничение оператора \mathcal{A} на это подпространство: \tilde{\mathcal{A}}x=\mathcal{A}x,\ x\in \mathrm{Im}(\mathcal{A}). Легко видеть, что справедливы равенства:

    \operatorname{Im}(\tilde{\mathcal{A}})=\operatorname{Im}\left(\mathcal{A}^{2}\right), \quad \operatorname{Ker}(\tilde{\mathcal{A}})=\operatorname{Ker}(\mathcal{A}) \cap \operatorname{Im}(\mathcal{A})

    Поэтому получаем:

    \operatorname{rk} A-\operatorname{rk} A^{2}=\operatorname{dim}(\operatorname{Im}(\mathcal{A}))-\operatorname{dim}(\operatorname{Im}(\tilde{\mathcal{A}}))=\operatorname{dim}(\operatorname{Ker}(\tilde{\mathcal{A}})) \leqslant \operatorname{dim}(\operatorname{Ker}(\mathcal{A}))=n-\operatorname{rk} A

    Мы использовали то, что для любого линейного оператора \mathcal{L} действующего на векторном пространстве V справедлива формула

    \operatorname{dim}(\operatorname{Im}(\mathcal{L}))+\operatorname{dim}(\operatorname{Ker}(\mathcal{L}))=\operatorname{dim} V

Задача 2

Сколькими способами n различных четных чисел и n различных нечетных чисел можно записать в таблицу 2\times nтаким образом, чтобы нечетное число никогда не стояло под четным? Ответ должен содержать не более одной суммы.

Подсказка

Разбить все столбцы на группы по принципу того, какое число по чётности стоит снизу, какое сверху.

Решение

  • Решение

    • Разобьём все столбцы таблицы на три группы:

      1. \text{НН: нечётная стоит под нечётной}, 2. \text{ЧН: чётная стоит под нечётной}, 3. \text{ЧЧ: чётная стоит под чётной.}

      Предположим, что в группе НН в первой строке k элементов. Тогда во второй строке этой группы также k элементов, а количество элементов в верхней строке в группе ЧН равно n-2k. Тем самым имеем следующую картинку:

      Число способов выбрать элементы для группы НН равно C_n^kC_{n-k}^k: сначала выбираем C_{n}^k способами нечётные числа на верхние позиции, затем на нижние. Число способов выбрать чётные элементы (нечётные элементы уже определены на предыдущем шаге) для группы ЧН равно C_{n}^{n-2k}. Элементы в верхней строке для группы ЧЧ можно выбрать C_{2k}^k способами, на нижние позиции пойдут оставшиеся чётные элементы. После того как числа распределены по группам нам нужно выбрать места в таблице, где будут располагаться группы. Например, места с 1 по 10 уходят для группы НН, с 10 по 20 для группы ЧН , и с 20 по nдля группы ЧЧ. Это можно сделать C_n^k C_{n-k}^k способами - выбираем места для группы НН и затем для ЧЧ, для группы ЧН оставшиеся. Далее нужно учесть, что мы можем переставлять числа внутри группы, на одной строке.

      Это даст нам ещё (k!)^2 ((n-2k)!)^2 (k!)^2вариантов. Окончательно получаем ответ:

      S = \sum_{0\leqslant k \leqslant \frac{n}{2}} C_{n}^k C_{n-k}^k C_{n}^{n-2k} C_{2k}^k C_n^k C_{n-k}^k (k!)^2 ((n-2k)!)^2 (k!)^2

Задача 3

На станцию приходят в случайное время две электрички. Времена их приходов независимы и имеют экспоненциальное распределение с плотностью e^{-x} при x>0. Студент приходит на станцию в момент времени 2. Найдите:

a) вероятность того, что он сможет уехать хотя бы на одной электричке;

б) математическое ожидание времени ожидания студентом ближайшей электрички (считаем, что время ожидания равно нулю, если студент опоздал на обе электрички).

Подсказки

Обозначим T_1и T_2 времена прихода первой и второй электричек соответственно. Переформулировать вопрос задачи в терминах T_1,T_2

Решение

  • Решение

    Обозначим T_1 и T_2 времена прихода первой и второй электричек соответственно. Событие состоящее в том, что студент сможет уехать хотя бы на одной электричке может быть записано в следующем виде:

    \max\{T_1,T_2\}>2.

    Поэтому вероятность из пункта а) вычисляется следующим образом:

    P(\text{студент сможет уехать хотя бы на одной электричке}) == P(\max\{T_1,T_2\}>2) =1 - P(\max\{T_1,T_2\}\leqslant 2) = = 1- P(T_1 \leqslant 2\ \text{и}\ T_2\leqslant 2) =^{(*)}1 - (P(T_1 \leqslant 2))^2 =1 - (1-e^{-2})^2.

    В равенстве ^{(*)} мы воспользовались независимостью случайных величин T_1 и T_2

    Решим пункт б). Обозначим \tau время ожидания электрички. Имеем равенство:

    \tau = \begin{cases} 0,& \max\{T_1,T_2\}<2 ,\\ \max\{T_1,T_2\}-2,& \min\{T_1,T_2\}<2\leqslant\max\{T_1,T_2\},\\ \min\{T_1,T_2\} - 2,& 2\leqslant\min\{T_1,T_2\} \end{cases}

    Для положительного x вычислим

    P(\tau>x) = P(\min\{T_1,T_2\} - 2> x)+ + P(\max\{T_1,T_2\}-2>x,\ \min\{T_1,T_2\}<2) = =P(T_1>x+2,\ T_2>x+2)+ P(T_1<2,\ T_2>x+2)+ +P(T_1>x+2,\ T_2<2) =e^{-2(x+2)} + 2e^{-(x+2)}(1-e^{-2}).

    Заметим, что случайная величина не является абсолютно непрерывной, так как имеет атом в нуле P(\tau=0)>0. Тем не менее для её математического ожидания справедлива формула:

    E\tau = \int_{0}^{+\infty} x \frac{d}{dx} (1 - P(\tau>x)) dx = 2\int_{0}^{+\infty} x e^{-2(x+2)}dx + + 2(1-e^{-2}) \int_{0}^{+\infty} x e^{-(x+2)}dx =\frac{1}{2}e^{-4} + 2(1-e^{-2})e^{-2}.

    В последнем равенстве интеграл вычисляется по частям, либо на основе формулы для математического ожидания экспоненциального распределения с параметром \lambda:

    EX = \lambda \int_{0}^{+\infty} x e^{-\lambda x} dx = \frac{1}{\lambda},

    где X экспоненциально распределён с параметром \lambda>0.

Задача 4

Верно ли, что всякая нечетная непрерывная функция, удовлетворяющая условию f(2x) = 2f(x), линейна.

Подсказка

  • Подсказки

    Придумать чётную функцию g(x) такую, что g(2x) = g(x).

Решение

  • Решение

    Неверно. Пример функции

    f(x) = x \cos(2\pi \log_2(|x|))

Задача 5

Пусть A и B — ортогональные матрицы (не ортогональные друг другу, а просто ортогональные!). Докажите, что

\det(A^TB - B^TA) =\det(A+B)\cdot \det(A-B)
Подсказка

Использовать равенство \det A^T = \det A

Решение

  • Решение

    Имеем равенства:

    \det(A+B)\cdot \det(A-B) = \det(A-B)\cdot \det(A+B) = = \det(A^T-B^T)\cdot \det(A+B) ==\det((A^T-B^T)(A+B)) = \det(A^TA+A^TB-B^TA-B^TB) == \det(A^TB - B^TA).

    В последнем равенстве мы использовали то, что для ортогональной матрицы X выполняется соотношение X^TX = E, где E — единичная матрица. Также мы воспользовались известными формулами :

    \det A^T = \det A,\quad \det(AB) = \det(BA).

Задача 6

Назовем элемент прямоугольной матрицы седлом, если он является наибольшим в своей строке и наименьшим в своем столбце или наоборот. Придумайте алгоритм, за O(nm)операций находящий все седла в матрице A[1..n][1..m], использующий не более O(n+m)памяти и не более 1 раза обращающийся к каждому элементу A (можете считать, что элемент A[i][j]превращается в NaN сразу после вызова A[i][j]Считайте, что все элементы матрицы различны

Подсказка

Подумать как найти максимальный элемент в iстроке и минимальный jстолбце.

Решение

  • Решение

    Будем обходить все элементы матрицы по очереди и будем хранить максимальный и минимальный элемент для каждой строки и для каждого столбца:

    \text{1. } M^{i} \text{максимальный элемент в } i-ом \text{ столбце}\text{2. } m^{i} \text{ минимальный элемент в }i-\text{ом столбце,}\text{3. }M_{i} \text{ максимальный элемент в }i\text{-ой строке}\text{4. } m_{i} \text{ минимальный элемент в }i \text{-ой строке. }

    Для этого нам понадобится 2(n+m)+1 памяти и 4nm сравнений. Заметим, что элемент x является седлом тогда и только тогда, когда xвстречается в M_{i}и m^{j}или в m_{i}и M^{j}для некоторых i,jТеперь нужно пройти по двум массивам M_{i}и m_{i}и проверить каждый элемент встречается ли он в m^{j}или в M^{j}. Для этого требуется 2nmсравнений.

    Легко видеть, что общее число операций оценивается как O(nm) и необходимая память ограничена O(n+m). Тем самым искомый алгоритм построен.

Задача 8

Пусть \{\xi_n\}_{n\geqslant 1}— последовательность случайных величин, имеющих стандартное нормальное распределение. Сходится ли ряд?

\sum_{n=1}^{\infty} P\left(\xi_n> \sqrt{2 \ln n+2 \ln \ln n}\right)

Подсказки

Для оценки интеграла проинтегрировать по частям.

Решение

  • Для положительных x имеем:

    P\left(\xi_n> x\right) = \frac{1}{\sqrt{2\pi}} \int_{x}^{+\infty} e^{-\frac{u^2}{2}} du =^{(*)} \frac{1}{\sqrt{2\pi}} \left(-\frac{1}{u}e^{-\frac{u^2}{2}}\right)\Big|_{x}^{+\infty} - - \frac{1}{\sqrt{2\pi}} \int_{x}^{+\infty} \frac{1}{u^2} e^{-\frac{u^2}{2}} du== \frac{1}{\sqrt{2\pi}} \frac{1}{x} e^{-\frac{x^2}{2}}  - \frac{1}{\sqrt{2\pi}} \int_{x}^{+\infty} \frac{1}{u^2} e^{-\frac{u^2}{2}} du < \frac{1}{\sqrt{2\pi}} \frac{1}{x} e^{-\frac{x^2}{2}} .

    В равенстве ^{(*)} мы проинтегрировали по частям. Поэтому

    P\left(\xi_n> \sqrt{2 \ln n+2 \ln \ln n} \right) <\frac{1}{\sqrt{2\pi}} \frac{1}{\sqrt{2 \ln n+2 \ln \ln n}} \frac{1}{n \ln n} < \frac{c}{n \ln^{\frac{3}{2}}n}

    для некоторой константы c. Так как ряд \sum_{n} \frac{1}{n \ln^{\frac{3}{2}}n} сходится, то на основании

    признака сравнения делаем вывод, что исходный ряд сходится.

    Комментарий: Из леммы Бореля-Кантелли и доказанной сходимости ряда вытекает, что \xi_n<\sqrt{2 \ln n+2 \ln \ln n} для всех n начиная с некоторого номера с вероятностью единица, причём неважен характер зависимости случайных величин \xi_n.

Что-то не так? Напишите нам на email shadhelper@yandex.ru✌️

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


  1. kovserg
    16.10.2021 02:48
    #23595946

    Не могли бы вы подробнее прокомментировать решение первой задачи?

    image


    1. rk-helper Автор
      16.10.2021 12:54
      #23596652

      Добавили более подробное определение оператора \tilde{\mathcal{A}}. По сути это просто сужение исходного оператора \mathcal{A}на меньшее подпространство\mathrm{Im}(\mathcal{A}). Поэтому его ядро есть пересечение ядра исходного оператора и этого подпространства. В нашем видео https://www.youtube.com/watch?v=Z7TNyUMwv5Y дан более детальный разбор этой задачи.


  1. Alexandroppolus
    19.10.2021 19:10
    #23607778

    В 6 задаче в массивах М и m можно хранить не сами значения максимумов/минимумов, а их индексы. Тогда второй этап будет содержать O(n+m) сравнений: обходим массивы М и m для строк, и если, например, для строки M[i] === j, то проверяем что для j-го столбца m[j] === i, и наоборот.