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

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

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

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

Рассмотрим функцию $\psi(x)=\sum_{k=1}^{\infty}\displaystyle\frac{1}{2^{2[log_2k]}}x^k$ , где квадратные скобки означают целую часть числа. Найдите $\int_0^1\psi(x)\psi'(x)dx$ .
Петя и Вася подбрасывают правильную монетку (вероятность выпадения орла равна 0.5). Петя подбрасывает ее n раз, а Вася - n+1. Найдите вероятность того, что у Васи орлов выпало больше, чем у Пети.
Определим последовательность $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$ .
Найдите математическое ожидание числа неподвижных точек для случайной перестановки на $n$ элементах.
Верно ли, что rank(AB) = rank(BA) для любых квадратных матриц A и B?
Есть круговая трасса, на которой в некоторых местах стоят бензоколонки. Расстояния между ними и количество бензина на каждой бензоколонке известны. Имеется также машина с постоянным и известным расходом топлива. Предложите алгоритм за O(n) по времени (n - количество бензоколонок), который позволяет найти ту бензоколонку, начиная с которой можно проехать всю трассу, или сказать, что такой нет.