Вступительный экзамен в ШАД 2013 год

Вступительный экзамен в Школу анализа данных
2013 год

Экзамен длится 4 часа

Условия задач

Последовательность { $x_n$ } $_{n=0}^{+\infty}$ задана реккурентным соотношением: $x_0=0$ , $x_1=1$ , $x_{n+1}=\displaystyle\frac{x_n+nx_{n-1}}{n+1}$ . Покажите, что данная последовательность сходится, и найдите ее предел.
Имеется 100 некоторых подмножеств множества {0, 1, ..., 9}. Докажите, что среди них найдется два подмножества, у которых симметрическая разность имеет мощность не более двух.
На единичной окружности { $x^2+y^2=1$ } выбирается случайная точка P (из равномерного распределения). В единичном круге { $x^2+y^2\le1$ } выбирается случайная точка Q (также из равномерного распределения). Пусть R - прямоугольник со сторонами, параллельными осям координат и диагональю PQ. Какова вероятность того, что весь прямоугольник лежит в единичном круге?
Пусть $f$ - положительная непрерывная функция на $R$ , причем $\int_{-\infty}^{+\infty}f(x)dx=1$ . Пусть $\alpha\in(0,1)$ , а интервал $[a,b]$ - это интервал минимальной длины из тех, для которых $\int_{a}^{b}f(x)dx=\alpha$ . Покажите, что $f(a)=f(b)$ .
Дана матрица $M$ размера nxn, где $m_{ij}=a_ia_j$ при $i\ne j$ и $m_{ij}=a_i^2+k$ , $i,j=1,...,n$ . Найдите определитель матрицы $M$ .
Задана битовая матрица nxn, с элементами 0 и 1 (каждый элемент матрицы занимает один бит памяти). Назовем строку (столбец) исходной матрицы плохой (плохим), если в нем встречается хотя бы один ноль. Необходимо в исходной матрице занулить все плохие строки и столбцы. Предложите алгоритм, решающий эту задачу за O(1) дополнительной памяти и оцените его временную сложность.
Рассмотрим линейное пространство многочленов на R от двух переменных степени не выше 2013. Рассмотрим его подпространство V, образованное всеми многочленами $f$ , для которых криволинейный интеграл первого рода $\oint_{\{x^2+y^2=r^2\}}f(x,y)ds=0$ , причем для любого r. Найдите размерность подпространства V.