21 мая 2016

1. Решите уравнение $$\lim\limits_{n\to \infty} \cos nx = 1.$$
2. Докажите, что целочисленная матрица не может иметь собственного значения, равного $\frac14 (-3 + i\sqrt{5})$.
3. В мишень, которая представляет собой прямоугольник размера $3\times 2$, стреляют из пистолета. Известно, что отклонение пули от точки, на которую нацелен пистолет, произвольно, но не превышает $0,1$ по любому направлению, параллельному сторонам прямоугольника. Стрелок целится в произвольную точку мишени. С какой вероятностью он попадет в мишень?
4. Пусть $f:\mathbb{R}^2 \to \mathbb{R}$ — ограниченная гладкая функция, причем ее среднее значение на любой окружности радиуса $1$ равно значению в центре этой окружности. Докажите, что $f$ постоянна.
   Решение
   Рассмотрим оператор, который вычисляет значение функции в некоторой точке $\vec{r}$ и вычитает среднее значение функции $f$ на окружности радиуса $1$, построенной вокруг этой точки: $$(Tf) (\vec{r}) = f(\vec{r}) - \int\limits_{0}^{1} f(\vec{r} + \vec{\tau} (s)) ds,$$ где $\vec{\tau} (s) = (\begin{array}{cc} \cos (2\pi s) & \sin (2\pi s) \end{array})^\mathrm{T}$. Найдем, как действует этот оператор при преобразовании Фурье $F$: $$T_{F} \varphi (\vec{\omega}) = F T F^{-1} \varphi (\vec{\omega}) = \left(1 - \int\limits_{0}^{1} e^{i \vec{\tau} (s) \cdot \vec{\omega}} ds \right) \varphi (\vec{\omega}) = g(\vec{\omega}) \varphi (\vec{\omega}),$$ где $\varphi (\vec{\omega})$ принадлежит пространству обобщенных функций. Мы получили, что $T_F$ является оператором умножения на гладкую функцию $g(\vec{\omega})$. Найдем нули этой функции: $$g(\vec{\omega}) = 1 - \int\limits_{0}^{1} e^{i \vec{\tau} (s) \cdot \vec{\omega}} ds = 1 - \int\limits_{0}^{1} e^{i |\vec{\omega}| (\cos \Phi \cos (2\pi s) +\sin \Phi \sin (2\pi s)}ds =$$ $$= 1 - \int\limits_{0}^{1} e^{i |\vec{\omega}| \cos (\Phi - 2\pi s)}ds = 1 - \int\limits_{0}^{1} e^{i |\vec{\omega}| \cos (2\pi s)}ds =$$ $$= 1 - \int\limits_{0}^{1/2} e^{i |\vec{\omega}| \cos (2\pi s)} ds - \int\limits_{0}^{1/2} e^{-i |\vec{\omega}| \cos (2\pi s)}ds = 1 - 2 \int\limits_{0}^{1/2} \cos(|\vec{\omega}| \cos (2\pi s))ds.$$ За $\Phi$ мы обозначили угол между декартовыми компонентами $\vec{\omega}$. В дальнейшем он исчезает, поскольку интеграл берется по всему периоду периодической функции. Произведем замену $u = \cos (2\pi s)$. Тогда $$g(\vec{\omega}) = 1 + \frac{1}{\pi} \int\limits_{1}^{-1} \frac{\cos(|\vec{\omega}| u) du}{\sqrt{1 - u^2}} = 1 - \frac{2}{\pi} \int\limits_{0}^{1} \frac{\cos(|\vec{\omega}| u) du}{\sqrt{1 - u^2}} =$$ $$= \frac{2}{\pi} \int\limits_0^1 \frac{(1 - \cos(|\vec{\omega}| u) du}{\sqrt{1 - u^2}}.$$ Отсюда видно, что $g(\vec{\omega})$ имеет единственный нуль в точке $\vec{\omega} = 0$. Найдем порядок этого нуля. Нетрудно разложить $g(\vec{\omega})$ в ряд Маклорена с остаточным членом в форме Пеано: $$g(\vec{\omega}) = \frac{2}{\pi} \int\limits_0^1 \left(\frac{\vec{\omega}^2u^2}{2} + O(\vec{\omega}^2u^2) \right) \frac{du}{\sqrt{1 - u^2}} = \frac14 \vec{\omega}^2 + O(\vec{\omega}^2).$$ Таким образом, порядок нуля равен двум. Отсюда следует, что $\text{ker}\, (T_F)$ состоит из линейной оболочки $\delta(\vec{\omega})$ и $\delta'(\vec{\omega})$. При обратном преобразовании Фурье эта оболочка соответствует множеству функций вида $f = Ax + By + C$. Поскольку только константа из них ограничена, утверждение задачи доказано.
   Решение 2
   Предположим, что функция $f$ не постоянна. Если $f$ не содержит положительных значений, отразим для удобства $f(\vec{r}) \to -f(\vec{r})$. Рассмотрим два случая.
   1. Функция $f$ удовлетворяет условию Липшица: $$\exists L \colon \forall \vec{r}_i, \vec{r}_j \,\, |f(\vec{r}_j) - f(\vec{r}_i)| \leqslant L|\vec{r}_j - \vec{r}_i|.$$ Выберем такой вектор $\vec{h}$, что $|\vec{h}| = 1$. Рассмотрим функцию $$g(\vec{r}) = f(\vec{r} + \vec{h}) - f(\vec{r}),$$ которая также удовлетворяет условиям задачи и условию Липшица с константой $K=2L$. Пусть $M = \sup g(\vec{r}) > 0$. Выберем $\varepsilon_0 > 0$ и $\vec{r}_0$ такими, что $$M - \varepsilon_0 < g(\vec{r}_0) \leqslant M.$$ Тогда $$g(\vec{r_0}) = \int\limits_{0}^{\xi} g(\vec{r_0} + \vec{\tau} (s)) ds + \int\limits_{\xi}^{1} g(\vec{r_0} + \vec{\tau} (s)) ds,$$ где $\vec{\tau} (s) = (\begin{array}{cc} \cos (2\pi s) & \sin (2\pi s) \end{array})^\mathrm{T}$, $0 < \xi < 1$.
   Далее $$g(\vec{r_0}) \leqslant \int\limits_{0}^{\xi} (g(\vec{r_0} + \vec{h}) + 2\pi K\xi) ds + \int\limits_{\xi}^{1} M ds = \xi g(\vec{r_0} + \vec{h}) + 2\pi K\xi^2 + M(1-\xi).$$ $$g(\vec{r}_0 + \vec{h}) \geqslant M - \frac{1}{\xi} (M - g(\vec{r}_0)) - 2\pi K\xi.$$ Выберем $\xi = \sqrt{\frac{M - g(\vec{r}_0)}{2\pi K}}$ (важно только, чтобы $\varepsilon_0$ был достаточно мал для $\xi < 1$; также заметим, что в случае $M = g(\vec{r}_0)$ мы легко придем к противоречию, поэтому $\xi > 0$). Отсюда $$g(\vec{r}_0 + \vec{h}) \geqslant M - \sqrt{2\pi (M - g(\vec{r}_0))K} = M - \sqrt{2\pi \varepsilon_0 K}.$$ Продолжая рассуждения по индукции, получим: $$g(\vec{r}_0 + n\vec{h}) \geqslant M - \varepsilon_n,\,\, \varepsilon_{n} = \sqrt{2\pi \varepsilon_{n-1} K}.$$ Таким образом, $$f(\vec{r}_0 + n\vec{h}) - f(\vec{r}_0) = \sum\limits_{k=1}^{n} g(\vec{r}_0 + k\vec{h}) \geqslant nM - \sum\limits_{k=1}^{n} \varepsilon_k,$$ что приводит к противоречию, поскольку $\sum\limits_{k=1}^{n} \varepsilon_k$ мы можем сделать сколь угодно малым уменьшая $\varepsilon_0$ (и при необходимости сдвигая $\vec{r}_0$), а значит, функция не ограничена.
   2. Функция $f$ не удовлетворяет условию Липшица.
   Рассмотрим функцию: $$\tilde{f} (\vec{r}) = \frac{1}{|D_a|} \int\limits_{D_a} f(\vec{r} + \vec{v}) d^2\vec{v},$$ где $D_a$ — диск радиуса $a$. Заметим, что нам достаточно доказать, что $\tilde{f} (\vec{r})$ постоянна для всех конечных $a$. Тогда в пределе $a \to 0$ мы получим, что и $f$ постоянна. Покажем, что функция $\tilde{f}$ удовлетворяет условиям задачи. Очевидно, что $\tilde{f}$ ограниченная и гладкая. Далее $$\int\limits_0^1 \tilde{f} (\vec{r} + \vec{\tau} (s)) ds = \frac{1}{|D_a|} \int\limits_0^1 \int\limits_{D_a} f(\vec{r} + \vec{v} + \vec{\tau} (s)) d^2\vec{v} ds =$$ $$= \frac{2\pi}{|D_a|} \int\limits_0^1 \int\limits_{0}^{a} \int\limits_{0}^1 f(\vec{r} + p\vec{\tau} (s') + \vec{\tau} (s)) ds' dp ds =$$ $$= \frac{2\pi}{|D_a|} \int\limits_{0}^{a} \int\limits_0^1 f(\vec{r} + p\vec{\tau} (s')) ds' dp = \tilde{f} (\vec{r}).$$ Поскольку производные $\tilde{f} (\vec{r})$ ограничены, она удовлетворяет условию Липшица. Тогда по первому пункту решения эта функция постоянна, что доказывает исходное утверждение.
5. Дана матрица $n\times n$, каждая строка и каждый столбец которой упорядочены по возрастанию (то есть $a_{ki} < a_{kj}$ и $a_{it} < a_{jt}$ при $i<j$). Предложите алгоритм, находящий два элемента этой матрицы, сумма которых наиболее близка к заданному числу $q$. Ограничение по дополнительной памяти — $O(n)$. Изменять исходную матрицу нельзя. Внимание: оценка будет зависеть от эффективности вашего алгоритма.
6. Робот движется по клеткам бесконечной шахматной доски. Один его шаг — это перемещение на случайную из восьми соседних клеток. Найдите математическое ожидание модуля разности между количеством черных и количеством белых клеток, на которых робот побывал за $n$ шагов (каждая клетка считается столько раз, сколько на ней побывал робот). Ответ представьте в виде компактного выражения.
7. Пусть $J \in \mathrm{Mat}_{2n\times 2n} (\mathbb{R})$ — кососимметрическая матрица, $\beta$ — положительное число, а $u \in \mathbb{R}^{2n}$ — ненулевой вектор. Найдите $\mathrm{det}\;(E + \beta u u^{\mathrm{T}} J)$.
   Решение
   Воспользуемся известным фактом, что определитель матрицы равен произведению ее собственных значений. Отсюда следует, что если мы найдем собственные значения матрицы $u u^{\mathrm{T}} J$ (обозначим их как $\lambda_i$), то определитель исходной матрицы будет равен $\prod\limits_i (1 + \beta \lambda_i)$.
   Для нахождения собственных значений матрицы $u u^{\mathrm{T}} J$ воспользуемся ассоциативностью произведения матриц. Заметим, что если мы умножим матрицу на произвольный вектор $(u u^{\mathrm{T}} J) h = u (u^{\mathrm{T}} J h)$, то в случае $u^{\mathrm{T}} J h \neq 0$ получившийся вектор будет коллинеарен вектору $u$.
   Отсюда следует, что
   (а) $u$ — собственный вектор с собственным значением $u^{\mathrm{T}} J u$,
   (б) все собственные значения кроме, возможно, $u^{\mathrm{T}} J u$ равны $0$.
   Функция $u^{\mathrm{T}} J u$ представляет собой квадратичную форму с нулевой матрицей, поскольку матрица $J$ кососимметрична. Значит, все собственные значения $u u^{\mathrm{T}} J$ равны нулю. Таким образом, определитель исходной матрицы равен $1$.
   Ответ
   $1$.
8. Докажите, что из последовательности из $mn+1$ различных действительных чисел всегда можно выделить возрастающую подпоследовательность из $n+1$ числа или убывающую подпоследовательность из $m+1$ числа.