1 июня 2014

1. Пусть $M \subseteq \mathbb{R}$ — множество из $n$ элементов. Пусть, далее, $$S_M = \left\{ \left. \frac{x+y}{2} \right| x,y \in M, x \neq y \right\}.$$ Найдите наименьшую возможную мощность множества $S_M$ (одинаковые элементы множества считаются одним элементом).
   Решение
   Пусть $x_1 < x_2 < \cdots x_n$ — элементы множества $M$. Тогда $$\frac{x_1+x_2}{2} < \frac{x_1+x_3}{2} < \cdots < \frac{x_1+x_n}{2} < \frac{x_2+x_n}{2} < \frac{x_3+x_n}{2} < \cdots < \frac{x_{n-1}+x_n}{2}$$ суть различные элементы множества $S_M$ в количестве $2n-3$.
   Чтобы убедиться, что оценка точна, достаточно рассмотреть множество $M=\{1,2,\ldots,n\}.$
   Ответ
   $2n-3$.
2. На окружности выбираются $3$ случайных точки. С какой вероятностью центр окружности лежит внутри треугольника с вершинами в этих точках?
   Решение
   Пусть $x_1$, $x_2$, $x_3$ — три точки на окружности. С вероятностью $1$ найдется единственная пара чисел $t_2, t_3$, такая, что $x_1 + t_2 x_2 + t_3 x_3 = 0$. Легко убедится, что искомая вероятность совпадает с вероятностью $P(t_2, t_3 > 0)$. Рассмотрим события $A_1 = \{t_2, t_3 > 0\}$, $A_2 = \{t_2>0,t_3<0\}$, $A_3 = \{t_2<0, t_3>0\}$, $A_4 = \{t_2,t_3<0\}$. Так как эти события равновероятны, несовместны и их объединение имеет вероятность $1$, заключаем, что вероятность каждого из них равна $\frac{1}{4}$.
   Ответ
   $\dfrac{1}{4}$.
3. Квадратная матрица $A$ размера $9\times 9$ над полем характеристики, отличной от $2$, такова, что $A^2=E$. Найдите ранг матрицы $E-A$, если известно, что ранг матрицы $E+A$ равен $7$.
   Решение
   Так как $A^2 = E$, матрица $A$ диагонализуема, причем на диагонали стоят числа $1$ и $-1$. Так как $\mathrm{rank}\,(E+A)=7$ и $\mathrm{char}\,K \neq 2$, мы заключаем, что $-1$ встречается $2$ раза, а $1$ встречается $7$ раз. Тогда $\mathrm{rank}\,(E-A)=2$.
   Решение 2
   Пусть $V$ — векторное пространство над полем $K$, $\dim V = 9$. Также введем обозначения $U = \ker (E+A)$, $W = \ker (E-A)$. Тогда $\dim U = \dim V - \mathrm{rank}\, (E+A) = 9 - 7 = 2$.
   Докажем, что $U \cap W = \varnothing$. В самом деле, если $(E-A)x = 0$, то $(E+A)x = 2x$. Поскольку $\text{char } K \neq 2$, $2x \neq 0$ для $x \neq 0$ (в соответствии с определением характеристики поля).
   Заметим, что $(E-A)(E+A)=0$. Отсюда следует, что $\text{Im}(E+A) \subset \ker (E-A)$, а значит $\dim W \geq \mathrm{rank}\, (E+A)=7$.
   С другой стороны, $\dim (U+W) = \dim U + \dim W - \dim (U \cap W) = \dim U + \dim W \leq \dim V = 9$. Следовательно, $\dim W \leq 9 - \dim U = 7$.
   Из $\dim W \geq 7$ и $\dim W \leq 7$ получаем $\dim W = 7$. Значит $\mathrm{rank}\, (E-A) = \dim V - \dim W = 9 - 7 = 2$.
   Ответ
   $2$.
4. В полукруге есть $n$ неизвестных нам точек. Разрешается задавать вопросы вида «каково расстояние от точки $X$ до ближайшей из этих точек?» Если расстояние оказывается нулевым, точка считается угаданной. Докажите, что хотя бы одну из этих точек можно угадать не более чем за $2n+1$ вопрос.
   Решение
   Возьмем на диаметре полукруга $n+1$ точку $A_1,A_2, \ldots A_{n+1}$ и для каждой из них зададим наш вопрос. По принципу Дирихле, для каких-то двух соседних точек полученный ответ относился к одной и той же загаданной точке. Теперь мы рассматриваем точки $B_i$ пересечения окружностей с центрами в точках $A_i$ и $A_{i+1}$, $i=1,\ldots,n$. По сказанному выше, хотя бы одна из загаданных точек совпадает с одной из точек $B_i$. Эту точку мы находим за $n$ вопросов. Итого нам потребовалось не более $(n+1)+n=2n+1$ вопросов.
5. Найдите предел $$\lim\limits_{\lambda \to 0+} \frac{1}{\ln \lambda} \int\limits_\lambda^a \frac{\cos x}{x} dx.$$
   Решение
   Разобьем интеграл на слагаемые: $$\int\limits_\lambda^a \frac{\cos x}{x} dx = \int\limits_\lambda^a \frac{1}{x} dx + \int\limits_\lambda^a \frac{\cos x - 1}{x} dx.$$ Для первого слагаемого имеем: $$\lim\limits_{\lambda \to 0+} \frac{1}{\ln \lambda} \int\limits_\lambda^a \frac{1}{x} dx = -1.$$ Для второго слагаемого: $$\left| \int\limits_\lambda^a \frac{\cos x - 1}{x} dx \right| \leqslant \left| \int\limits_0^a \frac{\cos x - 1}{x} dx \right|.$$ Подынтегральная функция непрерывна в нуле (так как $\cos x - 1 = O(x^2)$), поэтому интеграл конечен, откуда получаем: $$\lim\limits_{\lambda \to 0+} \frac{1}{\ln \lambda} \int\limits_\lambda^a \frac{\cos x - 1}{x} dx = 0.$$ Поскольку оба предела существуют и конечны, предел суммы равен $-1$.
   Ответ
   $-1$.
6. Пусть $A$ и $B$ — квадратичные матрицы размера $2\times 2$. Рассмотрим линейный оператор $F$ на пространстве матриц $2\times 2$, действующий по правилу $$F(M) = A \cdot M \cdot B.$$ Матрица $A$ имеет $2$ различных собственных значения $\lambda_1$ и $\lambda_2$, а $B$ — $2$ различных собственных значения $\mu_1$ и $\mu_2$. Найдите собственные значения оператора $F$, если (а) матрицы $A$ и $B$ — диагональные; (б) матрицы $A$ и $B$ — произвольные.
   Решение
   (а) Собственными векторами являются матричные единицы.
   (б) Пусть $v$ — собственный вектор матрицы $A$ с собственным значением $\lambda$, а $u$ — собственный вектор матрицы $B^{\mathrm{T}}$ с собственным значением $\mu$. Матрица $B^{\mathrm{T}}$ имеет те же собственные векторы, что и $B$. Тогда матрица $v u^{\mathrm{T}}$ будет собственным вектором оператора $F$ с собственным значением $\lambda \mu$.
   Ответ
   $\lambda_1 \mu_1, \lambda_1 \mu_2, \lambda_2 \mu_1, \lambda_2 \mu_2$ в обоих пунктах.
7. Квадратная марица $n\times n$ заполнена различными натуральными числами. Предложите алгоритм, находящий два элемента этой матрицы, не лежащих ни в одной строке, ни в одном столбце, с максимально возможным произведением. Ограничение по времени — $O(n^2)$, по памяти — $O(n)$.
   Решение
   За $O(n^2)$ находим максимум $a$ и второй максимум $b$ в матрице. Если полученные элементы не лежат в одной строке или столбце, то задача решена. Если же лежат — находим максимальный элемент $c$ из тех элементов, которые не лежат в той строке/столбце, которая общая для $a$ и $b$. Тогда если $c$ не лежит в строке/столбце с $a$, то $ac$ будет искомым максимальным произведением. Если лежит — то находим максимум $d$ среди тех элементов, которые не лежат в той строке/столбце, которая общая для $a$ и $b$ и не лежат в одной строке/столбце с $a$. Тогда либо $bc$, либо $ad$ будет искомым максимальным произведением.
   Решение 2
   За $O(n^2)$ операций находим максимумы и вторые максимумы по строкам и столбцам, записываем их вместе с индексами в массив длины $O(n)$. Для каждого из них выбираем из списка максимальное число, не лежащее с ним ни в одной строке, ни в одном столбце, и перемножаем. Из полученных произведений выбираем максимальное.
8. Игральную кость с $n$ гранями (и числами от $1$ до $n$ на этих гранях) подбрасывают до тех пор, пока сумма выпавших очков не станет больше либо равна $n$. Все грани кости выпадают с одинаковой вероятностью. Найдите математическое ожидание числа бросков.
   Решение
   Обозначим через $M(k)$ математическое ожидание числа бросков, требуемых для получения суммы, большей или равной $n$, при условии, что в начальный момент сумма была равна $k$.
   Тогда имеем $$M(n)=0, M(n-1)=1, M(n-2) = 1 + \frac{1}{n} M(n-1) = 1 + \frac{1}{n},$$ $$M(n-3) = 1 + \frac{1}{n} M(n-2) + \frac{1}{n} M(n-1) = 1 + \frac{2}{n} + \frac{1}{n^2},$$ $$M(n-4) = 1 + \frac{1}{n} M(n-3) + \frac{1}{n} M(n-2) + \frac{1}{n} M(n-1) = 1 + \frac{3}{n} + \frac{3}{n^2} + \frac{1}{n^3}.$$ Возникает гипотеза о том, что $$M(n-k) = \sum_{i=1}^{k-1} C_{k-1}^i \frac{1}{n^i},$$ которая проверяется при помощи индукции.
   Искомое математическое ожидание равно $$M(0) = \sum_{i=1}^{n-1} C_{n-1}^i \frac{1}{n^i} = \left( 1 + \frac{1}{n} \right)^{n-1}.$$
   Ответ
   $\left( 1 + \frac{1}{n} \right)^{n-1}.$