|
|
 |
Условие
На плоскости сидят кузнечик Коля и 2020 его товарищей. Коля собирается совершить прыжок через каждого из остальных кузнечиков (в произвольном порядке) так, что начальная и конечная точка каждого прыжка симметричны относительно перепрыгиваемого кузнечика. Назовём точку финишной, если Коля может в неё попасть после 2020-го прыжка. При каком наибольшем числе $N$ найдётся начальная расстановка кузнечиков, для которой имеется ровно $N$ различных возможных финишных точек?
Решение
Оценка. Способ 1. Введём на плоскости систему координат так, чтобы Коля сидел в точке $(0, 0)$. Пусть $\vec{a}_1$, $\vec{a}_2$, ..., $\vec{a}_{2020}$ – радиус-векторы кузнечиков в порядке их перепрыгивания Колей. Нетрудно найти радиус-вектор финишной точки $2(-\vec{a}_1 + \vec{a}_2 - \vec{a}_3 + ... - \vec{a}_{2019} + \vec{a}_{2020})$. Число различных по виду сумм равно $C_{2020}^{1010}$ (числу способов выбрать 1010 слагаемых на нечётных местах).
Способ 2. Заметим, что если кузнечик перепрыгнет через какую-то точку $A$, а затем через какую-то точку $B$, то в итоге он сдвинется на вектор $2\overrightarrow{AB} = 2(\overrightarrow{OB} - \overrightarrow{OA})$.
Каждой финишной точке можно поставить в соответствие последовательность, в которой Коля перепрыгивал своих друзей, чтобы оказаться в этой точке после 2020 прыжков – то есть перестановку чисел от 1 до 2020 (считаем всех кузнечиков, кроме Коли, пронумерованными). Пусть Коля в какой-то момент оказался в точке $O$ и собирается перепрыгнуть кузнечиков, расположенных в точках $A, B, C$ (рассматриваем только три последовательных прыжка). Если Коля сделает эти прыжки в порядке $ABC$, то сначала он сдвинется на вектор $2\overrightarrow{OA}$, а затем за два прыжка сдвинется ещё на вектор $2\overrightarrow{BC} = 2(\overrightarrow{OC} - \overrightarrow{OB})$, то есть в итоге за три прыжка сдвинется на вектор
$2(\overrightarrow{OA} + \overrightarrow{OC} - \overrightarrow{OB})$. Если же Коля сделает эти прыжки в порядке $CBA$, то, аналогично, сдвинется в итоге на вектор $2(\overrightarrow{OC} + \overrightarrow{OA} - \overrightarrow{OB})$, то есть попадёт в ту же самую точку, что и в предыдущем случае. Таким образом, в последовательности прыжков Коли можно поменять местами любых двух кузнечиков, стоящих через один, и это не изменит финишной точки. Значит, финишная точка характеризуется не перестановкой чисел от 1 до 2020 (которых 2020!), а только тем, какие числа в такой перестановке стоят на нечётных местах. Соответственно, различных финишных точек не может быть больше $C_{2020}^{1010}$.
Пример. Расположим кузнечиков в точках числовой прямой с координатами 0 (у Коли), 1, 3, 3², ..., 32019. Докажем, что все суммы степеней троек с коэффициентами $\pm1$ различны. Прибавив к такой сумме постоянную сумму 1 + 3 + 3² + ... + 32019, получим сумму с коэффициентами 0 и 2. Она соответствует 2020-значному троичному числу из нулей и двоек, а все такие числа различны.
Ответ
При $N = C_{2020}^{1010}$.
Замечания
1. На самом деле, почти любое расположение кузнечиков даёт $C_{2020}^{1010}$ финишных точек.
2. 7 баллов.
