7 июня 2014 (Минск)

1. Стержень длины $L$ произвольным образом разламывают на две части и выбрасывают меньшую часть. Затем оставшуюся часть ломают и снова выбрасывают меньшую часть. Найдите вероятность того, что длина оставшейся части не меньше $L/2$.
   Решение
   Длина $x$ первого оставшегося отрезка (все делим на $L$) равномерно распределена на отрезке $[\frac12;1]$. Если мы зафиксируем длину $x$, то длина второго оставшегося отрезка $y$ будет равномерно распределена на отрезке $[\frac{x}{2};x]$. Нас интересует событие $y \geqslant \frac12$.
   Запишем формулу полной вероятности: $$p(y \geqslant \frac12) = \int\limits_{1/2}^1 2dx \int\limits_{1/2}^x \frac2x dy = 4\int\limits_{1/2}^1 \frac{dx}{x} \left( x- \frac12 \right) = 2 - 2\ln 2.$$
   Ответ
   $2-2\ln 2$.
2. Найдите минимум и максимум функции $$f(x,y) = x^2 + y^2 - 12x + 16y$$ на круге $x^2 + y^2 \leqslant 5^2$.
   Решение
   Рассмотрим функцию $z = f(x,y)+100 = (x-6)^2 + (y+8)^2$. Понятно, что эта функция достигает минимума и максимума в тех же точках, что и $f(x,y)$. Видно, что $z$ постоянна на окружности с центром в точке $(6, -8)$ и увеличивается с увеличением радиуса окружности, поэтому минимум достигается в ближней точке касания этой окружности с окружностью $x^2 + y^2 = 5^2$, а максимум — в дальней.
   Заметим, что через точки касания окружностей проходит прямая, соединяющая центры окружностей. Поэтому, достаточно найти точки пересечения окружности $x^2 + y^2 = 5^2$ с прямой $y = -\frac{8x}{6}$. Получим $(3,-4)$ и $(-3,4)$. Им соответствуют значения $z=25$ и $z=225$. Тогда $\min (f(x,y)) = -75$, а $\max (f(x,y)) = 125$.
   Ответ
   $-75$; $125$.
3. Сколько $2014$-значных чисел, составленных из цифр $1$,$\,3$,$\,4$,$\,6$,$\,7$,$\,9$, делятся на $7$?
   Решение
   Заметим, что цифры $1$,$\,3$,$\,4$,$\,6$,$\,7$,$\,9$ при делении на $7$ дают остатки $1$,$\,3$,$\,4$,$\,6$,$\,0$ и $2$ соответственно, и среди всех возможных остатков в этом наборе нет $5$. Представим, что в нашем наборе есть еще цифра $5$, которая дает остаток $5$ при делении на $7$. Тогда количество $2014$-значных чисел, составленных из этого набора и делящихся на $7$, равно $7^{2013}$ (количеству всех $2013$-значных чисел из этого набора). В самом деле, к любому $2013$-значному числу из этого набора мы можем приписать в конце такую единственную цифру из набора, чтобы получившееся $2014$-значное число делилось на $7$.
   Вернемся теперь к исходному набору. В этом случае количество $2014$-значных чисел, составленных из этого набора и делящихся на $7$, равно $6^{2013}$ за вычетом тех $2013$-значных чисел, которым требуется дополняющий остаток $5$. Очевидно, что такие $2013$-значные числа должны давать остаток $3$ при делении на $7$ ($3\cdot 10 \mod 7 = 2$, $2+5 \mod 7 = 0$).
   Таким образом, задача сводится к нахождению всех $2013$-значных чисел, составленных из данного набора, которые дают остаток $3$ при делении на $7$. Аналогично, количество таких чисел равно $6^{2012}$ за вычетом тех $2012$-значных чисел, которым требуется дополняющий остаток $5$. Такие числа должны давать остаток $4$ при делении на $7$ ($4\cdot 10 \mod 7 =5$, $5+5 \mod 7 = 3$), и задача снова сводится к нахождению уже $2012$-значных чисел, которые дают остаток $4$ при делении на $7$.
   Продолжая рассуждения по индукции, мы придем к задаче о количестве $1$-значных чисел из набора, которые дают остаток $2$ при делении на $7$. Таких чисел, очевидно, $1$.
   Объединив все эти задачи, получим ответ на изначальный вопрос: $$6^{2013} - 6^{2012} + \ldots + 6^1 - 1 = \frac{6^{2014}-1}{7}.$$
   Ответ
   $\dfrac{6^{2014}-1}{7}$.
4. В социальной сети зарегестрировано $n$ человек. Каждый участник может подписываться на сообщения других участников, причем если человек $A$ подписан на $B$, то из этого не следует, что $B$ подписан на $A$. Известно, что среди зарегестрированных пользователей есть знаменитость — человек, на которого подписаны все $n-1$ других пользователей, но сам он не подписан ни на кого. При помощи одного запроса к серверу вы можете определить, подписан ли человек $A$ на сообщения человека $B$. Предложите алгоритм, позволяющий найти знаменитость за не более чем $n$ запросов к серверу.
   Решение
   Зададим все подписки булевой матрицей $A$ размером $n\times n$, в которой $$A_{ij} = \begin{cases} 1,&\text{если } i\text{-й подписан на }j\text{-ого;}\\ 0,&\text{иначе.}\end{cases}$$ Заметим, что если $A_{ij} = 1$, то $i$-ый не может быть знаменитостью, а если $A_{ij} = 0$, то $j$-ый не может быть знаменитостью. Таким образом, за один запрос к серверу можно исключить одного человека из кандидатов в знаменитости.
   Сначала пусть $k=1$, а $l$ пробегает значения от $2$ до $n$. Если в какой-то момент $A_{kl}=1$, то приравниваем $k=l$. Тогда значение $k$ после последнего запроса — номер знаменитости. Всего будет послано $n-1$ запросов на сервер.
5. Найдите сумму ряда $$\sum\limits_{n=1}^\infty \frac{2^n}{n!}.$$
   Решение
   Заметим, что $$e^x = \sum\limits_{n=0}^\infty \frac{x^n}{n!} = 1 + \sum\limits_{n=1}^\infty \frac{x^n}{n!}.$$ Тогда $$\sum\limits_{n=1}^\infty \frac{2^n}{n!} = e^2 - 1.$$
   Ответ
   $e^2 - 1$.
6. Квадратная матрица $A$ размера $n\times n$ строится следующим образом: $$a_{ij} = \begin{cases}1,& \textrm{ если }i\textrm{ делит }j,\\0,& \text{ иначе.}\end{cases}$$ Вычислите определитель матрицы $A$.
   Решение
   Заметим, что матрица $A$ — верхнетреугольная, на диагонали которой стоят единицы. Следовательно, $\det A = 1$.
   Ответ
   $1$.
7. В коридоре длины $L$ находятся $n$ роботов, $i$-й из которых изначально расположен в позиции $x_i$ (все позиции различны $0 \leqslant x_i \leqslant L$). Все роботы движутся с единичной скоростью вдоль коридора. $i$-й робот движется со скоростью $v_i\; (\pm 1)$. При столкновении робота с границей коридора или с другим роботом направление вектора скорости робота меняется на противоположное.
   Прошло $t$ единиц времени...
   (a) Требуется найти множество точек, в которых находятся роботы (без учета порядка: не важно, какой робот находится в какой точке; точки в множестве не должны повторятся).
   (б) Для каждого робота $i$ необходимо указать его финальное положение $y_i$ в коридоре.
   Предложите эффективный алгоритм решения этих задач.
   Решение
   Движение роботов периодичное с периодом $T = 2L/1 = 2L$, поэтому вместо интервала $t$ мы можем рассматривать интервал $t - [t/T]T$.
   (a) Заметим, что если мы не будем различать роботов, то их соударения не будут менять ничего. Поэтому мы просто можем считать, что каждый робот соударяется только со стенками. Тогда его положение легко найти за $O(1)$. На выходе получим набор координат, некоторые из которых могут повторяться. Убрать повторы можно сортировкой и последующим проходом по набору. Итоговая сложность — $O(n \log n)$.
   (б) Порядок номеров роботов не меняется в процессе движения. Поэтому, если мы возьмем набор координат из предыдущего пункта (повторы не удаляем) и пронумеруем их в том же порядке, в каком они были пронумерованы в начале движения, мы получим ответ на данных пункт. Для этого можно отсортировать координаты по возрастанию или убыванию (в начальный момент и в момент времени $t$). Итоговая сложность — $O(n \log n)$.