31 мая 2015

1. Квадратная матрица $A$ такова, что $\mathrm{tr}(AX)=0$ для любой матрицы $X$, имеющей нулевой след. Докажите, что матрица $A$ является скалярной (то есть имеет вид $\lambda E$ для некоторого скаляра $\lambda$).
2. Придя на письменный экзамен в ШАД, студенты поняли, что среди любых четырех человек хотя бы один уже знаком с тремя оставшимися. Докажите, что в этом случае среди любых четверых человек хотя бы один уже знаком со всеми остальными студентами.
3. На окружности выбираются две случайные точки $A$ и $B$. Найдите математическое ожидание площади меньшего из сегментов, на которые хорда $AB$ разбивает круг.
4. Дан массив из $n$ целых чисел. Предложите алгоритм, сортирующий их по остатку при делении на $5$ за время $O(n)$ (в каком порядке будут расположены числа, имеющие один и тот же остаток, неважно). Ограничение по дополнительной памяти — $O(1)$.
5. Исследуйте на сходимость и абсолютную сходимость ряд $$\sum\limits_{k=1}^\infty \sin \left( \pi \sqrt{k^2 + 1} \right).$$
6. У вас имеется неограниченное число костей в форме всех возможных правильных многогранников. Можно ли, однократно бросив некоторый набор таких костей, симулировать бросок (а) правильной семигранной кости? (б) правильной 15-гранной кости?
7. Пусть $A$ и $B$ — квадратные вещественные матрицы одного и того же размера. Докажите, что $$\mathrm{det} (E-AB) = \mathrm{det} (E-BA).$$
   Решение
   1. Пусть $A$ обратима. Тогда $$\det (E-AB) = \det (A^{-1}) \det (E-AB) \det A = \det(E - BA).$$ 2. Пусть $A$ необратима. Тогда рассмотрим полином $$P(x) = \det (E - (A - xE)B) - \det(E - B(A - xE)).$$ Если $x$ не является собственным значением $A$, матрица $A-xE$ обратима, поэтому для таких $x$ $P(x) = 0$. Получаем, что $P(x)$ — полином конечной степени, имеющий бесконечное число корней, а значит, $P(x) \equiv 0$.
   Решение 2
   Заметим, что $$\left( \begin{array}{cc} E&A\\O&E \end{array} \right) \left( \begin{array}{cc} E-AB&O\\O&E \end{array} \right) \left( \begin{array}{cc} E&O\\B&E \end{array} \right) = \left( \begin{array}{cc} E&O\\B&E \end{array} \right) \left( \begin{array}{cc} E&O\\O&E - BA \end{array} \right) \left( \begin{array}{cc} E&A\\O&E \end{array} \right).$$ Поэтому $$\det(E - AB) = \det(E - BA).$$
8. За столом сидят $n$ старателей, перед каждым из которых находится кучка золотого песка. Каждую минуту происходит следующее: по общей команде каждый из них перекладывает в свою кучку половину песка из кучки левого соседа и половину — из кучки правого соседа. Опишите асимптотическое поведение кучек (а) при $n=3$; (б) при произвольном $n$.