10 июня 2012

1. Даны $2012$ гирек разной массы. Они разбиты на две группы (по $1006$ в каждой), внутри которых упорядочены по массе. Предложите способ за $11$ взвешиваний найти $1006$-ю гирьку по массе среди всех.
   Решение
   Сравним массы $503$-их по массе гирек в этих группах. Пусть, для определенности, $a_{503} > b_{503}$. Тогда гирьки, которые легче $b_{503}$ в ее группе (+ сама $b_{503}$) и тяжелее $a_{503}$ в ее группе не могут быть $1006$-ми по массе, поэтому выкидываем их из групп. В результате такого шага у нас остались две группы по $503$ гирьки. Продолжая аналогичные рассуждения (в случае нечетного числа гирек в группе легкую при сравнении не выкидываем), за $10$ шагов у нас останется по одной гирьке в каждой группе и та, которая легче, и будет искомой.
2. Вычислите $\int\limits_0^{2\pi} (\sin x)^8 dx$.
   Решение
   Заметим, что $$\int\limits_0^{2\pi} (\sin x)^n dx = -\int\limits_0^{2\pi} (\sin x)^{n-1} d(\cos x) = (n-1) \int\limits_0^{2\pi} (\cos x)^2 (\sin x)^{n-2} dx.$$ Используя основное тригонометрическое тождество, получаем $$\int\limits_0^{2\pi} (\sin x)^n dx = \frac{n-1}{n} \int\limits_0^{2\pi} (\sin x)^{n-2} dx.$$ Тогда $$\int\limits_0^{2\pi} (\sin x)^8 dx = 2\pi \prod_{\substack{k=2\\k+=2}}^8 \frac{k-1}{k} = \frac{35\pi}{64}.$$
   Ответ
   $\dfrac{35\pi}{64}$.
3. Докажите, что многочлен с действительными коэффициентами, принимающий на действительной оси только положительные значения, может быть представлен в виде суммы квадратов многочленов с действительными коэффициентами.
   Решение
   Из $P(x) > 0$ следует, что у многочлена нет вещественных корней. Поскольку коэффициенты многочлена действительные, для любого комплексного корня $x_i$ комплексно-сопряженное число $\overline{x_i}$ также является корнем. Поэтому многочлен можно представить в виде: $$P(x) = (x - x_1)(x - \overline{x_1}) \cdots (x-x_k)(x - \overline{x_k}).$$ Попарно раскрывая скобки получим следующий вид выражения: $$P(x) = (x^2 + b_1x + c_1) \cdots (x^2 + b_kx + c_k).$$ Выделим полный квадрат в каждом из квадратичных множителей: $$P(x) = ((x + b_1/2)^2 + q_1) \cdots ((x + b_k/2)^2 + q_k).$$ Заметим, что $q_i > 0$ для любого $i$, поскольку иначе у выражения $(x + b_i/2)^2 + q_i$ были бы действительные корни. Значит, мы можем написать $q_i = y_i^2$, где $y_i$ — некоторое действительное число. Тогда $$P(x) = ((x + b_1/2)^2 + (y_1)^2) \cdots ((x + b_k/2)^2 + (y_k)^2).$$ Как видим, при раскрытии скобок мы получим сумму квадратов многочленов с действительными коэффициентами, что и требовалось доказать.
4. Какую наибольшую дисперсию может иметь случайная величина, принимающая значения на отрезке от $0$ до $1$?
   Решение
   $Dx = \int\limits_0^1 x^2 dF(x) - ( \int\limits_0^1 x dF(x) )^2 \leq \int\limits_0^1 x dF(x) - ( \int\limits_0^1 x dF(x) )^2 = z - z^2 \leq \frac14$, где $F(x)$ — произвольная монотонная функция распределения, а интегралы берутся в смысле Римана-Стилтьеса. Очевидно, что неравенство превращается в равенство в случае, если $F(x)$ описывает распределение Бернулли с параметром $\frac12$.
   Ответ
   $\dfrac14$.
5. В множестве из $n$ человек каждый может знать или не знать другого (если $A$ знает $B$, отсюда не следует, что $B$ знает $A$). Все знакомства заданы булевой матрицей $n\times n$. В этом множестве может найтись или не найтись знаменитость — человек, который никого не знает, но которого знают все. Предложите алгоритм, который бы находил в множестве знаменитость или говорил, что ее в этом множестве нет. Сложность по времени — $O(n)$, сложность по памяти — $O(1)$.
   Решение
   Для определенности положим $$K_{ij} = \begin{cases} 1,&\text{если } i\text{-й знает }j\text{-ого;}\\ 0,&\text{иначе.}\end{cases}.$$ Заметим, что если $K_{ij} = 1$, то $i$-ый не может быть знаменитостью, а если $K_{ij} = 0$, то $j$-ый не может быть знаменитостью. Таким образом, за одну проверку можно исключить одного человека из кандидатов в знаменитости.
   Сначала пусть $s=1$, а $l$ пробегает значения от $2$ до $n$. Если в какой-то момент $K_{sl}=1$, то приравниваем $s=l$. Тогда значение $s$ после последней проверки — номер единственного оставшегося кандидата. Чтобы проверить, является ли этот кандидат знаменитостью, нужно провести еще $n-1$ проверок, знают ли его остальные, и $n-1$ проверок, знает ли он остальных. Всего будет проведено $3(n-1)$ проверок, следовательно, сложность по времени — $O(n)$. Поскольку мы использовали только $2$ переменные, сложность по памяти — $O(1)$.
6. Рассмотрим случайную перестановку на $n$ элементах. Докажите, что данные $k$ элементов окажутся в одном цикле с вероятностью $\frac1k$.
   Решение
   Будем генерировать случайную подстановку немного нестандартным образом. Сначала равновероятно выберем случайную перестановку, а затем сопоставим ей циклы, заканчивающиеся на элементах в порядке тривиальной перестановки. Например, для перестановок из $9$ элементов $$\begin{align*} 172598346 &\to (1)(72)(5983)(4)(6)\\ 592613478 &\to (59261)(3)(4)(7)(8)\\ 641982735 &\to (641)(982)(73)(5) \end{align*}$$ Рассмотрим самый правый элемент из элементов под номерами $1\ldots k$ в такой записи. Любой из этих элементов может с одинаковой вероятностью быть самым правым. Чтобы данные $k$ элементов лежали в одном цикле, самым правым из них может быть только элемент под номером $1$. Поэтому искомая вероятность равна $1/k$.
   Решение 2
   Посчитаем, для начала, вероятность того, что данные $k$ элементов окажутся в цикле длины $k$. Всего перестановок $n!$, циклов $(k-1)!$, перестановок из оставшихся элементов $(n - k)!$. Тогда такая вероятность равна $$p_k = \frac{1}{n!} (k-1)! (n-k)!$$ Пусть теперь они оказались в цикле длины $k+m$. Тогда мы дополнительно выбираем $m$ элементов из $n-k$ и вероятность становится $$p_{k+m} = \frac{1}{n!} C^m_{n-k} (k+m-1)! (n-k-m)!$$ Полная вероятность равна сумме $$\sum_{m=0}^{n-k} p_{k+m} = \frac{1}{n!} \sum_{m=0}^{n-k} C^m_{n-k} (k+m-1)! (n-k-m)! =$$ $$= \frac{(n-k)!}{n!} \sum_{m=0}^{n-k} \frac{(k+m-1)!}{m!} = \frac{(n-k)!}{n!} \frac{k+m-m}{k} \sum_{m=0}^{n-k} \frac{(k+m-1)!}{m!} =$$ $$= \frac{(n-k)!}{kn!} \sum_{m=0}^{n-k} \left( \frac{(k+m)!}{m!} - \frac{m(k+m-1)!}{m!} \right) =$$ $$= \frac{(n-k)!}{kn!} \left( \sum_{m=1}^{n-k+1} \frac{m(k+m-1)!}{m!} - \sum_{m=0}^{n-k} \frac{m(k+m-1)!}{m!} \right) =$$ $$= \frac{(n-k)!}{kn!} \frac{(n-k+1)n!}{(n-k+1)!} = \frac{1}{k}.$$
7. Есть неизвестная нам квадратичная форма $Q$ в $n$-мерном пространстве. Разрешается задавать вопрос вида «Чему равно $Q(v)$?». Какое минимальное число вопросов надо задать, чтобы определить, является ли форма $Q$ положительно определенной?
   Решение
   Пусть квадратичная форма записана в базисе $e_1, e_2, \ldots e_n$. Понятно, что если ответ на какой-то вопрос будет неположительным, то форма не положительно определенная. Задав $\frac{n(n+1)}{2}$ вопросов можно найти все коэффициенты (например, сначала находим диагональные, затем все остальные) и определить, является ли форма положительно определенная. Докажем, что за меньшее число вопросов сделать мы этого не сможем.
   
   Каждый вопрос дает нам линейное уравнение на коэффициенты. Если мы задали вопросов меньше, чем число коэффициентов, какие-то коэффициенты будет неопределены. Пусть неопределен диагональный коэффициент $a_{jj}$. Тогда ответ на вопрос $Q(e_{j}) = a_{jj}$ может быть отрицательным, а значит мы не можем быть уверены в положительной определенности. Пусть теперь все диагональные коэффициенты известны и положительны, а некоторый недиагональный коэффициент $a_{ij}$ неопределен. Тогда ответ на вопрос $Q(e_i + e_j) = a_{ii} + a_{ij} + a_{jj}$ может быть отрицательным.
   Ответ
   $\dfrac{n(n+1)}{2}.$