7 апреля 2013 (Новосибирск)

1. Рассмотрим функцию $\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$.
2. Улоф Пальме и Рави Шанкар подбрасывают правильную монетку (вероятность выпадения орла $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$.
3. Определим последовательность $\{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)$.
4. Найдите математическое ожидание числа неподвижных точек для случайной перестановки на $n$ элементах.
   Решение
   Рассмотрим индикаторные случайные величины: $$X_i = \begin{cases} 1,& \text{если } \sigma_i = i,\\0,& \text{иначе} \end{cases}.$$ Тогда число $X$ неподвижных точек подстановки $\sigma$ равно сумме $X_1 + X_2 + \cdots + X_n$.
   Найдем математическое ожидание каждого из слагаемых: $$M(X_1) = 0 \cdot P(X_1=0) + 1 \cdot P(X_1=1) = P(X_1=1)=P(\sigma_i=i)=\frac{1}{n}.$$ В самом деле, элемент $i$ фиксирует $(n-1)!$ перестановок.
   Теперь воспользуемся линейностью матожидания: $$M(X) = M(X_1 + X_2 + \cdots + X_n) = M(X_1) + M(X_2) + \cdots + M(X_n) = n \cdot \frac{1}{n} = 1.$$
   Ответ
   $1$.
5. Верно ли, что $\mathrm{rank}\,AB = \mathrm{rank}\,BA$ для любых квадратных матриц $A$ и $B$?
   Решение
   Пусть $A = \begin{pmatrix}0&1\\0&0\end{pmatrix}$, а $B = \begin{pmatrix}1&0\\0&0\end{pmatrix}$. Тогда $\mathrm{rank}\,AB = 0$, но $\mathrm{rank}\,BA = 1$.
   Ответ
   Не верно.
6. Есть круговая трасса, на которой в некоторых местах стоят бензоколонки. Расстояние между ними и количество бензина на каждой бензоколонке известны. Имеется также машина с постоянным и известным расходом топлива. Предложите алгоритм, работающий за $O(n)$ по времени, который позволяет найти ту бензоколонку, начиная с которой можно проехать всю трассу, или сказать, что такой нет.
   Решение
   Пронумеруем бензоколонки по порядку начиная с произвольной. Пусть теперь $g[i]$ — изменение количества топлива после заправки в $i$-ой бензоколонки и прохождения дороги после нее. Тогда если $\sum\limits_{i=1}^n g[i] < 0$ такой бензоколонки нет, поскольку в таком случае количество топлива в бензоколонках меньше, чем требуется для прохождения всех дорог. Покажем, что если $\sum\limits_{i=1}^n g[i] \geqslant 0$ такая бензоколонка существует всегда. Рассмотрим частичные суммы $h[k] = \sum\limits_{i=1}^k g[i]$. Пусть минимальная частичная сумма достигается в индексе $j$ и равна $h[j]$. Тогда если $h[j] \geqslant 0$, то задача решена. Если же нет — начнем движение с бензоколонки, следующей за $j$. В таком случае частичные суммы всегда неотрицательны, поскольку в противном случае $j$ не был элементом, в котором достигается минимальная частичная сумма. Сложность по времени — $O(n)$.