Полный разбор экзамена в ШАД

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

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

Задача 1

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

Подсказки
Использовать связь ранга матрицы с образом соответствующего линейного оператора.
Решение
Обозначим $\mathcal{A}$ оператор с матрицей . Напомним, что $\operatorname{Im}(\mathcal{A})$ обозначает образ оператора, $\operatorname{Ker}(\mathcal{A})$ — ядро.
Определим оператор $\tilde{A}$ , действующий на $\operatorname{Im}(\mathcal{A})$ как ограничение оператора $\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}$ действующего на векторном пространстве справедлива формула
$\operatorname{dim}(\operatorname{Im}(\mathcal{L}))+\operatorname{dim}(\operatorname{Ker}(\mathcal{L}))=\operatorname{dim} V$

Задача 2

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

Подсказки
Разбить все столбцы на группы по принципу того, какое число по чётности стоит снизу, какое сверху.
Решение
- Разобьём все столбцы таблицы на три группы:
  $1. \text{НН: нечётная стоит под нечётной},$ $2. \text{ЧН: чётная стоит под нечётной},$ $3. \text{ЧЧ: чётная стоит под чётной.}$
  Предположим, что в группе НН в первой строке элементов. Тогда во второй строке этой группы также элементов, а количество элементов в верхней строке в группе ЧН равно . Тем самым имеем следующую картинку:
  Число способов выбрать элементы для группы НН равно $C_{n-k}^k$ : сначала выбираем $C_{n}^k$ способами нечётные числа на верхние позиции, затем на нижние. Число способов выбрать чётные элементы (нечётные элементы уже определены на предыдущем шаге) для группы ЧН равно $C_{n}^{n-2k}$ . Элементы в верхней строке для группы ЧЧ можно выбрать $C_{2k}^k$ способами, на нижние позиции пойдут оставшиеся чётные элементы. После того как числа распределены по группам нам нужно выбрать места в таблице, где будут располагаться группы. Например, места с 1 по 10 уходят для группы НН, с 10 по 20 для группы ЧН , и с 20 по для группы ЧЧ. Это можно сделать способами - выбираем места для группы НН и затем для ЧЧ, для группы ЧН оставшиеся. Далее нужно учесть, что мы можем переставлять числа внутри группы, на одной строке.
  Это даст нам ещё вариантов. Окончательно получаем ответ:
  $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)^2 (k!)^2 ((n-2k)!)^2 (k!)^2$

Задача 3

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

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

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

Подсказки
Обозначим и времена прихода первой и второй электричек соответственно. Переформулировать вопрос задачи в терминах
Решение
Обозначим и времена прихода первой и второй электричек соответственно. Событие состоящее в том, что студент сможет уехать хотя бы на одной электричке может быть записано в следующем виде:
$\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.$
В равенстве $^{(*)}$ мы воспользовались независимостью случайных величин и
Решим пункт б). Обозначим $\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}$
Для положительного вычислим
$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},$
где экспоненциально распределён с параметром $\lambda>0$ .

Задача 4

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

Подсказки
Придумать чётную функцию такую, что .
Решение
Неверно. Пример функции
$f(x) = x \cos(2\pi \log_2(|x|))$

Задача 5

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

$\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).$
В последнем равенстве мы использовали то, что для ортогональной матрицы выполняется соотношение , где — единичная матрица. Также мы воспользовались известными формулами :
$\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] Считайте, что все элементы матрицы различны

Подсказка
Подумать как найти максимальный элемент в строке и минимальный столбце.
Решение
Будем обходить все элементы матрицы по очереди и будем хранить максимальный и минимальный элемент для каждой строки и для каждого столбца:
$\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{-ой строке. }$
Для этого нам понадобится памяти и сравнений. Заметим, что элемент является седлом тогда и только тогда, когда встречается в $M_{i}$ и $m^{j}$ или в $m_{i}$ и $M^{j}$ для некоторых Теперь нужно пройти по двум массивам $M_{i}$ и $m_{i}$ и проверить каждый элемент встречается ли он в $m^{j}$ или в $M^{j}$ . Для этого требуется сравнений.
Легко видеть, что общее число операций оценивается как и необходимая память ограничена . Тем самым искомый алгоритм построен.

Задача 8

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

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

Подсказки
Для оценки интеграла проинтегрировать по частям.
Решение
Для положительных имеем:
$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}$
для некоторой константы . Так как ряд $\sum_{n} \frac{1}{n \ln^{\frac{3}{2}}n}$ сходится, то на основании
признака сравнения делаем вывод, что исходный ряд сходится.
Комментарий: Из леммы Бореля-Кантелли и доказанной сходимости ряда вытекает, что $\xi_n<\sqrt{2 \ln n+2 \ln \ln n}$ для всех начиная с некоторого номера с вероятностью единица, причём неважен характер зависимости случайных величин $\xi_n$ .

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

Источник: https://habr.com/ru/post/583200/

Вернуться к списку

Интересные статьи

Прикручиваем Twig к Битрикс, или ещё одна попытка скрестить ежа с ужом

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

Администратор узла сети I2P. Полный курс

В I2P присутствует две основные сущности: роутер и конечная точка. Роутером называется программный клиент, который необходимо установить для использования I2P. По умолчан...

Ещё один велосипед: пишем свой автозагрузчик классов для Битрикс

Кто бы что ни говорил, но я считаю, что изобретение велосипедов — штука полезная. Использование готовых библиотек и фреймворков, конечно, хорошо, но порой стоит их отложить и создать ...

Разбор неисправных ноутбучных аккумуляторов. Заметки электровелосипедиста

Здравствуйте. По роду деятельности более 6 лет занимаюсь ремонтом и сборкой Li-ion аккумуляторных батарей для электровелосипедов. У меня часто оказываются неисправные ноутбучные аккумулятор...

Композитный сайт 1С-Битрикс

Согласно многочисленным исследованиям поведения пользователей на сайте, порядка 25% посетителей покидают ресурс, если страница грузится более 4 секунд.