24 мая 2015

1. Найдите предел последовательности $(a_n)$, для которой $a_0=-\frac12$, $$a_{n+1}=\frac{a^2_n (a_n-3)}{4}.$$
   Решение
   Сначала докажем, что последовательность сходится. Если $a_n < 0$, то $a_{n+1} < 0$, поэтому она ограниченна сверху. Сравним $a_n$ и $a_{n+1}$: $$a_n \;\;?\;\; \frac{a_n^2 - 3}{4} \Leftrightarrow 0 \;\;?\;\; a_n^3 - 3a_n^2 - 4a_n \Leftrightarrow 0 \;\;?\;\; a_n(a_n+1)(a_n-4).$$ Видим, что при $a_n \in (-1;0)$ имеет место неравенство $a_n < a_{n+1}$, то есть последовательность возрастает. По теореме Вейерштрасса она имеет предел. Чтобы его найти, перейдем к пределу в нашем рекуррентном соотношении: $$a = \frac{a^2(a-3)}{4} \Leftrightarrow a^3 - 3a^2 - 4a = 0,$$ откуда предел может быть одним из чисел $0$, $-1$ и $4$. Нетрудно понять, что это $0$.
   Ответ
   $0$.
2. На плоскости, однородно покрытой прямоугольниками со сторонами $10$ и $20$, рисуют случайную окружность радиуса $4$. Найдите вероятность того, что окружность имеет общие точки ровно с тремя прямоугольниками.
   Решение
   Будем следить за положением центра окружности. Ясно, что можно ограничить рассмотрение внутренностью одного прямоугольника. Нетрудно видеть, что для того, чтобы окружность пересекала ровно три прямоугольника, должны выполняться два условия:
   (1) расстояния от центра до двух ближайших сторон прямоугольника должны быть меньше $4$;
   (2) расстояние до ближайшей вершины прямоугольника должно быть больше $4$.
   Зная это, мы можем изобразить множество точек, удовлетворяющих этим условиям:
   Следовательно, искомая вероятность равна $$\frac{S_{\text{закрашенной части}}}{S_{\text{прямоугольника}}} = \frac{4 \cdot (16 - \frac14 \cdot 16\pi)}{10 \cdot 20} = \frac{16 - 4\pi}{50} = \frac{8 - 2\pi}{25}.$$
   Ответ
   $\dfrac{8 - 2\pi}{25}$.
3. Дима и Ваня по очереди вписывают элементы в квадратную матрицу порядка $2n$. Цель Вани — сделать так, чтобы получившаяся в итоге матрица имела собственное значение $1$, а цель Димы — помешать ему. Дима ходит первым. Есть ли у кого-нибудь из них выигрышная стратегия?
   Решение
   Получившаяся матрица $A$ будет иметь собственное значение $1$, если матрица $A - E$ будет вырожденной. Добиться этого Ваня может, например, следующим образом. После того, как Дима вписал какой-то элемент $a_{ij}$, Ваня вписывает новый элемент $a_{ik}$ в ту же строку таким образом, чтобы $a_{ik}-\delta_{ik}=-(a_{ij}-\delta_{ij})$, где $\delta_{ij}$ — символ Кронекера. Тогда сумма чисел в каждой из строк матрицы $A - E$ будет равна нулю, то есть матрица $A - E$ будет вырожденной.
   Ответ
   При правильной стратегии выиграет Ваня.
4. Найдите определитель матрицы $A=(c_{ij})$, где $a_{ij} = C_{i+j-2}^{i-1}$.
   Решение
   Воспользуемся формулой $C_n^k = C_{n-1}^{k-1} + C_{n-1}^k$. Вычтем из каждой строки матрицы предыдущую, а затем из каждого столбца предыдущий. Полученная матрица будет иметь вид: $$\begin{pmatrix}1&0\\0& \left( C_{i+j-2}^{i-1} \right)_{i,j=1}^{n-1} \end{pmatrix}.$$ Продолжая рассуждение по индукции, убеждаемся, что определитель исходной матрицы равен единичной, то есть $1$.
   Ответ
   $1$.
5. Даны два массива целых чисел $a[1..n]$ и $b[1..k]$, причем все элементы $b$ различны. Предложите алгоритм, находящий набор индексов $i_1 < i_2 < \ldots < i_k$ с минимальной разностью $i_k-i_1$, для которого набор $a[i_1],\ldots, a[i_k]$ является перестановкой элементов массива $b$. Ограничение по времени — $O(nk)$ (более быстрые алгоритмы приветствуются), по дополнительной памяти — $O(n)$.
   Решение
   Это можно сделать в один проход по массиву $a$. Каждый раз, когда мы встречаем элемент массива $b$, мы записываем его и его номер в специальные массивы. При этом мы поддерживаем в этих массивах отрезок $I$, на котором мы надеемся найти все различные элементы $b$. Ясно, что если очередной элемент массива $a$ совпадает с первым элементом отрезка $I$, то $I$ уже явно не может быть кратчайшим отрезком, удовлетворяющим условию задачи, и мы можем сдвинуть его левый конец. Если на очередном шаге мы понимаем, что $I$ содержит все различные элементы $b$, то $I$ — кандидат на ответ; в этом случае мы также сдвигаем его левый конец.
   Оценка $O(n)$ по памяти очевидна. Оценка $O(nk)$ по сложности может быть обоснована следующим образом: мы все делаем в один проход (отсюда $n$) и на каждом шаге должны искать элемент в массиве $b$ (отсюда $k$). Ясно, что алгоритм можно улучшить: если вначале отсортировать $b$ и использовать двоичный поиск, получим $O(n \log k)$. Если же использовать совершенное хеширование, то можно добиться сложности $O(n+k)$.
6. В 2222 году волейбольные турниры проводят по новой системе. Говорят, что команда A превосходит команду B, если A выиграла у B или у какой-либо команды, выигравшей у B (правило не транзитивно!). Каждая пара команд играет по одному разу. Ничья исключается волейбольными правилами. Чемпионом объявляют команду, превзошедшую все другие команды. Докажите, что (а) чемпион обязательно найдется, и (б) не может быть ровно двух чемпионов.
   Решение
   Договоримся, что каждая команда за турнир получает очки, равные числу превзойденных ею команд. Сначала докажем следующую простую лемму:
   
   Лемма. Пусть команда Е не превосходит команду К. Тогда К набрала больше очков, чем Е.
   
   Доказательство. Если Е не превосходит К, то К победила команду Е, а также все команды, которые победила команда Е.
   Теперь пусть Х — команда, которую превзошла команда Е. Если Е выиграла у Х, то К также выиграла у Х. Значит, К превосходит Х. Если же Е выиграла у команды F, которая выиграла у Х, то заметим, что К тоже выиграла у F. Значит, К выиграла у F, которая выиграла у Х, то есть К превосходит Х. Итого, К превосходит все команды, которые превзошла Е, да еще и Е в придачу, то есть как минимум на одну команду больше, чем Е. Лемма доказана.
   
   (а) Пусть А — команда, заработавшая максимальное число очков. Докажем, что А — чемпион. Допустим, это не так, тогда есть команда В, которую А не превзошла. По лемме получаем, что В заработала больше очков, чем А. Противоречие.
   
   (б) Пусть у нас есть два чемпиона: А и В. Друг с другом они играли; пусть, к примеру, победила А. Так как В превосходит все другие команды (и А в частности), то В победила некоторую команду, которая выиграла у А. Допустим для начала, что есть команды, которые победили и А, и В. Тогда можно показать, что та из них (назовем ее С), которая набрала больше всего очков, и будет третьим чемпионом. В самом деле, пусть Е — команда, которую не превзошла С. Тогда, во-первых Е победила и А, и В, а во-вторых, Е заработала больше очков, чем С — противоречие. Пусть теперь нет команд, которые победили и А, и В. Рассмотрим множество всех таких команд, которые победили А, но проиграли В. Отметим, что оно непусто (см. выше). Среди них возьмем команду с наибольшим числом очков. Тогда пользуясь леммой мы можем установить, что эта команда является третьим чемпионом.
7. Вычислите интеграл $$\int\limits_{\frac13}^3 \frac{\textrm{arctg}\, x}{x^2-x+1} dx.$$
   Решение
   Обозначим исходный интеграл через $I$. Произведем замену $x = \frac{1}{t}$.
   Тогда $$I = \int\limits_{\frac13}^3 \frac{\textrm{arctg}\, x}{x^2-x+1} dx = \int\limits_{\frac13}^3 \frac{\textrm{arcctg}\, t}{t^2 - t + 1} dt =$$ $$= \int\limits_{\frac13}^3 \frac{\frac{\pi}{2} - \textrm{arctg}\, t}{t^2 - t + 1} dt = \frac{\pi}{2} \int\limits_{\frac13}^3 \frac{dt}{t^2 - t + 1} dt - I.$$ Отсюда $$I = \frac{\pi}{4} \int\limits_{\frac13}^3 \frac{dt}{t^2 - t + 1} dt = \frac{\pi}{2 \sqrt{3}} \textrm{arctg}\, \left. \left( \frac{2x-1}{\sqrt{3}} \right) \right|_{\frac13}^3 =$$ $$= \frac{\pi}{2\sqrt{3}} \left( \textrm{arctg}\, \frac{5}{\sqrt{3}} + \textrm{arctg}\, \frac{1}{3\sqrt{3}} \right) = \frac{\pi}{2\sqrt{3}} \textrm{arctg}\, 4\sqrt{3}.$$
   Ответ
   $\dfrac{\pi}{2\sqrt{3}} \textrm{arctg}\, 4\sqrt{3}.$
8. На плоскости нарисована ломаная с $n$ звеньями. Длина каждого звена равна $1$, ориентированный угол между соседними звеньями с равной вероятностью равен $\alpha$ или $-\alpha$. Найдите математическое ожидание квадрата расстояния от ее начальной точки до конечной.
   Решение
   Введем на плоскости систему координат так, чтобы первое звено ломаной было направлено вдоль оси $Ox$. Пусть $\alpha_k$ — ориентированный угол между $(k+1)$-м звеном ломаной и первым звеном ломаной (то есть осью $Ox$). Тогда $\alpha_0=0$, $\alpha_{k+1} = \alpha_k + \xi_{k+1} \alpha$, где $\xi_k$ — случайная величина, принимающая с вероятностью $\frac12$ значения $\pm 1$. Отметим, что проекции на оси $Ox$ и $Oy$ $k$-го звена ломаной равны $\cos \alpha_{k-1}$ и $\sin \alpha_{k-1}$ соответственно. Тогда квадрат расстояния от начала ломаной до ее конца равен $$L_n^2 = \left( \sum\limits_{k=0}^{n-1} \cos \alpha_k \right)^2 + \left( \sum\limits_{k=0}^{n-1} \sin \alpha_k \right)^2.$$ Наша задача — найти математическое ожидание этой случайной величины.
   Имеем $$\begin{align*} M(\cos \alpha_k) &= M(\cos(\alpha_{k-1} + \xi_k \alpha)) = M(\cos \alpha_{k-1} \cos (\xi_k \alpha) - \sin \alpha_{k-1} \sin (\xi_k \alpha)),\\ M(\sin \alpha_k) &= M(\sin(\alpha_{k-1} + \xi_k \alpha)) = M(\sin \alpha_{k-1} \cos (\xi_k \alpha) + \cos \alpha_{k-1} \sin (\xi_k \alpha)). \end{align*}$$ Пользуясь тем, что $\sin \alpha_0 = 0$ и $\cos (\xi_k \alpha) = \cos \alpha$ (в силу нечетности косинуса), по индукции получаем, что $$\begin{align*} M(\cos \alpha_k) &= \cos^k \alpha,\\ M(\sin \alpha_k) &= 0. \end{align*}$$ Далее найдем математическое ожидание произведений. Пусть $m \geqslant k$. С помощью индукции по $(m-k)$ можно доказать, что $$\begin{align*} M(\cos \alpha_k \cdot \cos \alpha_m) &= \cos^{m-k} \alpha \cdot M(\cos^2 \alpha_k),\\ M(\sin \alpha_k \cdot \sin \alpha_m) &= \cos^{m-k} \alpha \cdot M(\sin^2 \alpha_k). \end{align*}$$ Следовательно $$M(L_{n+1}^2) = M \left( \left( \sum\limits_{k=0}^{n} \cos \alpha_k \right)^2 + \left( \sum\limits_{k=0}^{n} \sin \alpha_k \right)^2 \right) =$$ $$= M(L_{n}^2) + M \left( \cos^2 \alpha_n + \sin^2 \alpha_n + 2 \sum\limits_{k=0}^{n-1} (\cos \alpha_n \cos \alpha_k + \sin \alpha_n \sin \alpha_k) \right) =$$ $$= M(L_{n}^2) + 1 + 2 \sum\limits_{k=0}^{n-1} \cos^{n-k} \alpha \cdot (M(\sin^2 \alpha_k) + M(\cos^2 \alpha_k)) =$$ $$= M(L_{n}^2) + 1 + 2 \sum\limits_{k=0}^{n-1} \cos^{n-k} \alpha = M(L_{n}^2) + 1 + 2 \sum\limits_{t=1}^n \cos^t \alpha =$$ $$= M(L_{n}^2) + 1 + 2\cos \alpha \cdot \frac{1 - \cos^n \alpha}{1 - \cos \alpha}.$$ Отсюда уже нетрудно получить ответ $$M(L_n^2) = n \cdot \frac{1+\cos \alpha}{1 - \cos \alpha} - 2 \cos \alpha \cdot \frac{1 - \cos^n \alpha}{(1 - \cos \alpha)^2}.$$
   Ответ
   $n \cdot \dfrac{1+\cos \alpha}{1 - \cos \alpha} - 2 \cos \alpha \cdot \dfrac{1 - \cos^n \alpha}{(1 - \cos \alpha)^2}$.