2 июня 2013

1. Найдите $\prod\limits_{k=1}^\infty \cos (x2^{-k})$.
   Решение
   Используем формулу двойного угла: $$\cos (x2^{-k}) = \frac12 \frac{\sin (x2^{1-k})}{\sin (x2^{-k})}.$$ Тогда $$\prod\limits_{k=1}^\infty \cos (x2^{-k}) = \prod\limits_{k=1}^\infty \frac12 \frac{\sin (x2^{1-k})}{\sin (x2^{-k})} =$$ $$= \lim_{k \to \infty} \frac{1}{2^k} \frac{\sin x}{\sin (x2^{-k})} = \frac{\sin x}{x}.$$
   Ответ
   $\dfrac{\sin x}{x}.$
2. Дана матрица $A$ размера $n\times n$, где $a_{ij} = (i-j)^2, i,j=1, \ldots, n$. Найдите ранг матрицы $A$.
   Решение
   Пусть $\{A_j\}_{j=1}^n$ — столбцы матрицы $A$, а $\{P_k\}$ — столбцы вида $(1^k, 2^k, \ldots, n^k)^\mathrm{T}$. Тогда по условию задачи $A_j = P_2 - 2jP_1 + j^2P_0$. Отсюда следует, что столбцы матрицы $A$ принадлежат подпространству, натянутому на линейно независимые вектора $P_2, P_1, P_0$. Значит, $\mathrm{rank}\,A \leqslant 3$. Заметим, что в случае $n\geqslant 3$ столбы $A_1, A_2, A_3$ будут линейно независимы. Действительно, $$\begin{vmatrix} 1&-2&1\\ 1&-4&4\\ 1&-6&9 \end{vmatrix} = -4 \neq 0$$ Поэтому при $n\geqslant 3$ $\mathrm{rank}\, A = 3$. В случаях $n=1$ и $n=2$ получим $0$ и $2$ соответственно.
   Ответ
   При $n\geqslant 3$ $\mathrm{rank}\, A = 3$. В случаях $n=1$ и $n=2$ получим $0$ и $2$ соответственно.
3. Имеется множество $A=\{1,2,3,\ldots,256\}$. Найдите размер максимального по мощности подмножества $A' \in A$, такого, что $A'$ не содержит элементов $x,y$, таких, что $x=2y$.
4. На окружности случайно выбирается $n$ точек. Найдите вероятность того, что все они принадлежат некоторой полуокружности.
5. Назовем двумерный массив действительных чисел $A[1\ldots n][1\ldots n]$ возрастающим, если для любых $k,l$ $A[k][l] \geqslant A[i][j], i \leqslant k, j \leqslant l$. Задача поиска в квадратном возрастающем массиве формулируется так: для заданного возрастающего массива $A[1\ldots n][1\ldots n]$ и некоторого числа $X$ определить, встречается ли число $X$ в массиве $A$. Покажите, что не существует алгоритма, решающего эту задачу менее, чем за $n$ сравнений.
6. У линейного преобразования $n$-мерного пространства существуют $n+1$ собственных векторов, таких, что любые $n$ из них линейно независимы. Найдите всевозможные матрицы, которые могли бы задавать такое преобразование.
   Решение
   Понятно, что число линейно независимых собственных векторов, принадлежащих некоторому собственному значению (геометрическая кратность), равно алгебраической кратности этого собственного значения (поскольку есть $n$ линейно независимых собственных векторов, а геометрическая кратность не превышает алгебраическую). Тогда, при распределении $n+1$ вектора по $n$ собственным значениям, некоторому собственному значению $\lambda$ достанется на $1$ вектор больше, чем его геометрическая кратность. Пусть теперь есть собственное значение $\kappa \neq \lambda$. Тогда возьмем $n$ векторов, кроме одного вектора из $\kappa$. В таком случае эти вектора будут линейно зависимы — противоречие. Это означает, что все собственные значения оператора равны $\lambda$.
   Таким образом, любой вектор из собственного подпространства, при действии на него оператора, растягивается в $\lambda$ раз. Но поскольку из собственных векторов можно составить базис, любой другой вектор пространства, при действии на него оператора, также будет растягиваться в $\lambda$ раз. Нетрудно понять, что матрица такого оператора должна быть скалярной. В самом деле, при умножении матрицы на вектора вида $(0,\ldots 1 \ldots ,0)^\mathrm{T}$, мы должны получить вектора вида $(0,\ldots \lambda \ldots ,0)^\mathrm{T}$. Значит, все элементы на диагонали матрицы равны $\lambda$. Если же теперь для некоторых $i\neq j$ $a_{ij}\neq 0$, то легко подобрать вектор, который уже не растянется в $\lambda$ раз.
   В качестве примера для любой скалярной матрицы можно взять все возможные вектора вида $(0,\ldots 1 \ldots ,0)^\mathrm{T}$ и вектор $(1,\ldots 1 \ldots, 1)^\mathrm{T}$.
   Ответ
   Все скалярные матрицы.
7. Найдите сумму ряда: $$\sum\limits_{n=1}^\infty \frac{f(n)}{n(n+1)},$$ где $f(n)$ — количество единиц в двоичном представлении числа $n$.
   Решение
   В первую очередь докажем, что данный ряд сходится. Нетрудно понять, что $f(n) \leq \log_2 (n+1)$. Теперь докажем, что начиная с некоторого $n$ выполняется $\log_2 (n+1)$ < $\sqrt{n}$. Действительно, по правилу Лопиталя получим: $$\lim_{n\to \infty} \frac{\log_2 (n+1)}{\sqrt{n}} = \frac{2}{\ln 2} \lim_{n\to \infty} \frac{1}{\sqrt{n}} = 0.$$ Отсюда получаем, что сходимость ряда $\sum\limits_{n=1}^\infty \frac{f(n)}{n(n+1)}$ эквивалентна сходимости ряда $\sum\limits_{n=1}^\infty \frac{\sqrt{n}}{n(n+1)}$.
   Этот ряд нетрудно ограничить: $$\sum_{n=1}^\infty \frac{\sqrt{n}}{n(n+1)} = \sum_{n=1}^\infty \left( \frac{\sqrt{n}}{n} - \frac{\sqrt{n}}{n+1} \right) = 1 + \sum_{n=2}^\infty \frac{\sqrt{n} - \sqrt{n-1}}{n} < 1 + \sum_{n=2}^\infty \left( \frac{1}{\sqrt{n-1}} - \frac{1}{\sqrt{n}} \right) = 2$$ (или воспользоваться фактом, что $\sum_{n=1}^\infty \frac{1}{n^{1+\varepsilon}}$ сходится при $\varepsilon > 0$). Для нахождения суммы ряда заметим, что $f(2n) = f(n)$ и $f(2n+1) = f(n)+1$. Тогда: $$\begin{align*} \sum\limits_{n=1}^\infty \frac{f(n)}{n(n+1)} &= \frac12 + \sum\limits_{n=1}^\infty \frac{f(2n)}{2n(2n+1)} + \sum\limits_{n=1}^\infty \frac{f(2n+1)}{(2n+1)(2n+2)} \\ &= \frac12 + \sum\limits_{n=1}^\infty \frac{f(n)}{2n(2n+1)} + \sum\limits_{n=1}^\infty \frac{f(n)+1}{(2n+1)(2n+2)} \\ &= \frac12 + \sum\limits_{n=1}^\infty f(n) \left[ \frac{1}{2n(2n+1)} + \frac{1}{(2n+1)(2n+2)} \right] + \sum\limits_{n=1}^\infty \frac{1}{(2n+1)(2n+2)} \\ &= \frac12 + \frac12 \sum\limits_{n=1}^\infty \frac{f(n)}{n(n+1)} + \sum\limits_{n=1}^\infty \frac{1}{(2n+1)(2n+2)}. \end{align*}$$ Поскольку ряд сходится, мы можем переписать: $$\begin{align*} \sum\limits_{n=1}^\infty \frac{f(n)}{n(n+1)} &= 1 + 2\sum\limits_{n=1}^\infty \frac{1}{(2n+1)(2n+2)} = 1 + 2\sum_{n=3}^\infty \frac{(-1)^{n+1}}{n} \\ &= 2\sum_{n=1}^\infty \frac{(-1)^{n+1}}{n} = 2 \left. \sum_{n=1}^\infty \frac{(-1)^{n+1}x^n}{n} \right|_{x=1} = 2\ln (1+x) |_{x=1} = 2\ln 2. \end{align*}$$
   Ответ
   $2\ln 2$.