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


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

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

 

(Ни­ко­лай Бе­лу­хов)

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

Ре­ше­ние.

I спо­соб. Слу­чай p=q=1 оче­ви­ден. Иначе p и q раз­лич­ны, пусть p мень­ше q. Всего ля­гуш­ка про­пры­га­ла путь, длина ко­то­ро­го де­лит­ся на p и на q, а зна­чит, и на p q, так как p и q вза­им­но про­сты. Тогда длина пути равна k p q для не­ко­то­ро­го на­ту­раль­но­го k, и ля­гуш­ка сде­ла­ла k q «ко­рот­ких» прыж­ков впра­во и k p «длин­ных» прыж­ков влево.

Из­вест­но, что при вза­им­но про­стых p и q можно пред­ста­вить d в виде d=a p минус b q с це­лы­ми a и b. Это ра­вен­ство, оче­вид­но, со­хра­нит­ся, если од­но­вре­мен­но уве­ли­чить (или умень­шить) a на q и b на p. По­это­му можно вы­брать a на­ту­раль­ным и не пре­вос­хо­дя­щим q. При этом b будет не­от­ри­ца­тель­ным (иначе d боль­ше или равно p плюс q пра­вая круг­лая скоб­ка , и так как a мень­ше или равно q, то b мень­ше p (ведь d боль­ше 0 пра­вая круг­лая скоб­ка . По­это­му a плюс b мень­ше p плюс q мень­ше или равно k левая круг­лая скоб­ка p плюс q пра­вая круг­лая скоб­ка .

Назовём каж­дую серию из a плюс b по­сле­до­ва­тель­ных прыж­ков ля­гуш­ки окном. Услов­но счи­та­ем, что за по­след­ним прыж­ком ля­гуш­ки идёт её пер­вый пры­жок (как при дви­же­нии по кругу), по­это­му окно может со­сто­ять и из не­сколь­ких по­след­них и пер­вых прыж­ков. Тогда всего окон ровно k левая круг­лая скоб­ка p плюс q пра­вая круг­лая скоб­ка штук.

Надо найти окно, где ля­гуш­ка сде­ла­ла ровно a ко­рот­ких прыж­ков (и b длин­ных)  — тогда она сдви­нет­ся на d за эти a плюс b прыж­ков. Такое окно найдётся, если есть окно, где ко­рот­ких прыж­ков не менее a, и окно, где их не более a: можно сдви­гать пер­вое окно по кругу, пока не дойдём до вто­ро­го, число ко­рот­ких прыж­ков в окне каж­дый раз ме­ня­ет­ся мак­си­мум на 1, по­это­му будет мо­мент, когда оно равно a.

Сло­жим число ко­рот­ких прыж­ков во всех окнах  — по­лу­чим k q левая круг­лая скоб­ка a плюс b пра­вая круг­лая скоб­ка , ведь каж­дый пры­жок учли a плюс b раз. Окон k левая круг­лая скоб­ка p плюс q пра­вая круг­лая скоб­ка , и в сред­нем на окно придётся  дробь: чис­ли­тель: k q левая круг­лая скоб­ка a плюс b пра­вая круг­лая скоб­ка , зна­ме­на­тель: k левая круг­лая скоб­ка p плюс q пра­вая круг­лая скоб­ка конец дроби ко­рот­ких прыж­ков. Это число равно

 дробь: чис­ли­тель: k q левая круг­лая скоб­ка a плюс b пра­вая круг­лая скоб­ка , зна­ме­на­тель: k левая круг­лая скоб­ка p плюс q пра­вая круг­лая скоб­ка конец дроби = дробь: чис­ли­тель: q a плюс q b, зна­ме­на­тель: p плюс q конец дроби = дробь: чис­ли­тель: p a плюс q a минус d, зна­ме­на­тель: p плюс q конец дроби =a минус дробь: чис­ли­тель: d, зна­ме­на­тель: p плюс q конец дроби ,

что боль­ше a минус 1 и мень­ше a. Зна­чит, найдётся окно, где ко­рот­ких прыж­ков не менее a, и окно, где их не более a.

 

II спо­соб. Ля­гуш­ку из усло­вия назовём ста­рой. Будем счи­тать, что она про­пры­ги­ва­ет свою по­сле­до­ва­тель­ность ходов бес­ко­неч­ное число раз по циклу. По­са­дим на пря­мую новую ля­гуш­ку в точку d и за­ста­вим её пры­гать ту же по­сле­до­ва­тель­ность прыж­ков, что пры­га­ет ста­рая (тоже в бес­ко­неч­ном цикле).

Мно­же­ство чисел, посещённых новой ля­гуш­кой, по­лу­ча­ет­ся из мно­же­ства чисел, посещённых ста­рой, сдви­гом на d. Если хотя бы одно число из но­во­го мно­же­ства сов­па­дет с чис­лом из ста­ро­го, то об­рат­ный сдвиг даст нам ис­ко­мую пару чисел. Пред­по­ло­жим, что этого не про­изойдёт.

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

p плюс q: d минус e= левая круг­лая скоб­ка a минус x пра­вая круг­лая скоб­ка p минус левая круг­лая скоб­ка b минус y пра­вая круг­лая скоб­ка q= левая круг­лая скоб­ка a минус x пра­вая круг­лая скоб­ка левая круг­лая скоб­ка p плюс q пра­вая круг­лая скоб­ка .

Далее пу­стим ля­гу­шек пры­гать од­но­вре­мен­но: ста­рую по про­дол­же­нию ис­ход­ной тра­ек­то­рии, а новую  — по сдви­ну­той. На каж­дом шаге раз­ность их ко­ор­ди­нат будет либо не ме­нять­ся (если они пры­га­ют в одну сто­ро­ну), либо ме­нять­ся на p плюс q (если одна пры­га­ет на +p, а дру­гая на q). Таким об­ра­зом, раз­ность все­гда будет оста­вать­ся крат­ной p плюс q; при этом она, по пред­по­ло­же­нию, не может ста­но­вить­ся ну­ле­вой, по­это­му она все­гда будет со­хра­нять знак.

Пусть ля­гуш­ки про­пры­га­ли пол­ный цикл и вер­ну­лись (новая в d, а ста­рая в e). Ко­ли­че­ство ходов в цикле обо­зна­чим через T. Сумму всех чисел, посещённых новой ля­гуш­кой (без учёта на­чаль­ной по­зи­ции), обо­зна­чим через S_1, а сумму чисел, посещённых ста­рой,  — через S. С одной сто­ро­ны, числа на со­от­вет­ству­ю­щих ходах от­ли­ча­лись не менее чем на p плюс q, причём раз­ность все­гда имела один и тот же знак, по­это­му \left|S_1 минус S| боль­ше или равно T левая круг­лая скоб­ка p плюс q пра­вая круг­лая скоб­ка . С дру­гой сто­ро­ны, набор чисел, посещённых новой ля­гуш­кой за цикл, от­ли­ча­ет­ся от ана­ло­гич­но­го на­бо­ра ста­рой ля­гуш­ки сдви­гом на d, по­это­му \left|S_1 минус S|=T d (от­ме­тим, что эти на­бо­ры могут со­дер­жать не­ко­то­рые числа по не­сколь­ко раз, если в те­че­ние цикла ля­гуш­ка по­се­ща­ла их не­од­но­крат­но). Под­став­ляя и со­кра­щая на T, по­лу­ча­ем d боль­ше или равно p плюс q, что про­ти­во­ре­чит усло­вию за­да­чи.

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

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

 \beginaligned дель­та _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 пра­вая круг­лая скоб­ка . \endaligned

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

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

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

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

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

IV спо­соб. По­сколь­ку p и q вза­им­но про­сты, ля­гуш­ка может вер­нуть­ся в ис­ход­ную точку, толь­ко сде­лав kq прыж­ков впра­во и kp прыж­ков влево, где k  — на­ту­раль­ное число. Изоб­ра­зим путь P ля­гуш­ки на це­ло­чис­лен­ной ре­шет­ке так: когда ля­гуш­ка пры­га­ет (на p) впра­во будем сдви­гать­ся на 1 впра­во, а когда пры­га­ет влево  — на 1 вверх. Ниже на ри­сун­ке слева изоб­ра­жен такой путь P для p=7, q=11, k=1 и по­сле­до­ва­тель­но­сти прыж­ков

7 минус 11 плюс 7 минус 11 плюс 7 плюс 7 минус 11 плюс 7 минус 11 плюс
 плюс 7 плюс 7 минус 11 плюс 7 минус 11 плюс 7 плюс 7 минус 11 плюс 7=0.

Как из­вест­но, най­дут­ся на­ту­раль­ные a и b, для ко­то­рых d=p a минус q b. Сдви­нув путь P на a впра­во и на b вверх, по­лу­чим новый путь Q. Выше на ри­сун­ке спра­ва изоб­ражён путь Q, по­лу­чен­ный из пути на левом ри­сун­ке для d=10, a=3 и b=1 левая круг­лая скоб­ка 10=7 умно­жить на 3 минус 11 умно­жить на 1 пра­вая круг­лая скоб­ка . Если P и Q имеют общую точку  левая круг­лая скоб­ка x, y пра­вая круг­лая скоб­ка , то точка  левая круг­лая скоб­ка x минус a, y минус b пра­вая круг­лая скоб­ка также лежит на P. Со­от­вет­ству­ю­щие по­ло­же­ния ля­гуш­ки на чис­ло­вой пря­мой равны p левая круг­лая скоб­ка x минус a пра­вая круг­лая скоб­ка минус q левая круг­лая скоб­ка y минус b пра­вая круг­лая скоб­ка и p x минус q y, а

 левая круг­лая скоб­ка p x минус q y пра­вая круг­лая скоб­ка минус левая круг­лая скоб­ка p левая круг­лая скоб­ка x минус a пра­вая круг­лая скоб­ка минус q левая круг­лая скоб­ка y минус b пра­вая круг­лая скоб­ка пра­вая круг­лая скоб­ка =p a минус q b=d,

что и тре­бо­ва­лось. То же будет верно, если путь Q имеет общую точку с рас­ши­рен­ным путем \mathbfP, по­лу­чен­ным до­бав­ле­ни­ем к P его копий, по­лу­чен­ны­ми сдви­га­ми на  левая круг­лая скоб­ка kq, kp пра­вая круг­лая скоб­ка , левая круг­лая скоб­ка 2kq, 2kp пра­вая круг­лая скоб­ка и т. д.

Пред­по­ло­жим, что общих точек у путей \mathbfP и Q нет, на­при­мер, Q лежит ниже \mathbfP. На ри­сун­ке спра­ва \mathbfP со­сто­ит из двух копий P, а Q по­лу­чен из P сдви­гом, со­от­вет­ству­ю­щим d=20, a=6, b=2  левая круг­лая скоб­ка 20=7 умно­жить на 6 минус 11 умно­жить на 2 пра­вая круг­лая скоб­ка .

Рас­смот­рим за­штри­хо­ван­ную фи­гу­ру F, рас­по­ло­жен­ную «между» \mathbfP и Q, и наи­мень­ший со­дер­жа­щий её пря­мо­уголь­ник (его раз­ме­ры k q \times левая круг­лая скоб­ка k p плюс l пра­вая круг­лая скоб­ка , где l  — на­ту­раль­ное число). Когда Q сов­па­да­ет с P, пло­щадь S левая круг­лая скоб­ка F пра­вая круг­лая скоб­ка равна 0 . Сдвиг на a впра­во уве­ли­чил эту пло­щадь на kpa, а сдвиг на b вверх умень­шил её на kqb. Зна­чит, S левая круг­лая скоб­ка F пра­вая круг­лая скоб­ка =k левая круг­лая скоб­ка p a минус q b пра­вая круг­лая скоб­ка =k d.

Оце­ним пло­щадь F снизу дру­гим спо­со­бом. Фи­гу­ру F можно раз­бить на k q вер­ти­каль­ных по­ло­сок тол­щи­ной в одну клет­ку. В каж­дой по­лос­ке есть ми­ни­мум одна клет­ка (ниж­няя). Фи­гу­ру F пе­ре­се­ка­ют по внут­рен­ним от­рез­кам k p плюс l минус 1 го­ри­зон­таль­ных линий сетки. В каж­дой вер­ти­каль­ной по­лос­ке кле­ток хотя-бы на одну боль­ше, чем ко­ли­че­ство пе­ре­се­ка­ю­щих её линий, т. к. есть клет­ка прямо под каж­дой ли­ни­ей, и клет­ка выше самой верх­ней линии. Зна­чит, общая пло­щадь F не менее k q плюс kp плюс l минус 1 кле­ток, что не мень­ше k левая круг­лая скоб­ка p плюс q пра­вая круг­лая скоб­ка кле­ток. Это про­ти­во­ре­чит не­ра­вен­ству d мень­ше p плюс q.

В каж­дой вер­ти­каль­ной по­лос­ке кле­ток хотя-бы на одну боль­ше чем ко­ли­че­ство пе­ре­се­ка­ю­щих её линий, т. к. есть клет­ка прямо под каж­дой ли­ни­ей, и клет­ка выше самой верх­ней линии.