20 мая 2017

1. Верно ли, что если матрица $A \in \mathrm{Mat}_n (\mathbb{R})$ симметрична и положительно определена, то квадратичная форма $q(X) = \mathrm{tr}(X^\mathrm{T} A X)$ на пространстве $\mathrm{Mat}_n (\mathbb{R})$ будет положительно определенной?
   Решение
   Так как $A$ — симметричная и положительно определена, то она может быть представлена в виде $A=C^{\mathrm{T}}C$. Поэтому $$X^{\mathrm{T}}C^{\mathrm{T}}CX=(CX)^{\mathrm{T}}CX=M^{\mathrm{T}}M.$$ Отсюда получаем: $$\mathrm{tr}(X^{\mathrm{T}}C^{\mathrm{T}}CX)= \mathrm{tr}(M^{\mathrm{T}}M) = \sum\limits_{i=1}^{n} \sum\limits_{j=1}^{n} m_{ij}^2,$$ то есть $\mathrm{tr}>0$ для любых $X$.
   Ответ
   Верно.
2. Известно, что $a_0 + \frac{a_1}{2} + \frac{a_2}{3} + \ldots + \frac{a_n}{n+1}=0$ Докажите, что многочлен $a_0 + a_1 x + a_2 x^2 + \ldots + a_n x^n$ имеет хотя бы один действительный корень.
   Решение
   Рассмотрим многочлен $a(x)=a_0x+\frac{a_1}{2}x^2+\frac{a_2}{3}x^3+\ldots+\frac{a_n}{n+1}x^{n+1}$. Тогда $a(0)=0$ и $a(1)=0$, а значит по теореме Ролля $a'(x)=a_0+a_1x+\ldots+a_nx^n$ равен нулю для некоторого $x_0$ из $(0,1)$.
3. Пусть $X_1, \ldots X_n$ — независимые одинаково распределенные случайные величины с математическим ожиданием $a$ и дисперсией $\sigma^2$, принимающие положительные значения. Пусть также $m < n$. Найдите математическое ожидание отношения: $$\frac{X_1 + \ldots + X_m}{X_1 + \ldots + X_n}.$$
   Решение
   Обозначим $\overline{X}=X_1 + \ldots + X_n$ и заметим, что: $$1=E\frac{\overline{X}}{\overline{X}}=E\sum\limits_{i=1}^{n}\frac{X_i}{\overline{X}}=\sum\limits_{i=1}^{n}E\frac{X_i}{\overline{X}}=nE\frac{X_1}{\overline{X}},$$ отсюда получим $$E\frac{X_1}{\overline{X}}=\frac{1}{n}.$$ Окончательно получим $$E\frac{X_1 + \ldots + X_m}{X_1 + \ldots + X_n}=E\sum_{i=1}^{m}\frac{X_1}{\overline{X}}=\sum_{i=1}^{m}E\frac{X_1}{\overline{X}}=\frac{m}{n}.$$
   Ответ
   $\dfrac{m}{n}$.
4. Черный куб покрасили снаружи белой краской, затем разрезали на $27$ одинаковых маленьких кубиков и как попало сложили из них большой куб. С какой вероятностью все грани этого куба будут белыми?
   Решение
   Заметим, что все маленькие кубики разбиваются на $4$ группы по количеству белых граней — $8$ кубиков с $3$ гранями, $12$ кубиков с $2$ гранями, $6$ кубиков с $1$ гранью и $1$ черный кубик.
   
   Посчитаем число комбинаций, которые можно получить вращая маленький кубик. Существует $6$ вариантов зафиксировать верхнюю грань и $24$ варианта расположения боковых граней при каждой фиксации. Таким образом, существует $24$ способа повернуть маленький кубик.
   
   Для каждой группы кубиков количество подходящих вариантов равно количеству перестановок внутри группы умножить на количество подходящих поворотов:

   1. $8!\cdot 3^8$ — кубик можно вращать вокруг диагонали;
   2. $12!\cdot 2^{12}$ — два варианта расположения белых граней;
   3. $6!\cdot 4^6$ — при фиксации белой грани существует $4$ варианта расположения;
   4. $1! \cdot 24$ — для черного кубика подходят любые вращения.

   Всего возможных комбинаций расположений кубиков $27! \cdot{24}^{27}$. Таким образом, искомая вероятность равна: $$\frac{8!\cdot 3^8 \cdot 12!\cdot 2^{12} \cdot 6! \cdot 4^6 \cdot 24}{27! \cdot{24}^{27}} = \frac{8!\cdot 3^8 \cdot 12!\cdot 2^{24} \cdot 6!}{27! \cdot{24}^{26}}.$$
   Ответ
   $\dfrac{8!\cdot 3^8 \cdot 12!\cdot 2^{24} \cdot 6!}{27! \cdot{24}^{26}}$.
5. Придумайте структуру для хранения действительных чисел, которая могла бы выполнять запросы «добавить элемент», «удалить элемент», «удалить максимальный элемент» и «удалить минимальный элемент», причем последние два выполняла бы за $O(1)$. Постарайтесь также минимизировать время выполнения первых двух запросов. Можно ли сделать так, чтобы и они тоже выполнялись за $O(1)$?
6. Последовательность $a_n$ задана условиями $a_1=1, a_{n+1}=\sin (a_n)$. Сходится ли ряд $\sum_{i=1}^\infty a_i$?
   Решение
   Докажем по индукции, что $a_n \geqslant \frac1n$.
   База индукции, $n=1$.
   $$a_1 \geqslant 1.$$ Переход: предположим, что $$a_k \geqslant \frac1k,$$ тогда $$a_{k+1} = \sin (a_k) \geqslant \sin \frac1k \geqslant \frac1k - \frac{1}{6k^3} \geqslant \frac{1}{k+1},$$ что и требовалось доказать.
   Таким образом, ряд ограничен снизу гармоническим рядом, а значит, он расходится.
   Ответ
   Ряд расходится.
7. Назовем матрицу вращательной, если при повороте на $90^{\circ}$ вокруг центра она не меняется.
   (a) Докажите, что для любого набора чисел $\lambda_1, \ldots \lambda_k \in \mathbb{R}$ найдется $n \in \mathbb{N}$ и вращательная матрица $n\times n$, для которой $\lambda_1, \ldots, \lambda_k$ являются собственными значениями.
   (б) Докажите, что у вращательной матрицы с действительными коэффициентами все собственные векторы $v$ с отличными от нуля действительными собственными значениями симметричны (то есть $v_i = v_{n-i+1}$).
8. В неориентированном графе без петель и кратных ребер $2n$ вершин и $n^2+1$ ребро. Треугольником в графе называется фигура, состоящая из трех вершин и трех соединяющих их ребер. Докажите, что в этом графе найдутся два треугольника с общим ребром.