8 июня 2014

1. Пусть $A$ — невырожденная вещественная матрица $n\times n$, все элементы которой положительны. Докажите, что число нулей среди элементов матрицы $A^{-1}$ не превосходит $n^2-2n$.
2. Трое игроков по очереди вынимают от $1$ до $m$ $(m>1)$ камней из кучи (количество камней в куче им изначально известно). Игрок, вынувший последний камень, проигрывает. Докажите, что если изначально куча была достаточно велика, то любые два игрока, договорившись, сумеют привести третьего к проигрышу.
3. Найдите предел последовательности $(c_n)$, определяемой рекуррентным соотношением $c_{n+1} = (1-\frac1n)c_n + \beta_n$, где $(\beta_n)$ — любая последовательность со свойством $n^2 \beta_n \to 0$ при $n \to \infty$.
   Решение
   Производя рекуррентные подстановки, нетрудно получить явное выражение $$c_n = \frac{1}{n-1} \sum\limits_{k=1}^{n-1} k \beta_{k}.$$ Поскольку последовательность $n^2 \beta_n$ сходится, она ограничена. Более формально $\exists A: \forall k \;\; |\beta_k| \leqslant \frac{A}{k^2}$. Тогда $$|c_n| \leqslant \frac{1}{n-1} \sum\limits_{k=1}^{n-1} k |\beta_{k}| \leqslant \frac{1}{n-1} \sum_{k=1}^{n-1} \frac{A}{k}.$$ Воспользуемся неравенством между средним арифметическим и средним квадратическим $$|c_n| \leqslant A \sqrt{\frac{\sum\limits_{k=1}^{n-1} \frac{1}{k^2}}{n-1}} \leqslant A \sqrt{\frac{2}{n-1}}.$$ Поскольку модуль $c_n$ ограничен рядом, сходящимся к $0$, $c_n \to 0$ при $n \to \infty$.
   Ответ
   $0$.
4. Отрезок $[0;1]$ разбит двумя случайными точками на три части. Найдите математическое ожидание длины меньшей из частей.
5. Предложите алгоритм, находящий значения $P(n+1), P(n+2), \ldots ,P(2n)$ неизвестного многочлена $n$-й степени $P(x)$, если даны его значения $P(0)$, $P(1), \ldots, P(n)$. Ограничение по времени — $O(n^2)$.
6. Вычислите интеграл $$\int e^{e^x + 2014x} dx.$$
7. Когда студент пришел в аудиторию, на доске было написано число $0$. В ожидании лекции студент подкидывает монетку и, если выпадет орел, он прибавляет к числу $1$, а если решка — то вычитает $1$. Орел и решка выпадают с равной вероятностью. Найдите вероятность того, что на момент после $(2n+1)$-го подбрасывания число на доске сменило знак (с положительного на отрицательный или наоборот) (а) ровно $n$ раз; (б) ни разу.
8. При каких натуральных $N$ существует квадратная матрица порядка $N$ с элементами $0,1$ такая, что ее квадрат — это матрица из одних единиц?