9 июня 2013

1. Последовательность $\{a_n\}_{n=0}^\infty$ определена рекурсивно: $$a_0=1, \;\;\;\;\;\;\; a_{n+1} = \frac{a_n}{1 + na_n}.$$ Найдите формулу общего члена последовательности.
   Решение
   Введем обозначение $b_n = \frac{1}{a_n}$. Тогда $b_{n+1} = \frac{1 + na_n}{a_n} = b_n + n$. Кроме того, $b_0 = \frac{1}{a_0} = 1$.
   Получаем, что $$b_n = b_0 + 1 + 2 + \cdots + n-1 = 1 + \frac{n(n-1)}{2} = \frac{n(n-1) + 2}{2}.$$ Отсюда получаем $$a_n = \frac{2}{n(n-1)+2}.$$
   Ответ
   $a_n = \dfrac{2}{n(n-1)+2}.$
2. Дано множество $A=\{1,2,\ldots,n\}$. Среди всех его подмножеств рановероятно выбирается $k$ его подмножеств. Найдите вероятность того, что $A_1 \cap A_2 \cap \ldots \cap A_k = \varnothing$.
   Решение
   Рассмотрим элемент $i \in A$. Очевидно, подмножеств в $A$, содержащих $i$ и не содержащих $i$, равное количество. Таким образом, вероятность того, что $i$ лежит в $A_j$ равна $\frac12$. Эти вероятности независимы для разных $j$. Получаем, что вероятность того, что $i$ содержится в $A_1 \cap A_2 \cap \ldots \cap A_k$ равна $\frac{1}{2^k}$. Соответственно, вероятность того, что $i$ не содержится в $A_1 \cap A_2 \cap \ldots \cap A_k$ равна $1 - \frac{1}{2^k}$. Эти вероятности независимы для разных $i$. Получается, что вероятность того, что ни один из номеров $i$ не попал в $A_1 \cap A_2 \cap \ldots \cap A_k$ равна $(1 - \frac{1}{2^k})^n$.
   Ответ
   $\left( 1 - \dfrac{1}{2^k} \right)^n$.
3. Дан массив длины $n$ из нулей и единиц. Найдите в нем подмассив максимальной длины, в котором количество единиц равно количеству нулей. Ограничения: $O(n)$ по времени, $O(n)$ по дополнительной памяти.
   Решение
   Обозначим исходный массив через $a$. Заведем еще четыре массива длины $n$: $b$, $c$, $d$ и $e$. Пройдем во возрастанию индексов и заполним массив $b$ по правилу $b[0] = 2a[0] - 1$, $b[i] = b[i-1] + 2a[0] - 1$ при $i>1$. Иными словами, если в массиве $a$ заменить нули на $-1$, то в массиве $b$ будут стоять суммы от $a[0]$ до $a[i]$. Заполним массивы $c$ и $d$ минус единицами. Далее идем по возрастанию номеров по массиву $b$. Если $b[i] = k$, то $d[k] = i$, если при этом выполнено $c[k] = -1$, то присваеваем $c[k]=i$.
   Далее, когда мы прошли по всему массиву $b$, заполним массив $e$ по правилу $e[i] = d[i] - c[i]$. Заметим, что если в массиве $a$ есть подмассив от $a[m]$ до $a[l]$, в котором равное количество единиц и нулей, то $b[m]=b[l]=k$. И тогда $c[k]$ — это минимальный номер $i$ такой, что $b[i]=k$, а $d[k]$ — максимальный. Соответственно, $e[k]$ — максимальное расстояние между $m$ и $l$, где $b[m] = b[l] = k$. Найдем максимум массива $e$, пусть он равен $e[j]$. Тогда искомый подмассив — это подмассив от $a[c[j]]$ до $a[d[j]]$.
4. Пусть $I_m=\int\limits_0^{2\pi} \cos (x) \cos (2x) \ldots \cos (mx) dx$. Для каких $m \in [1,10]$ $I_m \neq 0$?
   Решение
   Многократно воспользуемся формулой: $$\cos (lx) \cos (nx) = \frac12 (\cos ((l+n)x) \cos ((l-n)x)).$$ Тогда получим $$\cos (x) \cos (2x) \ldots \cos (mx) = \frac{1}{2^{m-1}} ( \cos (\alpha_1 x) + \cdots + \cos(\alpha_{2^m} x) ),$$ где $a_i = 1 \pm 2 \pm 3 \pm \cdots \pm m \in \mathbb{Z}$. Несложно убедиться, что четности всех чисел $a_i$ будут одинаковы. Более того, в случаях $m=4k$ и $m=4k+3$ все $a_i$ четны, а в случаях $m=4k+1$ и $4k+2$ — нечетны.
   Если $a_i \neq 0$, $\int\limits_0^{2\pi} \cos (\alpha_i x) dx = 0$. Значит, $I_m = 0$ при $m=4k+1$ и $m=4k+2$. Если же $m=4k$ или $4k+1$, то среди $a_i$ обязательно есть ноль, так как между числами $1,2,\ldots,m$ можно так расставить знаки «$+$» и «$-$», чтобы получился ноль.
   Действительно, $$(1-2-3+4)+(5-6-7+8) + \cdots + ((4k-3) - (4k-2) - (4k-1) + 4k) = 0,$$ $$(1+2-3)+(4-5-6+7) + \cdots + (4k - (4k+1) - (4k+2) + (4k+3)) = 0.$$ Таким образом, $I_m \neq 0$ при $m=4k$ и $4k+3$. Для $m \in [1,10]$ получим $m=3,4,7,8.$
   Ответ
   $3,4,7,8.$
5. Дан неориентированный непустой граф $G$ без петель. Пронумеруем все его вершины. Матрица смежности графа $G$ с конечным числом вершин $n$ (пронумерованных числами от $1$ до $n$) — это квадратная матрица $A$ размера $n$, в которой значение элемента $a_{ij}$ равно числу ребер из $i$-й вершины графа в $j$-ю вершину. Докажите, что матрица $A$ имеет отрицательное собственное значение.
   Решение
   Заметим, что $A$ — симметрическая ненулевая матрица с неотрицательными элементами и нулями на диагонали. Докажем, что у такой матрицы есть отрицательное собственное значение.
   Известный факт, что симметрическая матрица диагонализуема в вещественном базисе (все собственные значения вещественны). Допустим, что все собственные значения $A$ неотрицательны. Рассмотрим квадратичную форму $q$ с матрицей $A$ в базисе $\{e_1, \ldots, e_n\}$. Тогда эта квадратичная форма неотрицательно определена, так как все собственные значения неотрицательны. То есть $\forall v\colon q(v) \geqslant 0$. С другой стороны, пусть $a_{ij} \neq 0$. Тогда $q(e_i - e_j) = a_{ii} - 2a_{ij} + a_{jj} = -2a_{ij} < 0$. Это противоречит неотрицательной определенности $q$. Значит, исходное предположение неверно, и у $A$ есть отрицательное собственное значение.
6. Рассмотрим бесконечный двумерный массив $\{a_{ij}\}_{i,j=1}^{\infty}$, состоящий из натуральных чисел, причем каждое число встречается в массиве ровно $8$ раз. Докажите, что $\exists (m,n) \colon a_{mn} > mn$.
   Решение
   Допустим, что $\forall (m,n) \colon a_{mn} \leqslant mn$. Выберем некоторое $k \in \mathbb{N}$ и рассмотрим кривую на плоскости $y=\frac{1}{k} x$. Если $i,j \in \mathbb{N}$ и точка $(i,j)$ лежит под кривой $y = \frac{1}{k} x$, то $a_{ij} \leqslant ij \leqslant i \cdot \frac{k}{i} = k$. Таким образом, количество целых точек под кривой $y = \frac{1}{k} x$ должно быть не больше $8k$. С другой стороны, количество целых точек под этой кривой не меньше, чем $\int\limits_2^k \frac{kdx}{x} = k \ln x |_2^k = k(\ln k - \ln 2)$. При достаточно большом $k$ это число больше $8k$. Таким образом, мы получаем противоречие. Следовательно, найдется пара $(m,n)$ такая, что $a_{mn} > mn$.
7. Дана матрица из нулей и единиц, причем для каждой строки матрицы верно следующее: если в строке есть единицы, то они все идут подряд (неразрывной группой из единиц). Докажите, что определитель такой матрицы может быть равен только $\pm 1$ или $0$.
   Решение
   Переставляя строки, мы можем добиться того, чтобы позиции первых (слева) единиц не убывали сверху вниз. При этом определитель либо не изменится, либо поменяет знак. Если у двух строк позиции первых единиц совпадают, то вычтем ту, в которой меньше единиц из той, в которой больше. Определитель при этом не меняется. Такими операциями мы можем добиться того, что позиции первых единиц строго возрастают сверху вниз. При этом либо матрица окажется вырожденной, либо верхнетреугольной с единицами на диагонали. То есть, определитель станет либо $0$, либо $1$. Так как определитель при наших операциях либо не менялся, либо поменял знак, изначальный определитель был $\pm 1$ или $0$.