Question

На окружности отмечено 2020 точек. Лягушонок прыгает с одной отмеченной точки на другую, двигаясь по часовой стрелке. За один прыжок он может перепрыгнуть через 99 или через 100 отмеченных точек. Сможет ли лягушонок побывать во всех отмеченных точках ровно по одному разу и вернуться в ту же точку, с которой стартовал?

Answer 1

Пусть лягушонок стартует в точке $x_{0}$. Тогда, если какие-то две точки повторились, то лягушонок побывал также в точке $x_{0}$ дважды, т.е. мы попали в цикл. Если мы покажем, что уравнение $100l+99k=2020m+r,\; 0\leq r\leq 2019$ имеет решение при любом $r$, то цикл будет состоять из всех точек, и лягушонок побывает во всех точках по одному разу, а затем вернется в точку $x_{0}$;

Докажем для начала, что если существует решение для остатков $i,j$, то существует решение для остатка $i+j$. Это вполне очевидно: просто сложим два уравнения для остатков $i,j$. Теперь, в частности, если существует решение для $j=1$, то существует решение для всех остатков. То есть нам надо решить диофантово уравнение $100x+99y-2020z=1$; Для этого сразу положим $z=1$; Пусть $y=21$;

Тогда из числа $99\times 20=1980$ нам нужно получить число $2021$; Но мы умеем прибавлять единицу: $1=100-99$. То есть $99\times 20 +(100-99)+...+(100-99)=100\times41+99\times (-21)-2020=1$; Иными словами, получили решение $x=41,\;y=-21,\;z=1$, но нам нужно решение в натуральных числах. Не вопрос: добавим к $y$ 2020, а к $z$ добавим 99. Получим решение: $x=41,\; y=1999,\; z=100$.

Итак, план действий следующий.

Пусть мы находимся в точке $x_{0}$. Прыгаем 41 раз на 100 и 1999 раз на 99. Теперь мы в точке $x_{0}+1$. Таким образом, мы посетим все точки.

Answer 2

Да, лягушонок сможет побывать во всех отмеченных точках ровно по одному разу и вернуться в исходную точку.

Для начала, заметим, что лягушонок перепрыгивает через точки с номерами, кратными 99 или 100. Таким образом, после каждого прыжка он оказывается в точке с номером, отличным от предыдущей на 99 или 100.

Так как на окружности отмечено 2020 точек, мы можем представить эти точки в виде 101 последовательных групп по 20 точек в каждой. Внутри каждой группы лягушонок будет перепрыгивать через точки с номерами, отличными друг от друга на 99 или 100. Для перехода между группами, лягушонок может перепрыгнуть через 100 точек (одну из последних точек в одной группе и первую точку в следующей группе).

Таким образом, лягушонок сможет побывать внутри каждой группы точек ровно по одному разу и перейти от одной группы к другой, не пропуская ни одной точки. В конце, лягушонок вернется в исходную точку, совершив обратный прыжок через 100 точек.

Таким образом, лягушонок сможет побывать во всех отмеченных точках ровно по одному разу и вернуться в ту же точку, с которой стартовал.