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

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

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

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

Определим последовательность $x_n$ начальными условиями $x_1=a$ , $x_2=b$ и рекуррентной формулой $x_{n+1}=\displaystyle\frac{1}{2}(x_n+x_{n+1})$ . Найдите $\lim_{n\to\infty}x_n$ .
Рассмотрим функцию $\psi(x)=\sum_{k=1}^{\infty}\displaystyle\frac{1}{2^{2[log_2k]}}x^k$ , где квадратные скобки означают целую часть числа. Найдите $\int_0^1\psi(x)\psi'(x)dx$ .
Рассмотрим всевозможные непустые подмножества множества {1,2,3,...,n}. В каждом подмножестве перемножим числа, обратные его элементам. Потом сложим полученное $2^n-1$ число. Найдите полученную сумму.
Петя и Вася подбрасывают правильную монетку (вероятность выпадения орла равна 0.5). Петя подбрасывает ее n раз, а Вася - n+1. Найдите вероятность того, что у Васи орлов выпало больше, чем у Пети.
Дано некоторое множество положительных чисел мощности континуум. Докажите, что из него можно выбрать счетное подмножество с бесконечной суммой.
Дан массив из n чисел. Предложите алгоритм, позволяющий за O(n) операций определить, является ли этот массив перестановкой чисел от 1 до n. Дополнительной памяти не более O(1).
Пусть $A_1,A_2,...,A_n$ - конечные множества и $a_{ij}=|A_i\cap A_j|$ . Докажите, что матрица $(a_{ij})_{i=1,2,...,n}^{j=1,2,...,n}$ неотрицательно определена.