сайты - меню - вход - но­во­сти


Задания
Версия для печати и копирования в MS Word

Пусть p и q  — вза­им­но про­стые на­ту­раль­ные числа. Ля­гуш­ка пры­га­ет по чис­ло­вой пря­мой, на­чи­ная в точке 0, каж­дый раз либо на p впра­во, либо на q влево. Од­на­ж­ды ля­гуш­ка вер­ну­лась в 0. До­ка­жи­те, что для лю­бо­го на­ту­раль­но­го d мень­ше p плюс q най­дут­ся два числа, по­се­щен­ные ля­гуш­кой и от­ли­ча­ю­щи­е­ся на d.

Спрятать решение

Ре­ше­ние.

Пусть в мо­мент вре­ме­ни k ля­гуш­ка на­хо­дит­ся в точке ak, a_0=a_N=0. Про­дол­жим по­сле­до­ва­тель­ность (ai) пе­ри­о­ди­че­ски по пра­ви­лу a_i плюс N=a_i. Обо­зна­чим A=p плюс q . За­ме­тим, что  минус q \equiv p \bmod A, по­это­му a_n\equiv n p \bmod A для лю­бо­го n.

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

Обо­зна­чим r_k=a_8 плюс k минус a_k. Легко ви­деть, что все r_k дают оста­ток d от де­ле­ния на A.

Если ak  — самая левая из точек, по­се­щен­ных ля­гуш­кой, то r_k боль­ше 0. Если ak  — самая пра­вая точка, то r_k мень­ше 0. Зна­чит, при не­ко­то­ром i в по­сле­до­ва­тель­но­сти ri про­ис­хо­дит пе­ре­ме­на знака, r_i мень­ше 0 и r_i плюс 1 боль­ше 0. Тогда r_i плюс 1 мень­ше A, по­то­му что

 r_i плюс 1 минус r_i= левая круг­лая скоб­ка a_i плюс s плюс 1 минус a_i плюс 8 пра­вая круг­лая скоб­ка минус левая круг­лая скоб­ка a_i плюс 1 минус a_i пра­вая круг­лая скоб­ка мень­ше или равно p минус левая круг­лая скоб­ка минус q пра­вая круг­лая скоб­ка =A.

А так как r_i плюс 1 \equiv d \bmod A, то r_i плюс 1=d, что и тре­бо­ва­лось.

 

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

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

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

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

 левая круг­лая скоб­ка a_1 p минус d пра­вая круг­лая скоб­ка минус левая круг­лая скоб­ка a_2 p минус d пра­вая круг­лая скоб­ка =q k,

от­ку­да p левая круг­лая скоб­ка a_1 минус a_2 пра­вая круг­лая скоб­ка =q k. Тогда, так как p и q вза­им­но про­сты, a1a2 крат­но q; но в диа­па­зо­не от 2 до q плюс 1 все числа от­ли­ча­ют­ся менее чем на q, то есть этот слу­чай не­воз­мо­жен. Лемма до­ка­за­на.

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

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

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

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

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

Ана­ло­гич­но, если на каком-то от­рез­ке из a плюс b под­ряд иду­щих букв буква «П» встре­ча­ет­ся не менее чем a плюс 1 раз, то от­но­ше­ние ко­ли­че­ства букв «П» во всем круге к ко­ли­че­ству букв «Л» не менее  дробь: чис­ли­тель: a плюс 1, зна­ме­на­тель: b минус 1 конец дроби . Сле­до­ва­тель­но, либо  дробь: чис­ли­тель: n k, зна­ме­на­тель: m k конец дроби мень­ше или равно дробь: чис­ли­тель: a минус 1, зна­ме­на­тель: b плюс 1 конец дроби , либо  дробь: чис­ли­тель: n k, зна­ме­на­тель: m k конец дроби боль­ше или равно дробь: чис­ли­тель: a плюс 1, зна­ме­на­тель: b минус 1 конец дроби . При этом  дробь: чис­ли­тель: n k, зна­ме­на­тель: m k конец дроби = дробь: чис­ли­тель: n, зна­ме­на­тель: m конец дроби = дробь: чис­ли­тель: q, зна­ме­на­тель: p конец дроби . Чтобы прий­ти к про­ти­во­ре­чию, нам до­ста­точ­но по­ка­зать, что

 дробь: чис­ли­тель: a минус 1, зна­ме­на­тель: b плюс 1 конец дроби мень­ше дробь: чис­ли­тель: q, зна­ме­на­тель: p конец дроби мень­ше дробь: чис­ли­тель: a плюс 1, зна­ме­на­тель: b минус 1 конец дроби .

Левое не­ра­вен­ство эк­ви­ва­лент­но  левая круг­лая скоб­ка a минус 1 пра­вая круг­лая скоб­ка p мень­ше левая круг­лая скоб­ка b плюс 1 пра­вая круг­лая скоб­ка q, что сле­ду­ет из a p минус b q=d мень­ше p плюс q. Пра­вое не­ра­вен­ство ана­ло­гич­но эк­ви­ва­лент­но  левая круг­лая скоб­ка a плюс 1 пра­вая круг­лая скоб­ка p боль­ше левая круг­лая скоб­ка b минус 1 пра­вая круг­лая скоб­ка q, что сле­ду­ет из a p минус b q=d боль­ше минус p минус q.

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

 

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

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

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

 дель­та _i =x p минус левая круг­лая скоб­ка r минус x пра­вая круг­лая скоб­ка q=a p плюс левая круг­лая скоб­ка x минус a пра­вая круг­лая скоб­ка p минус b q минус левая круг­лая скоб­ка r минус x минус b пра­вая круг­лая скоб­ка q=
=d плюс левая круг­лая скоб­ка x минус a пра­вая круг­лая скоб­ка p плюс левая круг­лая скоб­ка x минус левая круг­лая скоб­ка r минус b пра­вая круг­лая скоб­ка пра­вая круг­лая скоб­ка q=d плюс левая круг­лая скоб­ка x минус a пра­вая круг­лая скоб­ка левая круг­лая скоб­ка p плюс q пра­вая круг­лая скоб­ка .

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

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

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

 дель­та _0 плюс дель­та _r плюс дель­та _2 r плюс \ldots плюс дель­та _r левая круг­лая скоб­ка T минус 1 пра­вая круг­лая скоб­ка ,

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