Пусть в мо­мент вре­ме­ни k ля­гуш­ка на­хо­дит­ся в точке a_k, Про­дол­жим по­сле­до­ва­тель­ность (a_i) пе­ри­о­ди­че­ски по пра­ви­лу Обо­зна­чим За­ме­тим, что по­это­му для лю­бо­го n.

Так как p и q вза­им­но про­стые, то p и A вза­им­но про­стые. До­ка­жем, что най­дет­ся такое целое s, что В самом деле, числа 0, p, 2p, ..., дают раз­лич­ные остат­ки при де­ле­нии на A (иначе для не­ко­то­рых по­лу­ча­ем, что чего не может быть, так как не де­лит­ся на A, а p вза­им­но про­сто с A). А зна­чит, среди этих остат­ков есть и d.

Обо­зна­чим Легко ви­деть, что все дают оста­ток d от де­ле­ния на A.

Если a_k  — самая левая из точек, по­се­щен­ных ля­гуш­кой, то Если a_k  — самая пра­вая точка, то Зна­чит, при не­ко­то­ром i в по­сле­до­ва­тель­но­сти r_i про­ис­хо­дит пе­ре­ме­на знака, и Тогда по­то­му что

А так как то что и тре­бо­ва­лось.

При­ве­дем дру­гое ре­ше­ние.

Пред­по­ло­жим, что для ка­ко­го-то такие точки не най­дут­ся.

Лемма. Най­дут­ся такие целые a и b, что

До­ка­за­тель­ство леммы. Рас­смот­рим числа ар–d при Если хотя бы одно из них де­лит­ся на q, то есть имеет вид bq, то мы по­лу­ча­ем что и тре­бу­ет­ся. В ином слу­чае какие-то два их этих чисел дают оди­на­ко­вый оста­ток от де­ле­ния на q (так как их всего ровно q и остат­ка 0 там нет). Тогда

от­ку­да Тогда, так как p и q вза­им­но про­сты, a₁–a₂ крат­но q; но в диа­па­зо­не от 2 до все числа от­ли­ча­ют­ся менее чем на q, то есть этот слу­чай не­воз­мо­жен. Лемма до­ка­за­на.

Мы можем уве­ли­чить a на q, а b на p  — со­от­но­ше­ние при этом не на­ру­шит­ся. Будем де­лать так до тех пор, пока не до­бьем­ся

Пусть ля­гуш­ка вер­ну­лась в 0, сде­лав n шагов впра­во и m шагов влево. Тогда а зна­чит, Будем счи­тать, что ля­гуш­ка про­пры­ги­ва­ет эту по­сле­до­ва­тель­ность ходов бес­ко­неч­ное число раз по циклу; ясно, что точки она при этом будет по­се­щать те же.

Возь­мем Рас­ста­вим по кругу буквы, опи­сы­ва­ю­щие под­ряд иду­щих ходов ля­гуш­ки. Будем вы­пи­сы­вать их по ча­со­вой стрел­ке, по одной букве на ход; если это ход впра­во, на­пи­шем букву «П», а если ход влево  — «Л». Всего мы рас­ста­ви­ли по кругу nk букв «П» и mk букв «Л».

Пусть мы най­дем от­ре­зок из под­ряд иду­щих букв, среди ко­то­рых ровно a раз встре­ча­ет­ся «П» (и ровно b раз «Л»). Тогда эти буквы со­от­вет­ству­ют по­сле­до­ва­тель­ным ходам, за ко­то­рые ля­гуш­ка сдви­ну­лась ровно на ap Про­ти­во­ре­чие. Зна­чит, ни на каком таком от­рез­ке буква «П» не может встре­чать­ся a раз.

Рас­смот­рим какой-то от­ре­зок из под­ряд иду­щих букв. Пусть буква «П» встре­ча­ет­ся на нем не более чем раз. По­смот­рим на от­ре­зок из букв, от­ли­ча­ю­щий­ся от преды­ду­ще­го сдви­гом на 1 по ча­со­вой стрел­ке, то есть по­лу­чив­ший­ся вы­ки­ды­ва­ни­ем одной буквы и до­бав­ле­ни­ем дру­гой. За­ме­тим, что на новом от­рез­ке буква «П» встре­ча­ет­ся не более чем раз, а так как ровно a быть не может, то тоже не более чем раз. По­вто­рив эти рас­суж­де­ния, по­лу­чим, что на любом от­рез­ке такой длины буква «П». встре­ча­ет­ся не более чем раз. Мы можем рас­смот­реть сред­нее ко­ли­че­ство букв «П». во всех на­бо­рах под­ряд иду­щих букв и сде­лать вывод, что доля букв «П» во всем круге не более Зна­чит, от­но­ше­ние ко­ли­че­ства букв «П» к ко­ли­че­ству букв «Л» во всем круге не пре­вос­хо­дит

Ана­ло­гич­но, если на каком-то от­рез­ке из под­ряд иду­щих букв буква «П» встре­ча­ет­ся не менее чем раз, то от­но­ше­ние ко­ли­че­ства букв «П» во всем круге к ко­ли­че­ству букв «Л» не менее Сле­до­ва­тель­но, либо либо При этом Чтобы прий­ти к про­ти­во­ре­чию, нам до­ста­точ­но по­ка­зать, что

Левое не­ра­вен­ство эк­ви­ва­лент­но что сле­ду­ет из Пра­вое не­ра­вен­ство ана­ло­гич­но эк­ви­ва­лент­но что сле­ду­ет из

Мы при­шли к про­ти­во­ре­чию, зна­чит, точки на рас­сто­я­нии d най­дут­ся.

При­ве­дем еще одно ре­ше­ние.

Как и в преды­ду­щем ре­ше­нии, будем счи­тать, что ля­гуш­ка пры­га­ет в бес­ко­неч­ном цикле. Также вос­поль­зу­ем­ся пред­став­ле­ни­ем для по­ло­жи­тель­ных a и b, сумму обо­зна­чив за r.

За δ_i обо­зна­чим раз­ность между по­ло­же­ни­я­ми ля­гуш­ки в мо­мент (то есть через шагов после на­ча­ла) и в мо­мент i. Так как их раз­де­ля­ет r шагов, то

Если δ_i равно d, то мы нашли ис­ко­мые по­зи­ции. Пред­по­ло­жим про­тив­ное: пусть для всех i. Тогда все числа δ_i имеют вид для целых

За­ме­тим, что раз­ность между δ_i и опре­де­ля­ет­ся тем, ка­ки­ми были -й и -й шаги; разо­брав слу­чаи, не­труд­но убе­дить­ся, что она равна 0 или Это озна­ча­ет, что числа δ_i либо все мень­ше 0 (имеют вид для на­ту­раль­но­го k), либо все боль­ше 0 (имеют вид для на­ту­раль­но­го k).

Тогда рас­смот­рим по­зи­цию ля­гуш­ки через rT шагов, где T  — ко­ли­че­ство шагов в ее цикле. С одной сто­ро­ны, она равна сумме

ко­то­рая по до­ка­зан­но­му выше долж­на быть либо от­ри­ца­тель­ной, либо по­ло­жи­тель­ной. С дру­гой сто­ро­ны, через rT шагов ля­гуш­ка вер­нет­ся на по­зи­цию 0. Про­ти­во­ре­чие.