Назад
Задача

На плоскости сидят кузнечик Коля и 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}$.

Чтобы оставлять комментарии, войдите или зарегистрируйтесь

Комментариев нет