2 июня 2018

1. В социальной сети «Улей» некоторые пары пользователей считаются друзьями, причем известно, что у любой пары друзей нет общих друзей, а у любой из пар не являющихся друзьями пользователей ровно два общих друга. Докажите, что у всех пользователей одинаковое число друзей.
   Решение
   Рассмотрим пару пользователей $a$ и $b$. Пусть они друзья. Тогда множества их друзей, не включающие $a$ и $b$, назовем $F(a)$ и $F(b)$. По условию задачи $F(a)$ и $F(b)$ не пересекаются. У любого пользователя из $F(a)$ существует один общий друг с $b$. Понятно, что он может быть только из $F(b)$. Таким же образом у любого пользователя из $F(b)$ существует единственный друг из $F(a)$. Такое может быть только в случае, если множества $F(a)$ и $F(b)$ содержат одинаковое число пользователей. Пусть теперь $a$ и $b$ не друзья. Тогда существует пользователь $c$, который общий для $a$ и $b$. По уже доказанному, у $a$ и $c$ одинаковое число друзей, у $b$ и $c$ одинаковое число друзей, а значит $a$ и $c$ также имеют одинаковое число друзей.
2. (a) Докажите, что функции $\det (X)$, $\det (X+E)$ и $\det (X-E)$ на пространстве комплексных матриц $3 \times 3$ линейно независимы.
   (b) Докажите, что найдется $m \in \mathbb{N}$, для которого набор функций $$\det (X-mE),\, \det (X-(m-1)E),\, \det (X-(m-2)E),\, \ldots,\, \det (X+mE)$$ линейно зависим.
3. Случайные величины $X$ и $Y$ независимы. $X$ имеет распределение Лапласа с плотностью $\frac{1}{2} e^{-|x|}$, а $Y$ — равномерное на отрезке $[1,2]$. Найдите плотность распределения случайной величины $X-2Y$.
4. Подстановка $\sigma$ задана двумя массивами $\text{a[1}\,\text{.}\,\text{.}\,\text{n]}$ и $\text{b[1}\,\text{.}\,\text{.}\,\text{n]}$ состоящими из всех различных чисел от $1$ до $n$ и такими, что $\text{b[i]} = \sigma (\text{a[i]})$ для каждого $i = 1,\ldots,n$ (например, $\text{a} = \text{[2,}\,\,\text{3,}\,\,\text{1]}$, $\text{b} = \text{[1,}\,\,\text{3,}\,\,\text{2]}$ кодирует транспозицию $(1,2)$). Придумайте алгоритм, определяющий, содержит ли $\sigma$ цикл длины $k$. Ваш алгоритм может изменять исходные массивы, но должен справляться с задачей за $O(n^2)$ операций с использованием $O(1)$ дополнительной памяти (оценивая эти две асимптотики, можете считать $k$ константой).
5. Пусть $f$ — гладкая вещественная функция, причем $f(0) = 0$, $f(1) = 1$. Докажите, что найдутся различные $x_1, x_2 \in [0,1]$, для которых $$\frac{1}{f^{'}(x_1)} + \frac{1}{f^{'}(x_2)} = 2.$$
6. Линейный оператор $A : \mathbb{R}^n \longrightarrow \mathbb{R}^n$ таков, что $A^3$ — это оператор проекции. Какие собственные значения может иметь $A$? Верно ли, что $A$ будет иметь диагональную матрицу в каком-либо базисе $\mathbb{R}^n$?
7. (a) Для непрерывной функции $f(x)$ найдите $$\frac{d}{da} \iint\limits_{-a \leqslant x,y \leqslant a} f \left( \frac{x+y}{2} \right) dx dy.$$ (b) Опишите все непрерывные функции $f(x)$, для которых при всех $a \in \mathbb{R}$ имеет место равенство $$\iint\limits_{-a \leqslant x,y \leqslant a} f \left( \frac{x+y}{2} \right) dx dy = \int\limits_{-a}^{a} f(x) dx.$$
8. Вы попали в лабиринт, состоящий из нескольких комнат, соединенных системой двусторонних порталов. Каждый портал соединяет только одну пару комнат лабиринта. Порталом можно пользоваться неограниченное число раз. Вы появляетесь в комнате $v_1$ и прыжками перемещаетесь между комнатами. В комнате $v_6$ находится выход из лабиринта. Предположим, что каждый следующий портал для прыжка вы выбираете случайно и равновероятно среди всех порталов в этой комнате, включая портал до предыдущей комнаты. Найдите математическое ожидание количества прыжков до первого попадания в $v_6$.
   Схема лабиринта: