МОШ 2021, 10 класс, задача 5
Пусть и — взаимно простые натуральные числа. Лягушка прыгает по числовой прямой, начиная в точке , каждый раз либо на вправо, либо на влево. Однажды лягушка вернулась в . Докажите, что для любого натурального найдутся два числа, посещённые лягушкой и отличающиеся на .
(Н. Белухов)
Решение. Пусть в момент времени лягушка находится в точке , . Продолжим последовательность периодически по правилу . Обозначим . Заметим, что , поэтому для любого .
Так как и взаимно простые, то и взаимно простые. Докажем, что найдётся такое целое , что .
В самом деле, числа , , , , дают различные остатки при делении на (иначе для некоторых получаем что , чего не может быть так как не делится на , а взаимно просто с ). А значит, среди этих остатков есть и .
Обозначим . Легко видеть, что все дают остаток от деления на .
Если самая левая из точек, посещённых лягушкой, то . Если самая правая точка, то . Значит, при некотором в последовательности происходит перемена знака, и . Тогда , потому что
А так как , то , что и требовалось.