3 июня 2017

1. Пусть $x$ и $y$ — два ненулевых вектора из $\mathbb{R}^n$. Верно ли, что найдется симметричная матрица $A,$ для которой $y=Ax$?
2. Непрерывная функция $f(x)$ такова, что $f(0)=f(2)$. Докажите, что для какого-то $x\in [0;2]$ имеет место равенство $f(x)=f(x-1)$.
   Решение
   Пусть $g(x) = f(x) - f(x-1)$. Тогда $\begin{cases} g(1) = f(1) - f(0), \\ g(2) = f(2) - f(1). \end{cases}$
   Заметим, что $g(1) + g(2) = f(2) - f(0) = 0$. Отсюда следует, что функция $g(x)$ меняет знак на отрезке $[1,2]$ (теорема о промежуточном значении непрерывной функции). Иными словами, $\exists x_0 \in [1,2]: g(x_0)=0$, откуда следует утверждение задачи.
3. Из равномерного распределения на отрезке $[0;1]$ независимо выбираются две точки $x$ и $y$. При каких $a$ события $\max(1-2x,y) < a$ и $\max(1-2y,x) < a$ независимы?
4. В компании «Тындекс» у каждого сотрудника не менее $50$ знакомых. Оказалось, что есть два сотрудника, знакомые друг с другом лишь через $9$ рукопожатий (то есть кратчайшая соединяющая их цепочка из попарно знакомых людей содержит $8$ промежуточных людей). Докажите, что в этой компании хотя бы $200$ сотрудников.
5. Квадратная матрица $A$ размера $n\times n$ имеет различные собственные значения $\lambda_1, \ldots, \lambda_n$. Найдите все собственные значения (в том числе комплексные) матрицы $$\begin{pmatrix}0&-A\\A&0\end{pmatrix}$$
   Решение
   Поскольку элементы столбцов блочной матрицы коммутируют, характеристическое уравнение можно представить в следующем виде: $$\det \begin{pmatrix}-\lambda E&-A\\A&-\lambda E\end{pmatrix} = \det(A^2 + \lambda^2 E^2) = \det(A - i \lambda E) \det(A + i \lambda E) = 0$$ Видно, что уравнению удовлетворяют $2n$ чисел $\pm i \lambda_k$ — они и будут искомыми собственными значениями.
   Ответ
   $\pm i \lambda_k$.
6. Вы — воин Света, и сегодня вам нужно победить толпу из $n$ гоблинов, каждый из которых изначально имеет $h_i$ единиц жизни $(1 \leqslant i \leqslant n$,$\,h_i\in \mathbb{Z}_n$,$\,0 < h_i < H)$. Боретесь с гоблинами вы с помощью специального магического посоха. Если ударить таким посохом по гоблину, тот сразу же теряет $p$ единиц жизни, а все остальные гоблины в толпе теряют $q$ единиц жизни каждый (таковы магические свойства посоха). Гоблин считается побежденным, если после очередного удара его здоровье становится меньше или равно нулю. Обычная борьба с нечистью давно нам приелась, и чтобы внести разнообразие в сегодняшнюю битву, вы решили победить всех гоблинов, сделав минимально возможное число ударов посохом. Предложите алгоритм нахождения этого числа ударов. Ваш алгоритм должен иметь асимптотику по времени $O(n \log n)$, затраты по памяти — $O(n)$.
7. Пусть $A$ и $B$ — две случайных булевых матрицы $n\times n$, у которых каждый элемент равен $1$ с вероятностью $p$ (значения различных элементов не зависят друг от друга). Сколько в среднем единиц будет в их произведении, если сложение и умножение происходят по модулю $2$?
8. Исследуйте на сходимость (абсолютную и условную) ряд $\sum_{k=1}^\infty a_k$, где $$a_k = \int\limits_0^{\frac{\sin k}{k}} \frac{\sin t}{t} dt.$$
   Решение
   (а) Исследуем на абсолютную сходимость.
   Разберем сначала вспомогательное утверждение: $$\left| \frac{\sin k}{k} \right| + \left| \frac{\sin (k+1)}{k+1} \right| \geqslant \frac{1}{6k},\;\; \forall k \geqslant 1.$$ Рассмотрим два случая:
   (i) $|\sin k | \geqslant \frac13 \Rightarrow$ утверждение очевидно
   (ii) $|\sin k| \leqslant \frac13$
   Рассмотрим единичную окружность и проведем две прямые: $y=\frac13$ и $y=-\frac13$. Тогда множество $|\sin k| \leqslant \frac13$ расположено на окружности между двумя этими прямыми. Из геометрических соображений можно увидеть, что при повороте этого множества на $1$ радиан, оно выйдет за пространство между прямыми. Это означает, что $|\sin(k+1)| \geqslant \frac13$ и $\left| \frac{\sin(k+1)}{k+1} \right| \geqslant \frac{1}{3(k+1)} \geqslant \frac{1}{6k}$, откуда следует исходное утверждение. В частности, из этого утверждения следует расходимость ряда $\sum\limits_{k=1}^\infty \left| \frac{\sin k}{k} \right|$.
   Попробуем теперь на основе этой идеи получить оценку на сумму абсолютных значений соседних членов исходного ряда: $$|a_k| + |a_{k+1}| = \left| \int\limits_0^{\frac{\sin k}{k}} \frac{\sin t}{t} dt \right| + \left| \int\limits_0^{\frac{\sin (k+1)}{k+1}} \frac{\sin t}{t} dt \right| = \int\limits_0^{\left| \frac{\sin k}{k} \right|} \frac{\sin t}{t} dt + \int\limits_0^{\left| \frac{\sin (k+1)}{k+1} \right|} \frac{\sin t}{t} dt.$$ (здесь мы воспользовались тем, что $\frac{\sin x}{x}$ — четная функция, первый нуль которой расположен в точках $\pm \pi$ и при интегрировании не достигается).
   Используя аналогичные рассуждения, получим: $$|a_k| + |a_{k+1}| \geqslant \int\limits_0^{\frac{1}{6k}} \frac{\sin t}{t} dt \geqslant \sin \frac{1}{6k}.$$ Воспользуемся неравенством $\sin x \geqslant \frac{2x}{\pi}$ при $x \in [0; \frac{\pi}{2}]$. Тогда получим $$|a_k| + |a_{k+1}| \geqslant \frac{1}{3\pi k},$$ и по признаку сравнения заключаем, что ряд не сходится абсолютно.
   (б) Исследуем на условную сходимость.
   Представим члены ряда в следующем виде: $$a_k = \int\limits_0^{\frac{\sin k}{k}} \frac{\sin t}{t} dt = \int\limits_0^{\frac{\sin k}{k}} 1 + O(t^2) dt = \frac{\sin k}{k} + O\left( \left( \frac{\sin k}{k} \right)^3 \right).$$ Также заметим, что $O\left( \left( \frac{\sin k}{k} \right)^3 \right)$ сходится, поскольку ряд $\left( \frac{\sin k}{k} \right)^3$ сходится абсолютно. Тогда по признаку сравнения, если ряд $\sum\limits_{k=1}^\infty \frac{\sin k}{k}$ сходится, то сходится и исходный ряд.
   Воспользуемся признаком Дирихле для сходимости рядов Абелева типа. Последовательность $\{\frac{1}{n}\}$ монотонна и стремится к нулю, осталось доказать ограниченность последовательности частичных сумм $\sum\limits_{k=1}^n \sin k$.
   Поскольку $$\sum\limits_{k=1}^n \sin k = \frac{\sin(\frac{n}{2}) \sin(\frac{n+1}{2})}{\sin(\frac{1}{2})} \leqslant \frac{1}{\sin (\frac12)},$$ получаем, что ряд сходится условно (чтобы посчитать последнюю сумму, можно домножить ее на $2\sin(\frac12)$ и расписать произведения синусов через разности косинусов).
   Ответ
   Ряд сходится условно.