Пусть p и q — взаимно простые натуральные числа. Лягушка прыгает по числовой прямой, начиная в точке 0. Каждый раз она прыгает либо на p вправо, либо на q влево. Однажды лягушка вернулась в 0. Докажите, что для любого натурального 
найдутся два числа, посещённые лягушкой и отличающиеся ровно на d.
(Николай Белухов)
I способ. Случай 
очевиден. Иначе p и q различны, пусть 
Всего лягушка пропрыгала путь, длина которого делится на p и на q, а значит, и на 
так как p и q взаимно просты. Тогда длина пути равна 
для некоторого натурального k, и лягушка сделала 
«коротких» прыжков вправо и 
«длинных» прыжков влево.
Известно, что при взаимно простых p и q можно представить d в виде 
с целыми a и b. Это равенство, очевидно, сохранится, если одновременно увеличить (или уменьшить) a на q и b на p. Поэтому можно выбрать a натуральным и не превосходящим q. При этом b будет неотрицательным (иначе 
и так как 
то 
(ведь 
Назовём каждую серию из 
последовательных прыжков лягушки окном. Условно считаем, что за последним прыжком лягушки идёт её первый прыжок (как при движении по кругу), поэтому окно может состоять и из нескольких последних и первых прыжков. Тогда всего окон ровно 
штук.
Надо найти окно, где лягушка сделала ровно a коротких прыжков (и b длинных) — тогда она сдвинется на d за эти прыжков. Такое окно найдётся, если есть окно, где коротких прыжков не менее a, и окно, где их не более a: можно сдвигать первое окно по кругу, пока не дойдём до второго, число коротких прыжков в окне каждый раз меняется максимум на 1, поэтому будет момент, когда оно равно a.
Сложим число коротких прыжков во всех окнах — получим 
ведь каждый прыжок учли раз. Окон 
и в среднем на окно придётся 
коротких прыжков. Это число равно
что больше 
и меньше a. Значит, найдётся окно, где коротких прыжков не менее a, и окно, где их не более a.
II способ. Лягушку из условия назовём старой. Будем считать, что она пропрыгивает свою последовательность ходов бесконечное число раз по циклу. Посадим на прямую новую лягушку в точку d и заставим её прыгать ту же последовательность прыжков, что прыгает старая (тоже в бесконечном цикле).
Множество чисел, посещённых новой лягушкой, получается из множества чисел, посещённых старой, сдвигом на d. Если хотя бы одно число из нового множества совпадет с числом из старого, то обратный сдвиг даст нам искомую пару чисел. Предположим, что этого не произойдёт.
Как и в предыдущем решении, представим число d в виде 
для некоторых неотрицательных a и b. Заставим старую лягушку пропрыгать ходов по её циклу; она окажется в точке 
где 
Так как 
разность координат новой и старой лягушек кратна
Далее пустим лягушек прыгать одновременно: старую по продолжению исходной траектории, а новую — по сдвинутой. На каждом шаге разность их координат будет либо не меняться (если они прыгают в одну сторону), либо меняться на 
(если одна прыгает на 
при этом она, по предположению, не может становиться нулевой, поэтому она всегда будет сохранять знак.
Пусть лягушки пропрыгали полный цикл и вернулись (новая в d, а старая в e). Количество ходов в цикле обозначим через T. Сумму всех чисел, посещённых новой лягушкой (без учёта начальной позиции), обозначим через 
а сумму чисел, посещённых старой, — через S. С одной стороны, числа на соответствующих ходах отличались не менее чем на 
причём разность всегда имела один и тот же знак, поэтому 
С другой стороны, набор чисел, посещённых новой лягушкой за цикл, отличается от аналогичного набора старой лягушки сдвигом на d, поэтому 
(отметим, что эти наборы могут содержать некоторые числа по несколько раз, если в течение цикла лягушка посещала их неоднократно). Подставляя и сокращая на T, получаем 
что противоречит условию задачи.
III способ. Как и в решении 2, будем считать, что лягушка прыгает в бесконечном цикле. Также воспользуемся представлением для неотрицательных a и b, сумму обозначив через r.
Через 
обозначим разность между положениями лягушки в момент 
(то есть через шагов после начала) и в момент i. Так как их разделяет r шагов, то
Если равно d, то мы нашли искомые позиции. Предположим противное, пусть 
для всех i. Тогда все числа имеют вид 
для целых 
Заметим, что разность между и 
определяется тем, какими были 
-й
-й
или 
Это означает, что числа либо все меньше 0, либо все больше 
Рассмотрим позицию лягушки через rT шагов, где T — количество шагов в её цикле. С одной стороны, она равна сумме
которая по доказанному выше должна быть либо отрицательной, либо положительной. С другой стороны, через rT шагов лягушка вернётся на позицию 0. Противоречие.
IV способ. Поскольку p и q взаимно просты, лягушка может вернуться в исходную точку, только сделав kq прыжков вправо и kp прыжков влево, где k — натуральное число. Изобразим путь P лягушки на целочисленной решетке так: когда лягушка прыгает (на p) вправо будем сдвигаться на 1 вправо, а когда прыгает влево — на 1 вверх. Ниже на рисунке слева изображен такой путь P для 
и последовательности прыжков
Как известно, найдутся натуральные a и b, для которых 
Сдвинув путь P на a вправо и на b вверх, получим новый путь Q. Выше на рисунке справа изображён путь Q, полученный из пути на левом рисунке для 
и 
Если P и Q имеют общую точку 
то точка 
также лежит на P. Соответствующие положения лягушки на числовой прямой равны 
и 
а
что и требовалось. То же будет верно, если путь Q имеет общую точку с расширенным путем 
полученным добавлением к P его копий, полученными сдвигами на 
и т. д.
Предположим, что общих точек у путей 
и Q нет, например, Q лежит ниже 
На рисунке справа состоит из двух копий P, а Q получен из P сдвигом, соответствующим 
Рассмотрим заштрихованную фигуру F, расположенную «между» и Q, и наименьший содержащий её прямоугольник (его размеры 
где l — натуральное число). Когда Q совпадает с P, площадь 
равна 0 . Сдвиг на a вправо увеличил эту площадь на kpa, а сдвиг на b вверх уменьшил её на 
Значит, 
Оценим площадь F снизу другим способом. Фигуру F можно разбить на вертикальных полосок толщиной в одну клетку. В каждой полоске есть минимум одна клетка (нижняя). Фигуру F пересекают по внутренним отрезкам 
горизонтальных линий сетки. В каждой вертикальной полоске клеток хотя-бы на одну больше, чем количество пересекающих её линий, т. к. есть клетка прямо под каждой линией, и клетка выше самой верхней линии. Значит, общая площадь F не менее 
клеток, что не меньше клеток. Это противоречит неравенству 
В каждой вертикальной полоске клеток хотя-бы на одну больше чем количество пересекающих её линий, т. к. есть клетка прямо под каждой линией, и клетка выше самой верхней линии.