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

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

Вариант 1

Найдите $\prod\limits_{k= 1}^{\infty}\cos(x\cdot2^{-k})$
Дана матрица $A$ размера $n$ x $n$ , где $a_{ij}=(i-j)^2$ , $i,j=1,...,n$ . Найдите ранг матрицы $A$ .
Имеется множество $A=$ { $1,2,3,...,256$ }. Найдите размер максимального по мощности подмножества $A'\subset A$ , такого, что $A'$ не содержит элементов $x,y$ , таких, что $x=2y$ .
На окружности случайно выбирается $n$ точек. Найдите вероятность того, что все они принадлежат некоторой полуокружности.
Назовем двумерный массив действительных чисел $A[1..n][1..n]$ возрастающим, если для любых $k, l$ $A[k][l]\ge A[i][j]$ , $i\le k, j\le l$ . Задача поиска в квадратном возрастающем массиве формулируется так: для заданного возрастающего массива $A[1..n][1..n]$ и некоторого числа $X$ определить, встречается ли число $X$ в массиве $A$ . Покажите, что не существует алгоритма, решающего эту задачу менее чем за $n$ сравнений.
У линейного преобразования $n$ -мерного пространства существует $n+1$ собственных векторов, таких, что любые $n$ из них линейно независимы. Найдите всевозможные матрицы, которые могли бы задавать такое преобразование.
Найдите сумму ряда $\sum\limits_{n=1}^{\infty}\displaystyle\frac{f(n)}{n(n+1)}$ , где $f(n)$ -количество единиц в двоичном представлении числа $n$ .

Вариант 2

Последовательность { $a_n$ } $_{n=0}^{\infty}$ определена рекурсивно $a_0=1$ , $a_{n+1}=\displaystyle\frac{a_n}{1+n\cdot a_n}$ . Найдите формулу общего члена последовательности.
Дано множество $A=$ { $1,2,...,n$ }. Среди всех его подмножеств равновероятно выбирается $k$ его подмножеств. Найдите вероятность того, что $A_1\cap A_2\cap...\cap A_n=\emptyset$
Дан массив длины $n$ из нулей и единиц. Найдите в нем подмассив максимальной длины, в котором количество единиц равно количеству нулей. Ограничения: $O(n)$ по времени, $O(n)$ по дополнительной памяти.
Пусть $\int_{0}^{2\pi}\cos(x)\cdot\cos(2x)...\cos(mx)dx$ . Для каких $m\in[1,10]$ $I_m\ne0$ ?
Дан неориентированный граф $G$ без петель. Пронумеруем все его вершины. Матрица смежности графа $G$ с конечным числом вершин $n$ (пронумерованных числами от 1 до $n$ ) - это квадратная матрица $A$ размера $n$ , в которой значение элемента $a_{ij}$ равно числу ребер из $i$ -ой вершины графа в $j$ -ю вершину. Докажите, что матрица $A$ имеет отрицательное собственное значение.
Рассмотрим бесконечный двумерный массив { $a_{ij}$ } $_{i,j=1}^{\infty}$ , состоящий из натуральных чисел, причем каждое число встречается в массиве ровно 8 раз. Докажите, что $\exists (m,n): a_{mn}>mn$ .
Дана матрица из нулей и единиц, причем для каждой строки матрицы верно следующее: если в строке есть единицы, то они все идут подряд (неразрывной группой из единиц). Докажите, что определитель такой матрицы может быть равен только $\pm1$ или $0$ .