7 июня 2015

1. Постройте график функции $$f(x) = \lim\limits_{n\to \infty} \sqrt[n]{1 + x^n + \left( \frac{x^2}{2} \right)^n}, \;\;\; x \geqslant 0.$$
   Решение
   Рассмотрим несколько случаев:
   1) $x<1$. Тогда $x^n$ и $( \frac{x^2}{2} )^n$ стремятся к нулю при $n \to \infty$ и, следовательно, $$\lim\limits_{n\to \infty} \sqrt[n]{1 + x^n + \left( \frac{x^2}{2} \right)^n} = 1.$$ 2) $1 \leqslant x < 2$. Тогда $\frac{x}{2} < 1$ и мы имеем $$\sqrt[n]{1 + x^n + \left( \frac{x^2}{2} \right)^n} = x \sqrt[n]{\frac{1}{x^n} + 1 + \left( \frac{x}{2} \right)^n} \to x\;\;(n \to \infty).$$ 3) $x \geqslant 2$. Тогда $\frac{2}{x} \leqslant 1$ и мы имеем $$\sqrt[n]{1 + x^n + \left( \frac{x^2}{2} \right)^n} = \frac{x^2}{2} \sqrt[n]{\left( \frac{2}{x^2} \right)^n + \left( \frac{2}{x} \right)^n + 1} \to \frac{x^2}{2}\;\;(n \to \infty).$$ Получается следующий график (правый участок графика представляет собою часть параболы):
   
   Ответ
   
2. Найдите собственные значения матрицы $v \cdot v^{\mathrm{T}}$, где $v$ — некоторый вектор-столбец.
   Решение
   Пусть $(\cdot,\cdot)$ — стандартное евклидово скалярное произведение $$(u,v) = u_1 v_1 + u_2 v_2 + \cdots + u_n v_n.$$ Заметим, что $(v \cdot v^{\mathrm{T}})x = v \cdot v^{\mathrm{T}} x = (v,x)v$. Пространство $V$, на котором действует наш линейный оператор, раскладывается в прямую сумму $V = < v > \oplus {< v >}^\perp$. Нетрудно видеть, что оба слагаемых являются собственными подпространствами для $v \cdot v^{\mathrm{T}}$ с собственными значениями $|v|^2$ и $0$ соответственно: $$\begin{align*} w = \lambda v &\Rightarrow (v \cdot v^{\mathrm{T}})w = \lambda v \cdot (v^{\mathrm{T}} v) = |v|^2 \cdot \lambda v;\\ w \perp v &\Rightarrow (v \cdot v^{\mathrm{T}})w = v \cdot (v^{\mathrm{T}} w) = (v,w)v = 0. \end{align*}$$
   Ответ
   $|v|^2$ и $0$.
3. Найдите математическое ожидание числа неподвижных точек подстановки на $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$.
4. Пусть $X$ и $Y$ — квадратные матрицы одинакового размера, причем $XY = \lambda X + \mu Y$ для некоторых $\lambda, \mu \neq 0$. Докажите, что матрицы $X$ и $Y$ коммутируют.
   Решение
   Преобразуем наше равенство: $$XY = \lambda X + \mu Y \iff XY - \lambda X - \mu Y + \lambda \mu E = \lambda \mu E \iff (X - \lambda E)(Y - \mu E) = \lambda \mu E.$$ Поскольку $\lambda, \mu \neq 0$, сомножители левой части обратимы, и мы можем сопрячь обе части, к примеру, матрицей $(X - \lambda E)$: $$(X - \lambda E)^{-1} (X - \lambda E) (Y - \mu E) (X - \lambda E) = \lambda \mu E \iff (Y - \mu E)(X - \lambda E) = \lambda \mu E.$$ Раскрывая скобки в левой части, получаем $$YX = \lambda X + \mu Y = XY,$$ что и требовалось доказать.
5. Электрическая цепь представляет собой связный неориентированный граф без кратных ребер, в котором ребра (числом $N$) — это провода, а вершины — либо лампочки, либо единственный источник тока. На каждом ребре размещено реле. Лампочка горит, если существует путь, соединяющий ее с источником тока, вдоль которого все реле находятся в положении «включено». Известно, что ровно одно из реле бракованное и никогда не пропускает ток. Вы можете включать и отключать реле (и видите, горят ли лампочки). Изначально все выключатели находятся в положении «включено». Опишите способ нахождения неисправного реле за $O(N)$ операций включения-выключения.
   Решение
   Это тот редкий случай, когда решение проще записать в виде псевдокода.
   
   FindBug(Node* root):
    Если граф — дерево, то бракованное реле находится перед
    первой (от корня) не горящей лампочкой.
    Если такого нет, отключаем все ребра графа. Return.
    Отключаем все ребра, выходящие из root.
    for (ребра j, выходящие из корня):
        Включаем j
        Его другой конец обозначим через new_root.
        FindBug(new_root). Если успешно — return.
        Выключаем j.

   Важное замечание. После выхода из FindBug все ребра в обработанном подграфе оказываются отключены и не мешают в дальнейшем.
   
   Оценим время работы алгоритма. Пусть $S_n$ — максимальная сложность FindBug для графа с $n$ ребрами. Пусть, далее, $j_1 \ldots j_t$ — все ребра, выходящие из источника. В худшем случае нам пришлось включить и выключить каждое из ребер $j_1 \ldots j_t$ и запустить процедуру FindBug для каждого из них.
   Тогда $$S_n \leqslant 2t + S_{k_1} + S_{k_2} + \cdots + S_{k_t},$$ где $k_1 + k_2 + \cdots + k_t = n-t.$
   Нетрудно видеть, что $S_1=S_2=0$, $S_3=1$. В любом случае, $S_m \leqslant 2m$ при $m=1,2,3$.
   Примем это за рабочую гипотезу. По индукции тогда можно заключить, что $$\begin{align*} S_n &\leqslant 2t + S_{k_1} + S_{k_2} + \cdots + S_{k_t} \leqslant 2t + 2k_1 + 2k_2 + \cdots + 2k_t\\ &= 2t + 2(k_1 + k_2 + \cdots + k_t) = 2t + 2(n-t) = 2n, \end{align*}$$ что и требовалось доказать.
6. Пусть $f$ — дифференцируемая функция, причем $f(0)=0$ и $0 < f'(x) \leqslant 1$. Докажите, что для всех $x \geqslant 0$ имеет место неравенство $$\int\limits_0^x f^3 (t) dt \leqslant \left( \int\limits_0^x f(t) dt \right)^2.$$
   Решение
   Мы будем активно пользоваться следующим правилом: $$\left. \begin{align*} u'(x) \leqslant v'(x)\;\text{при } x \geqslant 0\\u(0)=v(0) \end{align*} \right\} \Rightarrow u(x) \leqslant v(x)\;\text{при }x \geqslant 0.$$ Пусть $F(x) = \int\limits_0^x f^3(t) dt$, $G(x) = \left(\int\limits_0^x f(t) dt\right)^2$. Отметим, что $F(0)=G(0)=0$.
   Продифференцируем обе функции: $$F'(x) = f^3(x),\;\;G'(x) = 2\left(\int\limits_0^x f(t) dt\right)^2 \cdot f(x).$$ Снова видим, что $F'(0) = G'(0) = 0$ и снова дифференцируем: $$F''(x) = 3f^2(x) \cdot f'(x),\;\; G''(x) = 2f^2(x) + 2f'(x) \cdot \int_0^x f(t) dt.$$ Здесь уже можно немножко облегчить себе жизнь, заметив, что $2f^2(x) \cdot f'(x) \leqslant 2f^2(x)$. Значит, нам достаточно сравнить $f^2(x) \cdot f'(x)$ и $2f'(x) \cdot \int\limits_0^x f(t) dt$, а поскольку $f'(x) > 0$, то и просто $f^2(x)$ и $2\int\limits_0^x f(t) dt$.
   Заметим, что в нуле и то, и другое, равно $0$, и продифференцируем: $$(f^2(x))' = 2f(x) \cdot f'(x) \leqslant 2f(x) = \left( 2\int\limits_0^x f(t) dt \right)'.$$
7. Для произвольных положительных $n$ и $m$ вычислите сумму $$\sum\limits_{i=0}^n \frac{1}{2^{m+i+1}} C_{m+i}^i + \sum\limits_{i=0}^m \frac{1}{2^{n+i+1}} C_{n+i}^i.$$
   Решение
   Немного преобразуем выражение: $$\sum_{i=0}^n \frac{1}{2^{m+i+1}} C_{m+i}^i + \sum_{i=0}^m \frac{1}{2^{n+i+1}} C_{n+i}^i = \frac{1}{2^{m+n+1}} \left( \sum_{i=0}^n 2^{n-i} C_{m+i}^i + \sum_{i=0}^m 2^{m-i} C_{n+i}^i \right).$$ Знаменатель можно проинтерпретировать как количество последовательностей из $0$ и $1$ длины $m+n+1$. Пусть $X$ — множество последовательностей, в которых хотя бы $n+1$ единица, а $Y$ — множество последовательностей, в которых хотя бы $m+1$ ноль. Ясно, что $X \cap Y = \varnothing$, а $X \cup Y$ — множество всех последовательностей.
   Найдём мощность множества $X$. Пусть $(n + 1)$-я единица стоит на месте с номером $n + 1 +i$, где $i \in \{0, \ldots , m\}$. Тогда первые $n + i$ членов последовательности полностью определяются выбором позиций, на которых стоят единицы (это можно сделать $C_{n+i}^n=C_{n+i}^i$ способами), а последние $n-i$ могут быть любыми, то есть их можно выбрать $2^{n-i}$ способами. Таким образом, число последовательностей, содержащих хотя бы $n+1$ единицу, равно $\sum\limits_{i=0}^m 2^{m-i} C_{n+i}^i$.
   Аналогично число последовательностей, содержащих хотя бы $m+1$ ноль, равно $\sum\limits_{i=0}^n 2^{n-i} C_{m+i}^i$. А поскольку каждая последовательность принадлежит к одному и только одному из этих видов, то мы делаем вывод, что $$\sum_{i=0}^n 2^{n-i} C_{m+i}^i + \sum_{i=0}^m 2^{m-i} C_{n+i}^i = 2^{m+n+1}.$$ Таким образом, $$\sum_{i=0}^n \frac{1}{2^{m+i+1}} C_{m+i}^i + \sum_{i=0}^m \frac{1}{2^{n+i+1}} C_{n+i}^i = 1.$$
   Ответ
   $1$.
8. На сфере случайным образом выбираются четыре точки $A$,$B$,$C$ и $D$. С какой вероятностью кратчайшие дуги $AB$ и $CD$ пересекаются?
   Решение
   Проведем через точки $C$ и $D$ экватор. Тогда, очевидно, для выполнения условия задачи необходимо, чтобы точки $A$ и $B$ относительно этого экватора лежали в разных полусферах. Вероятность такого события равна $\frac12$. Пусть теперь точка $E$ — точка пересечения этого экватора и кратчайшей дуги, соединяющей точки $A$ и $B$. Ясно, что ее вероятность равномерно распределена по экватору. Таким образом, задача свелась к нахождению вероятности того, что случайная точка $E$ на окружности (экваторе), попадет в случайную дугу $CD$: $$p(E \in CD) = \int\limits_0^{\pi} \frac{x}{2\pi} \frac{dx}{\pi} = \frac14.$$ Тогда полная вероятность равна: $$p(AB \cap CD) = \frac12 p(E \in CD) = \frac18.$$
   Решение 2
   Рассмотрим случайную четвёрку точек $A$, $B$, $C$ и $D$. Прежде всего надо заметить, что ситуации, когда три и более точек лежат на одной большой окружности (в частности, если какие-то две из них диаметрально противоположны), имеют место c вероятностью ноль и потому не заслуживают рассмотрения. Далее, рассмотрим точки $A_-$, $B_-$, $C_-$ и $D_-$, диаметрально противоположные исходным. Имеются $16$ четвёрок точек $A_\pm$, $B_\pm$, $C_\pm$, $D_\pm$, из которых лишь $2$ нам подходят (это легко увидеть, если предположить, что исходные точки лежат в одной полусфере). Понятно, что появление случайных точек $A$, $B$, $C$ и $D$ можно представить, как появление восьми точек, включая диаметрально противоположные, а затем реализацию одной из четверок. Поскольку только $2$ нам подходят, вероятность равна $\frac18$.
   Ответ
   $\dfrac18$.