4 июня 2016

1. Докажите, что любая квадратная вещественная матрица является суммой двух обратимых.
2. Может ли непрерывная на всех числовой прямой функция принимать каждое значение (а) дважды? (б) трижды?
3. Каждая из случайных величин $X$ и $Y$ принимает два значения, причем $\mathrm{Cov} (X,Y) = 0$. Докажите, что $X$ и $Y$ независимы.
4. Все ребра неориентированного ациклического графа покрашены в два цвета: красный и синий. Предложите алгоритм, находящий длину максимального пути, в котором любые два соседних ребра разного цвета. Ограничение по времени — $O(V+E)$, где $V$ — число вершин графа, $E$ — число его ребер. Сколько дополнительной памяти требуется вашему алгоритму?
5. Пусть $\xi$, $\eta$ и $\lambda$ — независимые случайные величины, равномерно распределенные на отрезке $[0;1]$, а $t$ — фиксированное число. Найдите $P(\xi + \eta < t\lambda)$.
6. В пространстве многочленов с действительными коэффициентами степени не выше $n$ задана квадратичная форма $Q(f) = f(1) \cdot f(2)$. Найдите ее сигнатуру (число единиц и минус единиц в нормальном виде).
7. Найдите предел последовательности $$\lim_{n\to \infty} \int_0^1 e^{\{nx\}} x^{2016} dx,$$ где $\{t\}$ означает дробную часть числа $t$ (например, $\{ -\frac23 \} = \{ \frac43 \} = \frac13$).
   Решение
   Разобьем интервал интегрирования на $n$ участков, на каждом из которых целая часть числа $nx$ постоянна. Тогда $$\int\limits_0^1 e^{\{nx\}} x^{2016} dx = \sum_{k=1}^n \int\limits_{\frac{k-1}{n}}^{\frac{k}{n}} e^{nx} e^{1-k} x^{2016} dx.$$ Пусть функция $e^{nx} x^{2016}$ имеет первообразную $F(x)$. Тогда по формуле Ньютона-Лейбница получим $$\sum_{k=1}^n \int\limits_{\frac{k-1}{n}}^{\frac{k}{n}} e^{nx} e^{1-k} x^{2016} dx = (e-1) \sum_{k=1}^n \frac{1}{e^k} F\left( \frac{k}{n} \right) + \frac{1}{e^n} F(1) - F(0).$$ Нетрудно понять, что $F(x)$ имеет вид $e^{nx} g(x) = e^{nx} \sum_{s=0}^{2016} A_s x^s$. Коэффициенты полинома $g(x)$ легко найти из выражения $F'(x) = e^{nx} x^{2016}$. Рекуррентно получим $$A_{2016} = \frac{1}{n},$$ $$A_{2015} = \frac{-2016}{n^2},$$ $$A_{2014} = \frac{2015 \cdot 2016}{n^3},$$ $$\vdots$$ $$A_{0} = \frac{1 \cdots 2016}{n^{2017}}.$$ Сразу заметим, что $\lim\limits_{n\to \infty} \frac{1}{e^n} F(1) = \lim\limits_{n\to \infty} F(0) = 0$. Далее запишем $$(e-1) \sum_{k=1}^n \frac{1}{e^k} F\left( \frac{k}{n} \right) =$$ $$= (e-1) \left( \frac{1}{n^{2017}} \sum_{k=1}^n k^{2016} - \frac{2016}{n^{2017}} \sum_{k=1}^n k^{2015} + \cdots + \frac{1 \cdots 2016}{n^{2017}} \sum_{k=1}^n k^0 \right).$$ Поскольку $\sum\limits_{k=1}^n k^s$ — многочлен степени $s+1$, при $n \to \infty$ все члены суммы кроме первого стремятся к нулю. Итого $$\lim\limits_{n \to \infty} (e-1) \left( \frac{1}{n^{2017}} \sum_{k=1}^n k^{2016} \right) = \frac{e-1}{2017}.$$
   Ответ
   $\dfrac{e-1}{2017}$.
8. а) Докажите, что во множестве отрезков $\Lambda = \{ [i,j] | i,j=1,\ldots ,n, i<j \}$ можно выбрать подмножество $\Sigma$, содержащее $O(n \log n)$ отрезков так, чтобы любой отрезок из $\Lambda$ представлялся в виде объединения не более двух отрезков из $\Sigma$.
   б) Докажите, что эта оценка точна, то есть подможество $\Sigma \subseteq \Lambda$, удовлетворяющее условиям, должно содержать $\Omega (n \log n)$ отрезков.