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$. Таким образом, мы посетим все точки.