3 июня 2012

1. Определим последовательность $\{x_n\}$ начальными условиями $x_1=a$, $x_2=b$ и рекуррентной формулой $x_{n+1} = \frac12 (x_n + x_{n-1})$. Найдите $\lim\limits_{n\to \infty} x_n$.
   Решение
   Будем искать решение в виде $x_n = \lambda^n$. Тогда $\lambda^{n+1} = \frac12 (\lambda^n + \lambda^{n-1})$. Поделив на $\lambda^{n-1}$ получим $$\lambda^2 = \frac12 (\lambda + 1) \Leftrightarrow (\lambda -1)(\lambda + \frac12) = 0.$$ Таким образом, мы нашли решения $x_n=1$ и $x_n = \left( -\frac12 \right)^n$. Из линейности рекуррентного соотношения общее решение можно записать в виде $$x_n = C_1 + C_2 \left(-\frac12 \right)^n.$$ Подставим начальные условия $x_1=a$ и $x_2=b$. Тогда $$x_n = \frac13 (a+2b) + \frac43 (b-a) \left( -\frac12 \right)^n.$$ Переходя к пределу $n \to \infty$, получаем $\frac13 (a+2b)$.
   Ответ
   $\dfrac13 (a+2b)$.
2. Рассмотрим функцию $\varphi(x) = \sum\limits_{k=1}^\infty \frac{1}{2^{2[\log_2 k]}} x^k$, где квадратные скобки означают целую часть числа. Найдите $\int\limits_0^1 \varphi(x) \varphi'(x) dx$.
   Решение
   Нетрудно показать, что $\int \varphi(x) \varphi'(x) dx = \frac{\varphi^2 (x)}{2} + C$. Тогда $$\int\limits_0^1 \varphi(x) \varphi'(x) dx = \frac{\varphi^2 (1)}{2} - \frac{\varphi^2 (0)}{2} = \frac{\varphi^2 (1)}{2}.$$ Найдем $\varphi(1) = \sum\limits_{k=1}^\infty \frac{1}{2^{2[\log_2 k]}}$. Число $[\log_2 k]$ равно количеству значащих разрядов в двоичной записи числа $k$, а значит, оно меняется от $s$ до $s+1$ через $2^s$ членов ряда. Таким образом $$\varphi(1) = \sum\limits_{s=0}^\infty \frac{2^s}{2^{2s}} = \sum\limits_{s=0}^\infty \frac{1}{2^s} = 2.$$ И окончательно получим $\int\limits_0^1 \varphi(x) \varphi'(x) dx = 2$.
   Ответ
   $2$.
3. Рассмотрим всевозможные непустые подмножества множества $\{1,2,3,\ldots, n\}$. В каждом подмножестве перемножим числа, обратные его элементам. Потом сложим полученное $2^n - 1$ число. Найдите полученную сумму.
   Решение
   Докажем по индукции, что $S_n = n$.
   База индукции, $n=1$. Тогда $S_1 = 1$.
   Переход: предположим, что $S_k = k$. Тогда $$S_{k+1} = \frac{1}{k+1} + \frac{1}{k+1} S_k + S_k = \frac{1 + k + k(k+1)}{k+1} = k+1.$$
   Решение 2
   Заметим, что такая сумма равна $$\left( 1 + \frac11 \right) \left( 1 + \frac12 \right) \cdots \left( 1 + \frac{1}{n} \right) - 1.$$ В самом деле, в результате раскрытия скобок мы получим все возможные комбинации произведений обратных элементов. Приведем слагаемые в скобках к общему знаменателю. Тогда $$\frac21 \frac32 \cdots \frac{n+1}{n} - 1 = n+1 - 1 = n.$$
   Ответ
   $n$.
4. Улоф Пальме и Рави Шанкар подбрасывают правильную монетку (вероятность выпадения орла $0.5$). Улоф подбрасывает ее $n$ раз, а Рави — $n+1$. Найдите вероятность того, что у Рави будет больше орлов, чем у Улофа.
   Решение
   Пусть Улоф и Рави кинули монетку по $n$ раз. Обозначим вероятности возможных событий следующим образом:
   1. У Рави выпало больше орлов, чем у Улофа — $p$
   2. У Улофа выпало больше орлов, чем у Рави — $p$
   3. У Рави и Улофа одинаковое количество орлов — $1-2p$
   Есть только два возможных случая, в которых у Рави, после того как он подросил монетку в $(n+1)$-й раз, орлов будет больше, чем у Улофа:
   1. У Рави было больше орлов, чем у Улофа, и после $(n+1)$-го броска соотношение не поменялось — $p$
   2. У Рави и Улофа было одинаковое количество орлов и в $(n+1)$-й бросок выпал орел — $\frac12 (1-2p)$
   Поскольку два последних события несовместны, искомая вероятность равна $p + \frac12 (1-2p) = \frac12$.
   Ответ
   $\dfrac12$.
5. Дано некоторое множество положительных чисел мощности континуум. Докажите, что из него можно выбрать счетное подмножество с бесконечной суммой.
   Решение
   Покроем данное множество $M$ счетным числом подмножеств: $$M = \bigcup_{n=1}^\infty \left(M \cap \left[ \frac{1}{n}; \infty \right)\right).$$ Заметим, что хотя бы одно такое подмножество $A_N = M \cap [ \frac{1}{N}; \infty )$ должно иметь мощность континуум, поскольку в противном случае множество $M$ счетно как объединение счетного числа счетных множеств. Но в таком множестве будет континуум элементов, которые больше (или равны) некоторого числа $\frac{1}{N}$. А значит, любое счетное подмножество $A_N$ будет с бесконечной суммой.
6. Дан массив из $n$ чисел. Предложите алгоритм, позволяющий за $O(n)$ операций определить, является ли этот массив перестановкой чисел от $1$ до $n$. Дополнительной памяти не более $O(1)$.
   Решение
   Идея состоит в том, чтобы рассматривать массив $A$ как подстановку. Пусть индекс $i$ пробегает значения от $0$ до $n-1$. Когда мы встречаем положительный элемент $A[i]$, переходим от него к элементу $A[A[i]-1]$, от элемента $A[A[i]-1]$ к элементу $A[A[A[i]-1]-1]$ и так далее, пока мы не не вернемся к $A[i]$, либо не сможем совершить очередной шаг (в таком случае, массив перестановкой не является). В процессе меняем знак всех пройденных элементов на отрицательный. Поскольку на каждом элементе массива мы можем оказаться максимум два раза, итоговая сложность — $O(n)$. Дополнительная память — $O(1)$.
7. Пусть $A_1, A_2, \ldots, A_n$ — конечные множества и $a_{ij} = |A_i \cap A_j|$. Докажите, что матрица $(a_{ij})_{i=1,2,\ldots,n}^{j=1,2,\ldots,n}$ неотрицательно определена.
   Решение
   Рассмотрим все возможные элементы $x \in A_1 \cup A_2 \cup \cdots \cup A_n$. Для каждого из этих элементов построим матрицу $B_x$ следующим образом: $$(B_x)_{ij} = \begin{cases}1,&\textrm{если }x \in A_i \cap A_j;\\0,&\textrm{иначе}.\end{cases}$$ В таком случае матрица $a$ будет являться суммой всех матриц $B_x$.
   
   Лемма. Определитель всех главных миноров $B_x$ равен $0$ либо $1$.
   
   Доказательство. Заметим, что если элемент $x$ не содержится в некотором множестве $A_k$, то $k$-ая строка и $k$-й столбец матрицы $B_x$ будут состоять из нулей. Ненулевые же строки и столбцы матрицы $B_x$ одинаковы. Пусть в главном миноре на некотором месте стоит $0$. Но тогда в этом миноре есть строка или столбец полностью состоящие из нулей, тогда определитель такого минора равен нулю. Если же нулей нет, такой минор состоит полностью из единиц. Для минора размером $1 \times 1$ определитель равен единице, для всех же остальных миноров из единиц он равен нулю, поскольку их строки/столбцы линейно зависимы. Лемма доказана.
   
   Поскольку определитель всех главных миноров неотрицателен, в соответствии с критерием Сильвестра неотрицательно определена и сама матрица $B_x$. Но тогда и матрица $a$ неотрицательно определена как сумма неотрицательно определенных матриц.