26 мая 2013

1. Последовательность $\{x_n\}_{n=0}^\infty$ задана рекуррентным соотношением: $$x_0=0,\; x_1=1,\; x_{n+1}=\frac{x_n + nx_{n-1}}{n+1}.$$ Покажите, что данная последовательность сходится и найдите ее предел.
   Решение
   Заметим, что $$x_{k+1} - x_k = \frac{x_k + kx_{k-1}}{k+1} - x_k = \frac{k}{k+1} (x_{k-1} - x_k) =$$ $$= \frac{-k}{k+1} (x_k - x_{k-1}) = \frac{(-1)^k}{k+1} (x_1 - x_0) = \frac{(-1)^k}{k+1}.$$ Поскольку $$\lim_{k \to \infty} (x_{k+1} - x_k) \to 0,$$ ряд сходится.
   Найдем теперь члены ряда: $$x_n = \sum_{k=1}^n (x_k - x_{k-1}) = \sum_{k=1}^n \frac{(-1)^{k+1}}{k}.$$
   Поскольку $$\ln(t + 1) = \sum_{k=1}^\infty \frac{(-1)^{k+1}t^k}{k},$$ находим, что $$\lim_{n \to \infty} x_n = \ln 2.$$
   Решение 2
   Пусть $G(t)$ — производящая функция последовательности: $$G(t) = \sum_{k=0}^\infty x_k t^k.$$ Умножим каждое равенство в условии на $t^0, t^1, \ldots, t^k, \ldots$: \begin{align*} t^0 x_0 &= 0\\ t^1 x_1 &= t\\ \cdots&\\ t^k x_k &= t^k \left( \frac{x_{k-1} + (k-1)x_{k-2}}{k} \right)\\ \cdots& \end{align*} Просуммируем эти равенства и возьмем производную: $$G'(t) = 1 + G(t) + 2tG(t) + t^2G'(t) - tG(t).$$ Решаем дифференциальное уравнение на $G(t)$: $$G'(t)(t^2 - 1) + G(t)(t+1) = -1.$$ $$[G(t)(t-1)]'(t+1) = -1.$$ $$G(t) = \frac{C}{1-t} + \frac{\ln (t+1)}{1-t}.$$ Поскольку $G(0) = 0$: $$G(t) = \frac{\ln (t+1)}{1-t}.$$ Теперь мы можем найти члены последовательности, посмотрев на разложение $G(t)$ в ряд Тейлора: $$G(t) = (t - \frac{t^2}{2} + \frac{t^3}{3} - \cdots)(1 + t + t^2 + \cdots).$$ Тогда $$x_n = \sum_{k=1}^n \frac{(-1)^{k+1}}{k}.$$ Поскольку $$\ln(t + 1) = \sum_{k=1}^\infty \frac{(-1)^{k+1}t^k}{k},$$ понятно, что $$\lim_{n \to \infty} x_n = \ln 2.$$
   Ответ
   $\ln 2.$
2. Имеется $100$ некоторых подмножеств множества $\{0,1, \ldots, 9\}$. Докажите, что среди них найдется два подмножества, у которых симметрическая разность имеет мощность не более двух.
   Решение
   Будем решать задачу от противного. Предположим, что у любой пары подмножеств из условия мощность симметрической разности больше двух. Возьмем тогда некоторую пару различных подмножеств $A$ и $B$. Назовем $f(A)$ и $f(B)$ все возможные подмножества, у которых мощность симметрической разности с ними равна одному (эти подмножества не входят в $100$). Ясно, что $|f(A)| = |f(B)| = 10$. Докажем, что $f(A)$ и $f(B)$ не пересекаются. В самом деле, пусть есть некоторое подмножество $C$, которое принадлежит $f(A)$ и $f(B)$ одновременно, то есть $|C \bigtriangleup A| = 1$ и $|C \bigtriangleup B| = 1$. Но тогда $|A \bigtriangleup B| = 2$, чего быть не может. Далее, поскольку для любой пары множеств $f(A)$ и $f(B)$ не пересекаются, то каждому множеству (из $100$) можно поставить в соответствие $10$ других множеств (не из $100$). Таким образом, общее число подмножеств должно быть как минимум $11 \times 100 = 1100$. Но а нас есть только $2^{10} = 1024$ подмножества.
   Примечание. Данное решение можно сформулировать более красиво, если рассмотреть представления подмножеств в $10$-мерном бинарном пространстве $\{0, 1\}^{10}$, где стоит $1$ если элемент принадлежит подмножеству и $0$ в противном случае. Расстоянием между элементами пространства назовем расстояние Хэмминга, то есть число позиций, в которых соответствующие символы различны. Тогда единичная сфера в таком пространстве состоит из $10$ точек, а если мы поместим в это пространство $100$ точек, какие-то две сферы вокруг них должны пересечься. Центры таких сфер соответствуют подмножествам, у которых симметрическая разность имеет мощность не более двух.
3. На единичной окружности $\{x^2+y^2=1\}$ выбирается случайная точка $P$ (из равномерного распределения). В единичном круге $\{x^2 + y^2 \leqslant 1\}$ выбирается случайная точка $Q$ (также из равномерного распределения). Пусть $R$ — прямоугольник со сторонами, параллельными осям координат и диагональю $PQ$. Какова вероятность того, что весь прямоугольник лежит в единичном круге?
   Решение
   Заметим, что для того, чтобы прямоугольник лежал в единичном круге, нужно, чтобы точка $Q$ попала в прямоугольник, образованный точкой $P$ и ее отражениями относительно осей. Пусть точка $P$ задается углом $\varphi \in [0, \pi/2]$ (остальные случаи симметричны). Тогда ее плотность вероятности равна $\rho(\varphi) = \frac{2}{\pi}$. Условная вероятность попадания в прямоугольник равна площади прямоугольника $2\sin(2\varphi)$, деленной на площадь круга $\pi$. Тогда искомая вероятность равна интегралу $$\frac{4}{\pi^2} \int_0^{\pi/2} \sin(2\varphi) d\varphi = \frac{4}{\pi^2}.$$
   Ответ
   $\dfrac{4}{\pi^2}.$
4. Пусть $f$ — положительная непрерывная функция на $\mathbb{R}$, причем $\int\limits_{-\infty}^\infty f(x) dx = 1$. Пусть $\alpha \in (0,1)$, а интервал $[a;b]$ — это интервал минимальной длины из тех, для которых $\int\limits_a^b f(x) dx = \alpha$. Покажите, что $f(a)=f(b)$.
   Решение
   Рассмотрим функцию $F(t) = \int\limits_{a+t}^{b+t} f(x) dx$. Если $f(a) \neq f(b)$, $F(t)$ будет строго монотонной в окрестности $t=0$. Тогда существует такое $\Delta t$, что $F(\Delta t) > F(0)$. В таком случае мы можем уменьшить длину промежутка $[a+\Delta t; b + \Delta t]$ и получить $\alpha$, а значит, интервал $[a;b]$ был не минимальным.
5. Дана матрица $M$ размера $n\times n$, где $m_{ij}=a_i a_j$ при $i\neq j$ и $m_{ii} = {a_i}^2 + k,\; i,j=1,\ldots,n$. Найдите определитель матрицы $M$.
   Решение
   Матрицу $M$ можно представить в виде $M = uu^{\mathrm{T}} + kE$, где $u^{\mathrm{T}} = \begin{pmatrix}a_1&a_2&\cdots &a_n \end{pmatrix}$, а $E$ — единичная матрица. Тогда если $\{\lambda_i\}$ — собственные значения матрицы $uu^{\mathrm{T}}$, то $$\textrm{det}\, M = \textrm{det}\, (uu^{\mathrm{T}} + kE) = \prod\limits_i (\lambda_i + k).$$ Найдем собственные значения $uu^{\mathrm{T}}$. Заметим, что $(u u^{\mathrm{T}})x = u u^{\mathrm{T}} x = (u,x)u$. Пространство $V$, на котором действует $uu^{\mathrm{T}}$, раскладывается в прямую сумму $V = < u > \oplus {< u >}^\perp$. Нетрудно видеть, что оба слагаемых являются собственными подпространствами для $u u^{\mathrm{T}}$ с собственными значениями $u^{\mathrm{T}} u = \sum\limits_{i=1}^n a_i^2$ и $0$. Отсюда окончательно получим $$\textrm{det}\, M = k^{n-1} \left( k + \sum_{i=1}^n a_i^2 \right).$$
   Ответ
   $k^{n-1} \left( k + \sum\limits_{i=1}^n a_i^2 \right).$
6. Задана битовая матрица $n\times n$ с элементами $0$ и $1$ (каждый элемент матрицы занимает один бит памяти). Назовем строку (столбец) исходной матрицы плохой (плохим), если в нем встречается хотя бы один ноль. Необходимо в исходной матрице занулить все плохие строки и столбцы. Предложите алгоритм, решающий эту задачу за $O(1)$ дополнительной памяти и оцените его временную стоимость.
   Решение
   1) Посмотрим на первую строку и первый столбец матрицы. Запомним, хорошие они или плохие. На это потребуется $O(n)$ времени и $2$ бита дополнительной памяти.
   2) Пройдемся по оставшейся части матрицы $i=2\ldots n$, $j=2\ldots n$. Если $a_{ij} = 0$, занулим $a_{i1}$ и $a_{1j}$. Таким образом, в первой строке (столбце) будут стоять единицы, если вся строка (столбец) хорошие и наоборот. Этот шаг занимает $O(n^2)$ по времени, дополнительной памяти не требуется.
   3) Пройдемся по этой же матрице еще раз. Если $a_{i1} = 0$ либо $a_{1j} = 0$, занулим $a_{ij}$. В результате этих манипуляций мы выполнили условия задачи для всей матрицы, кроме, возможно, первой строки (столбца). Этот шаг также занимает $O(n^2)$ по времени.
   4) Используя результат пункта 1 приведем первую строку (столбец) в соответствии с условиями задачи. Это займет $O(n)$ по времени.
   Таким образом, мы решили задачу за $O(n^2)$ по времени и за $O(1)$ дополнительной памяти.
7. Рассмотрим линейное пространство многочленов над $\mathbb{R}$ от двух переменных степени не выше $2013$. Рассмотрим его подпространство $V$, образованное всеми многочленами $f$, для которых криволинейный интеграл первого рода $\oint\limits_{\{x^2+y^2=R^2\}} f(x,y) ds = 0$, причем для любого $R$. Найдите размерность подпространства $V$.
   Решение
   Запишем многочлен от двух переменных в общем случае: $$f(x, y) = \sum a_{nm} x^n y^m$$ Распишем интеграл по окружности: $$\oint\limits_{\{x^2+y^2=R^2\}} f(x,y) ds = \int\limits_0^{2\pi} \sum a_{nm} (R\cos \varphi)^n (R\sin \varphi)^m d\varphi =$$ $$= \sum a_{nm} R^{n+m} \int\limits_0^{2\pi} (\cos \varphi)^n (\sin \varphi)^m d\varphi = 0.$$ Если мы хотим, чтобы это равенство было выполнено для любого $R$, коэффициенты при различных степенях $R$ должны быть равны нулю. Рассмотрим более подробно интеграл $$c_{nm} = \int\limits_0^{2\pi} (\cos \varphi)^n (\sin \varphi)^m d\varphi.$$ Заметим, что $c_{nm} = c_{mn}$, поскольку нам не важно в какой точке окружности мы начнем интегрировать (более формально: сделаем замену $\varphi = \frac{\pi}{2} - \alpha$ и прибавим $\frac{3\pi}{2}$ к каждому пределу интегрирования).
   
   У нас есть три случая:
   1) $n$ и $m$ четные. Тогда подынтегральное выражение всегда неотрицательно, поэтому $c_{nm} > 0$.
   2) $n$ и $m$ имеют разную четность. Поскольку $c_{nm} = c_{mn}$, достаточно рассмотреть случай, в котором $n$ — четное, а $m$ — нечетное. Тогда подыинтегральное выражение антисимметрично относительно точки $\pi$, поэтому $c_{nm} = 0$.
   3) $n$ и $m$ нечетные. Тогда интеграл можно разбить на два участка: от $0$ до $\pi$ и от $\pi$ до $2\pi$. На каждом из этих участков подынтегральное выражение антисимметрично относительно центра ($\frac{\pi}{2}$ и $\frac{3\pi}{2}$ соответственно), поэтому $c_{nm} = 0$.
   (Если эти рассуждения не совсем понятны, попробуйте нарисовать графики $\sin x$, $\cos x$, $\sin^2 x$ и $\cos^2 x$. Более старшие степени только деформируют эти графики, не меняя указанных симметрий. Попробуйте понять, как выглядят графики их произведений.)
   
   Таким образом, $c_{nm}$ не равен нулю только когда $n$ и $m$ четные. Тогда в базисный набор мы сразу можем включить все одночлены $x^n y^m$, у которых $n$ и $m$ имеют разную четность либо оба нечетные. Но это еще не все возможные базисы. Несмотря на то, что для четных $n$ и $m$ коэффициенты $c_{nm}$ больше нуля, их линейная комбинация при одинаковой степени все равно может дать нуль. Это соответствует линейному ограничению на коэффициенты для четных степеней $R$, а значит уменьшает число базисных одночленов на $1$ от всех возможных для каждой такой степени.
   
   Посчитаем число одночленов от двух переменных степени не выше $s$. Есть $1$ одночлен степени $0$, $2$ одночлена степени $1$ и так далее. Общее число одночленов равно $$1 + 2 + \cdots + (s+1) = \frac{(s+1)(s+2)}{2}.$$ Число возможных четных степеней $R$ равно $\lfloor \frac{s}{2} \rfloor + 1$. Таким образом, размерность подпространства $V$ равна: $$\text{dim}\, V = \frac{(s+1)(s+2)}{2} - \lfloor \frac{s}{2} \rfloor - 1 = \frac{s(s+3)}{2} - \lfloor \frac{s}{2} \rfloor.$$ Для случая $s = 2013$ получим $\text{dim}\, V = 2\,028\,098$.
   
   Примечение. Выпишем явно базисные одночлены для первых $s$. Поскольку для очередного $s$ можно использовать предыдущий базис, будем выписывать только новые одночлены:

   $s$	Размерность $V$	С разной четностью и нечетные	Четные
   $1$	$2$	$x$, $y$
   $2$	$4$	$xy$	$x^2 - y^2$
   $3$	$8$	$x^3$, $y^3$, $x^2y$, $xy^2$
   $4$	$12$	$x^3y$, $xy^3$	$x^4 - 3x^2y^2$, $y^4 - 3x^2y^2$
   $5$	$18$	$x^5$, $y^5$, $x^4y$, $xy^4$, $x^2y^3$, $x^3y^2$

   
   Покажем, как получился, например, базис для $n=4$. При $R^4$ в разложении интеграла от произвольного многочлена стоит следующее выражение: $$a_{40} c_{40} + a_{04} c_{04} + a_{31} c_{31} + a_{13} c_{13} + a_{22} c_{22} = a_{40} c_{40} + a_{04} c_{04} + a_{22} c_{22}.$$ Условие на коэффициенты: $$a_{40} c_{40} + a_{04} c_{04} + a_{22} c_{22} = 0.$$ Подставим в разложение $$a_{40} x^4 + a_{04} y^4 + a_{22} x^2 y^2$$ получившееся условие: $$a_{40} \left( x^4 - \frac{c_{40}}{c_{22}} x^2y^2 \right) + a_{04} \left( y^4 - \frac{c_{04}}{c_{22}} x^2y^2 \right).$$ Нетрудно посчитать $$c_{40} = c_{04} = \frac{3\pi}{4}, \;\;\; c_{22} = \frac{\pi}{4}.$$ Поэтому выражение превращается в $$a_{40} (x^4 - 3x^2y^2) + a_{04} (y^4 - 3x^2y^2).$$
   Ответ
   $2\,028\,098.$