28 мая 2016

1. Пусть $A$ и $B$ — квадратные матрицы одинакового размера. Верно ли, что если $ABA=A$, то $BAB=B$?
   Решение
   Пусть $A = \begin{pmatrix}1&0\\0&0\end{pmatrix}$, а $B = \begin{pmatrix}1&0\\0&1\end{pmatrix}$. Тогда $ABA = A^2 = A$, но $BAB = A \neq B$. Значит, утверждение задачи не верно.
   Ответ
   Не верно.
2. Исследуйте на сходимость ряд $$\sum_{n=3}^\infty (\ln \ln n)^{-\ln n}.$$
   Решение
   Воспользуемся логарифмическим признаком сходимости рядов: $$D = \lim_{n\to \infty} \frac{\ln \frac{1}{a_n}}{\ln n} = \lim_{n\to \infty} \frac{\ln ((\ln \ln n)^{\ln n})}{\ln n} = \lim_{n\to \infty} \ln \ln \ln n.$$ Поскольку предел существует и равен $+ \infty$, ряд сходится.
   Решение 2
   Перепишем выражение для членов ряда в следующем виде $$a_n = (\ln \ln n)^{-\ln n} = \exp (-\ln n \ln \ln \ln n) = \frac{1}{n^{\ln \ln \ln n}}.$$ Заметим, что начиная с $n = \lceil \exp \exp \exp (2) \rceil$, данный ряд сходится быстрее, чем сходящийся ряд $\frac{1}{n^2}$. Следовательно, ряд сходится.
   Ответ
   Ряд сходится.
3. Случайные величины $X$ и $Y$ независимы. Плотность случайной величины $X$ равна $p_X (t) = \frac{t}{2} \cdot I_{[0;2]} (t)$ (где $I_{[0;2]} (t)$ — индикаторная функция отрезка $[0;2]$), а $Y$ имеет равномерное распределение на отрезке $[0;3]$. Найдите вероятность того, что из отрезков с длинами $X$,$Y$ и $1$ можно составить треугольник.
   Решение
   Проще найти вероятность противоположного события: $$\begin{align*} 1 - p(\triangle) &= p(Y \leqslant 1 - X) + p(Y \leqslant X-1) + p(Y \geqslant X+1)\\ &= \int\limits_0^1 \frac{t}{2} \frac{1-t}{3} dt + \int\limits_1^2 \frac{t}{2} \frac{t-1}{3} dt + \int\limits_0^2 \frac{t}{2} \frac{2-t}{3} dt\\ &= \frac{1}{36} + \frac{5}{36} + \frac{8}{36} = \frac{7}{18}. \end{align*}$$ Тогда $$p(\triangle) = 1 - \frac{7}{18} = \frac{11}{18}.$$
   Ответ
   $\dfrac{11}{18}.$
4. Даны $n$ отрезков $[a_i, b_i]$. Назовем индексом вложенности отрезка $[a_i,b_i]$ количество отрезков, которые его содержат. Предложите алгоритм, определяющий, есть ли в наборе отрезок с индексом вложенности, превышающим $1000$. Ограничение по времени — $O(n \log n)$, по дополнительной памяти — $O(n)$.
   Решение
   Пронумеруем все начала отрезков $a_i$ в порядке возрастания координаты. Если где-то координаты совпадают, порядок нумерации определяется по убыванию координат концов, если же и координаты концов совпадают — произвольным образом. Далее пронумеруем концы отрезков так, чтобы номер конца отрезка совпадал с номером его начала. Выпишем получившиеся номера концов отрезков в порядке убывания их координаты. Если где-то координаты совпадают — выписываем их в произвольном порядке. Сложность — $O(n \log n)$.
   В результате получилась некоторая перестановка $\sigma$ чисел от $1$ до $n$. Заметим, что индекс вложенности $i$-го отрезка равен количеству чисел, которые в этой перестановке одновременно
   (а) находятся левее (меньше по индексу) числа $i$
   (б) меньше (по значению) числа $i$
   Исключение составляют отрезки, которые полностью совпадают, но мы можем не обращать на это внимание, поскольку у одного из таких отрезков результат будет правильным (а у остальных — меньше), а следовательно, это не меняет ответ на вопрос задачи (считаем, что если отрезки совпадают, то каждый из них содержит все остальные).
   По перестановке $\sigma$ мы можем найти массив $\beta$ чисел, в котором число $\beta_i$ равно количеству таких чисел в перестановке $\sigma$, что они левее (меньше по индексу) и меньше (по значению) числа $\sigma_i$.
   Алгоритм нахождения $\beta$ по $\sigma$ практически идентичен классическому алгоритму нахождения таблицы инверсий по перестановке. Положим $\beta_i = 0, \,i=1\ldots n$. Пусть $k$ пробегает значения от $\lfloor \lg n \rfloor$ до $0$ (иными словами, $k$ пробегает количество цифр в двоичной записи максимального числа в $\sigma$). Для каждого $k$ будем обнулять все счетчики $x_s: 0 \leqslant s \leqslant n/2^{k+1}$ и для всех $j=1,2,\ldots,n$ выполнять следующее: вычисляем $r=\lfloor \sigma_j/2^k \rfloor \mod 2$, $s = \lfloor \sigma_j/2^{k+1} \rfloor$; если $r=0$, то $x_s\mathrel{+}=1$, если же $r=1$, то $b_j\mathrel{+}=x_s$.
   По существу алгоритм делает следующее. Запишем все числа перестановки в двоичной системе и дополним слева нулями так, чтобы длина всех записей была одинакова. Тогда на шаге $k = \lfloor \lg n \rfloor$ мы выписываем количество таких чисел в перестановке $\sigma$, что они меньше по индексу, а их старший бит меньше старшего бита числа $\sigma_i$. На шаге $k=\lfloor \lg n \rfloor - 1$ мы решаем задачу уже для двух старших битов и так далее. Сложность — $O(n \log n)$. В итоге нам нужно проверить, есть ли в массиве $\beta$ число, большее чем $1000$, что делается за $O(n)$. Итоговая сложность — $O(n \log n)$.
5. Существует ли непрерывная функция $f(x)$, для которой $f(f(x)) = 1-x^3$?
   Решение
   Предположим, что такая непрерывная функция существует. Заметим, что в таком случае функция $f(f(x))$ строго убывает. Из этого следует, что она биективна. Из биективности функции $f(f(x))$ следует биективность функции $f(x)$ (сюръективность и инъективность легко обосновываются по отдельности). Непрерывная биективная функция должна быть строго монотонной, а из строгой монотонности функции $f(x)$ следует, что функция $f(f(x))$ строго возрастает. Получили противоречие — значит, такой функции не существует.
   Ответ
   Не существует.
6. В ряд расположены $m$ предметов. Случайно выбираются $k$ предметов, $k<m$. Случайная величина $X$ равна количеству таких предметов $i$, что $i$ выбран, а все его соседи не выбраны. Найдите математическое ожидание $X$.
   Решение
   Пусть случайная величина $Y_i$ равна $1$ если $i$ выбран, а все его соседи не выбраны, и $0$ в противном случае. Тогда $$M(X) = M \left( \sum\limits_{j=1}^m Y_j \right) = \sum\limits_{j=1}^m M(Y_j).$$ Рассмотрим два случая.
   (а) $j = 1$ или $j=m$.
   Фиксируем один предмет и расставляем оставшиеся $k-1$ предметов по $m-2$ местам: $$M(Y_1) = M(Y_m) = C_{m-2}^{k-1} / C_m^k = \frac{k(m-k)}{m(m-1)}.$$ (б) $j=2\ldots m-1$.
   Фиксируем один предмет и расставляем оставшиеся $k-1$ предметов по $m-3$ местам: $$M(Y_{j\neq 1,m}) = C_{m-3}^{k-1} / C_m^k = \frac{k(m-k)(m-k-1)}{m(m-1)(m-2)}.$$ Считаем суммарное математическое ожидание: $$M(X) = 2 \frac{k(m-k)}{m(m-1)} + (m-2) \frac{k(m-k)(m-k-1)}{m(m-1)(m-2)} = \frac{k(m-k)(m-k+1)}{m(m-1)}.$$
   Ответ
   $\dfrac{k(m-k)(m-k+1)}{m(m-1)}$.
7. В графстве Орэ имеется несколько городов, соединенных дорогами, причем из каждого города выходит ровно три таких дороги. Инквизитор брат Франсуа странствует по графству, искореняя ересь. Выехав из города Э, он едет по дорогам, причем после каждого посещенного им города он поворачивает либо направо, либо налево по отношению к дороге, по которой приехал, и никогда не сворачивает в ту сторону, в которую он свернул перед этим. Докажите, что рано или поздно брат Франсуа вернется в город Э.
   Решение
   Все города графства Орэ связаны каким-то конечным числом дорог. Если инквизитор странствует по графству достаточно долго, то он проедет достаточно много дорог, поэтому хотя бы по одной дороге AB (A и B — города) он проедет не менее пяти раз. При этом не менее трех раз он проедет по этой дороге в одном и том же направлении (скажем, от A до B), поэтому, если из города B, кроме BA, ведут еще две дороги BC и BD, то инквизитор минимум дважды, — скажем, после $i$-го и после $j$-го посещения города B, где $j>i$, — сворачивал, выезжая из B (куда он оба раза приезжал из A), в одну и ту же сторону, скажем, в сторону города C. Но из условия тогда следует, что не только в $i$-e и в $j$-е посещение B инквизитор приехал в B из одного города — из A, — но и в A он оба раза приезжал из одного и того же города P (ведь если инквизитор после B свернул на дорогу BC, например, налево, то в A он должен был свернуть направо после посещения P). Аналогично этому устанавливается, что полностью совпадают пути инквизитора, предшествующие двум рассматриваемым посещениям города B: в город P он оба раза попал из одного и того же города, и так далее. Но тогда если инквизитор до $i$-го посещения B миновал, начиная с выезда из города Э, какое-то число $k$ городов, то и за $k$ городов до $j$-го посещения B он снова был в Э, что и доказывает утверждение задачи.
8. Пусть $A$ и $B$ — симметричные билинейные функции на двумерном вещественном пространстве, причем $A$ положительно определена, а $B$ отрицательно определена. Докажите, что любая непрерывная кривая в пространстве симметричных билинейных функций, соединяющая $A$ и $B$, содержит функцию с вырожденной матрицей.
   Решение
   Рассмотрим функцию от матрицы билинейной формы $f(X)$, которая возвращает максимальное собственное значение. Поскольку матрица симметрична, все собственные значения вещественны, а значит, функция определена для любой матрицы. В случае двумерного пространства понятно, что $f(X)$ является непрерывной как композиция непрерывных функций, образованных элементами матрицы. Теперь заметим, что $f(A) > 0$, а $f(B) < 0$. Тогда по теореме о промежуточных значениях непрерывной функции $\exists X_0: f(X_0) = 0$. Поскольку у такой матрицы $X_0$ есть собственное значение $0$ — это вырожденная матрица.