Раз­ность двух таких чисел, в ко­то­рых число восьмёрок раз­ли­ча­ет­ся на 1 , имеет вид Но то есть де­лит­ся на 47, как и 2021. По­это­му, до­бав­ляя восьмёрки по одной, мы будем по­лу­чать числа, де­ля­щи­е­ся на 47.

Де­ле­ние с остат­ком кучи кон­фет на k детей можно пред­став­лять себе так: мы рас­кла­ды­ва­ем кон­фе­ты на k кучек, ко­то­рые либо оди­на­ко­вы (если оста­ток 0), либо в части кучек кон­фет на 1 боль­ше, чем в осталь­ных (ко­ли­че­ство таких куч равно остат­ку).

Пусть пер­вый ребёнок раз­ло­жит так кон­фе­ты на кучки, рас­по­ло­жив кучи слева на­пра­во по воз­рас­та­нию числа кон­фет в них. Можно счи­тать, что он возьмёт себе пра­вую кучку, если он маль­чик, или левую, если он  — де­воч­ка.

Когда зайдёт сле­ду­ю­щий ребёнок, кон­фе­ты уже будут раз­ло­же­ны на кучки, как если бы он сам делил с остат­ком (ведь и число детей, и число куч умень­ши­лось на 1), и снова маль­чик возьмёт пра­вую кучу, а де­воч­ка  — левую, и т. д. В итоге маль­чи­ки возь­мут все пра­вые кучки в ко­ли­че­стве, рав­ном числу маль­чи­ков, что не за­ви­сит от по­ряд­ка детей в оче­ре­ди.

I спо­соб. Вы­бе­рем лю­бо­го або­ри­ге­на  — будем на­зы­вать его Петей,  — и по­ка­жем, как найти его воз­раст. Мыс­лен­но на­де­нем на каж­до­го вто­ро­го або­ри­ге­на шапку, на­чи­ная с Пети. За­ну­ме­ру­ем або­ри­ге­нов без шапок, иду­щих за Петей по ча­со­вой стрел­ке:

За­ме­тим, что каж­дый або­ри­ген верно со­об­ща­ет сумму воз­рас­тов своих со­се­дей (если сло­жить на­зван­ные або­ри­ге­ном числа). Сло­жим числа, на­зван­ные 1-м, 3-м, ..., 25-м або­ри­ге­на­ми без шапок  — это будет сумма воз­рас­тов всех або­ри­ге­нов в шап­ках плюс воз­раст Пети. Сло­жим числа, на­зван­ные 2-м, 4-м, ..., 24-м або­ри­ге­на­ми без шапок  — это будет сумма воз­рас­тов всех або­ри­ге­нов в шап­ках минус воз­раст Пети. Вычтя из пер­вой суммы вто­рую и по­де­лив на 2, по­лу­чим воз­раст Пети.

Зная воз­раст лю­бо­го або­ри­ге­на, легко узнать, кто его со­се­ди, по их от­ве­там.

Ответ: все­гда.

II спо­соб. Для удоб­ства будем счи­тать, что в круге стоят через од­но­го 25 муж­чин и 25 жен­щин. По­ка­жем, как раз­ли­чить муж­чин (жен­щи­ны опре­де­ля­ют­ся ана­ло­гич­но). За­ме­тим, что два вы­ска­зы­ва­ния о воз­расте одной жен­щи­ны от­ли­ча­ют­ся на 1 тогда и толь­ко тогда, когда ее со­се­ди  — ры­царь и лжец. По­это­му до­ста­точ­но опо­знать од­но­го муж­чи­ну: далее по кругу опре­де­ля­ют­ся все осталь­ные.

Раз­берём два слу­чая.

1)  Для одной из жен­щин вы­ска­зы­ва­ния об её воз­расте раз­ли­ча­ют­ся на 2. Тогда оба её со­се­да  — лжецы, и, как ска­за­но выше, все муж­чи­ны опре­де­ля­ют­ся.

2)  Таких жен­щин нет. Все муж­чи­ны раз­би­ва­ют­ся на груп­пы: внут­ри такой груп­пы оба со­се­да каж­дой жен­щи­ны го­во­рят об её воз­расте одно и то же. Но пока не из­вест­но, какие груп­пы со­сто­ят из лже­цов, а какие  — из ры­ца­рей.

Сло­жив все числа, на­зван­ные муж­чи­на­ми, по­лу­чим удво­ен­ную сумму воз­рас­тов жен­щин. Те­перь сло­жим пер­вые числа, на­зван­ные муж­чи­на­ми. Если по­лу­чен­ная сумма имеет ту же чётность, что сумма воз­рас­тов жен­щин, то среди муж­чин чётное число лже­цов, а если не сов­па­да­ет  — нечётное. По­сколь­ку из двух воз­мож­ных ва­ри­ан­тов ко­ли­че­ство лже­цов чётно толь­ко в одном, пу­те­ше­ствен­ник опре­де­лит, какой из ва­ри­ан­тов пра­виль­ный.

Вме­сто ис­ход­но­го пря­мо­уголь­ни­ка M будем рас­смат­ри­вать пря­мо­уголь­ник N с вер­ши­на­ми в уг­ло­вых лам­поч­ках.

Оцен­ки. За­ме­тим, что каж­дым ходом за­жи­га­ет­ся хотя бы одна из четырёх уг­ло­вых лам­по­чек. Сле­до­ва­тель­но, ходов не боль­ше 4. В п. а) за­ме­тим ещё, что мы долж­ны на каком-то ходу за­жечь цен­траль­ную лам­поч­ку. Вме­сте с ней по одну сто­ро­ну от про­ведённой пря­мой ока­жет­ся хотя бы две уг­ло­вых лам­поч­ки (по­сколь­ку пря­мая, па­рал­лель­ная про­ведённой и про­хо­дя­щая через центр, делит квад­рат N на две сим­мет­рич­ные от­но­си­тель­но цен­тра части).

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

б) Пря­мо­уголь­ник N имеет раз­ме­ры На его диа­го­на­ли нет дру­гих лам­по­чек, по­сколь­ку 19 и 20 вза­им­но про­сты. Про­ведём первую пря­мую па­рал­лель­но диа­го­на­ли, чуть ниже, чтобы эти две лам­поч­ки ока­за­лись над ней, а все осталь­ные лам­поч­ки оста­лись с той же сто­ро­ны, что и до этого; зажжём все лам­поч­ки ниже этой пря­мой. Ана­ло­гич­но про­ведём вто­рую пря­мую па­рал­лель­но диа­го­на­ли, но чуть выше, и зажжём все лам­поч­ки выше этой пря­мой, как на ри­сун­ке. (Для при­ме­ра мы взяли N раз­ме­ром   — по­мень­ше, но тоже с вза­им­но про­сты­ми сто­ро­на­ми.) Остав­ши­е­ся две уг­ло­вые лам­поч­ки можно за­жечь за два хода, от­се­кая пря­мой от осталь­ных.

Ответ: а) 3 хода; б) 4 хода.

Пусть или

Ал­го­ритм. Мыс­лен­но раз­де­лим но­ме­ра на 100 участ­ков по но­ме­ров, а в слу­чае нечётного k остав­ший­ся номер объ­явим за­пас­ным. Пусть i-й ту­рист сна­ча­ла про­ве­ря­ет все но­ме­ра i-го участ­ка, дви­га­ясь слева на­пра­во, потом идёт в за­пас­ной номер (если тот есть), а потом про­ве­ря­ет но­ме­ра -го участ­ка, но спра­ва на­ле­во (если про­ве­ря­ет 1-й уча­сток). Ни­ка­кие два ту­ри­ста не по­па­дут при этом в один номер, так как сум­мар­но на двух их участ­ках (вклю­чая за­пас­ной номер, если он есть), всего но­ме­ра.

Оцен­ка. Для того чтобы каж­дый из 100 ту­ри­стов мог га­ран­ти­ро­ван­но за­се­лить­ся в номер не на ре­мон­те, он дол­жен с са­мо­го на­ча­ла иметь спи­сок из раз­лич­ных но­ме­ров, в ко­то­рые будет за­хо­дить. Можно счи­тать, что спис­ки не ме­ня­ют­ся по ходу за­се­ле­ния дру­гих ту­ри­стов (по­сколь­ку ни­ка­кой ин­фор­ма­ции о них мы не узнаём).

Рас­смот­рим для каж­до­го ту­ри­ста пер­вые но­ме­ров из его спис­ка. Все эти чисел раз­лич­ны, иначе два ту­ри­ста с сов­пав­шим чис­лом могут оба по­пасть в этот номер (если их преды­ду­щие но­ме­ра, ко­то­рых сум­мар­но не боль­ше все на ре­мон­те). Сле­до­ва­тель­но,

При чётном k этой оцен­ки до­ста­точ­но. В слу­чае нечётного k, если у ка­ко­го-то ту­ри­ста, ска­жем, Пети, -й номер сов­па­да­ет с каким-то из «пер­вых» но­ме­ров, ска­жем, с Ва­си­ным, то когда у Пети пер­вые но­ме­ров будут на ре­мон­те, а у Васи  — все но­ме­ра до сов­па­да­ю­ще­го с Пе­ти­ным (их не более будут на ре­мон­те, они по­па­дут в один номер. Зна­чит, все -е но­ме­ра от­лич­ны от пер­вых (хотя могут сов­па­дать друг с дру­гом), то есть

За­ме­ча­ние. Для чётного числа ту­ри­стов (а их у нас 100), ал­го­ритм можно опи­сать не­сколь­ко иначе.

При чётном k мыс­лен­но пред­ста­вим план отеля как 50 ко­ри­до­ров, в каж­дом из ко­то­рых вдоль одной стены рас­по­ло­же­ны двери но­ме­ров. Каж­дой паре ту­ри­стов «от­да­дим» один ко­ри­дор по ко­то­ро­му они дви­га­ют­ся с про­ти­во­по­лож­ных кон­цов, про­ве­ряя все встре­чен­ные ком­на­ты. В сумме эта пара может об­на­ру­жить не более k ре­мон­ти­ру­ю­щих­ся но­ме­ров, по­это­му два сво­бод­ных но­ме­ра для них оста­нут­ся.

При нечётном k пред­ста­вим ко­ри­до­ры отеля как боль­шие диа­го­на­ли пра­виль­но­го 100-уголь­ни­ка: на каж­дой диа­го­на­ли по но­ме­ра, причём один номер общий для всех ко­ри­до­ров (на ри­сун­ке изоб­ра­же­на ана­ло­гич­ная кон­струк­ция для 6 ту­ри­стов и Каж­дая пара ту­ри­стов дви­га­ет­ся с про­ти­во­по­лож­ных кон­цов по сво­е­му ко­ри­до­ру. За­ме­тим, что если какой-то ту­рист дошел до цен­траль­но­го но­ме­ра, то он об­на­ру­жил ре­мон­ти­ру­ю­щих­ся но­ме­ров, по­это­му ни­ка­кой дру­гой ту­рист до цен­траль­но­го но­ме­ра не дойдёт.

Ответ: при и при

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. За­ста­вим ста­рую ля­гуш­ку про­пры­гать ходов по её циклу; она ока­жет­ся в точке где Так как раз­ность ко­ор­ди­нат новой и ста­рой ля­гу­шек крат­на

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

Пусть ля­гуш­ки про­пры­га­ли пол­ный цикл и вер­ну­лись (новая в 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 не менее кле­ток, что не мень­ше кле­ток. Это про­ти­во­ре­чит не­ра­вен­ству

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

Де­ле­ние с остат­ком кучи кон­фет на k детей можно пред­став­лять себе так: мы рас­кла­ды­ва­ем кон­фе­ты на k кучек, ко­то­рые либо оди­на­ко­вы (если оста­ток 0), либо в части кучек кон­фет на 1 боль­ше, чем в осталь­ных (ко­ли­че­ство таких куч равно остат­ку).

Пусть пер­вый ребёнок раз­ло­жит так кон­фе­ты на кучки, рас­по­ло­жив кучи слева на­пра­во по воз­рас­та­нию числа кон­фет в них. Можно счи­тать, что он возьмёт себе пра­вую кучку, если он маль­чик, или левую, если он  — де­воч­ка.

Когда зайдёт сле­ду­ю­щий ребёнок, кон­фе­ты уже будут раз­ло­же­ны на кучки, как если бы он сам делил с остат­ком (ведь и число детей, и число куч умень­ши­лось на 1), и снова маль­чик возьмёт пра­вую кучу, а де­воч­ка  — левую, и т. д. В итоге маль­чи­ки возь­мут все пра­вые кучки в ко­ли­че­стве, рав­ном числу маль­чи­ков, что не за­ви­сит от по­ряд­ка детей в оче­ре­ди.

До­ка­жем, что при вы­иг­ра­ет кот Мат­рос­кин. Для этого до­ста­точ­но, чтобы на по­след­нем шаге дяди Фёдора все остав­ши­е­ся 100 бу­тер­бро­дов ока­за­лись без кол­ба­сы.

Про­ну­ме­ру­ем бу­тер­бро­ды по по­ряд­ку. Стра­те­гию кота Мат­рос­ки­на раз­де­лим на не­сколь­ко ста­дий. Сна­ча­ла по­ка­жем, что он может дей­ство­вать так, чтобы к мо­мен­ту, когда оста­нет­ся треть от ис­ход­но­го ко­ли­че­ства бу­тер­бро­дов, все бу­тер­бро­ды, номер ко­то­рых даёт оста­ток 1 при де­ле­нии на 100, были без кол­ба­сы.

От­ме­тим в каж­дой сотне бу­тер­бро­дов тот бу­тер­брод, номер ко­то­ро­го даёт оста­ток 1 при де­ле­нии на 100. Пусть за пер­вые ходов кот Мат­рос­кин стя­нет кол­ба­су с каж­до­го от­ме­чен­но­го бу­тер­бро­да среди цен­траль­ной трети бу­тер­бро­дов. Так как Дядя Фёдор за это время съе­да­ет бу­тер­бро­дов, ни­ка­кие бу­тер­бро­ды среди цен­траль­ной трети съе­де­ны не будут. Сле­ду­ю­щие ходов кот Мат­рос­кин будет за­би­рать кол­ба­су с про­из­воль­но­го от­ме­чен­но­го бу­тер­бро­да, а если от­ме­чен­ных бу­тер­бро­дов с кол­ба­сой не оста­нет­ся  — ни­че­го не де­лать. Так как за один ход дядя Фёдор съе­да­ет не более од­но­го от­ме­чен­но­го бу­тер­бро­да (см. за­ме­ча­ние 1), то ещё через ходов все остав­ши­е­ся от­ме­чен­ные бу­тер­бро­ды будут без кол­ба­сы.

На сле­ду­ю­щей ста­дии своей стра­те­гии кот Мат­рос­кин ана­ло­гич­ным об­ра­зом добьётся того, чтобы все бу­тер­бро­ды, номер ко­то­рых даёт оста­ток 2 при де­ле­нии на 100, ока­за­лись без кол­ба­сы; при этом ко­ли­че­ство бу­тер­бро­дов снова умень­шит­ся в 3 раза. На каж­дой сле­ду­ю­щей ста­дии он будет осво­бож­дать от кол­ба­сы оче­ред­ной оста­ток от де­ле­ния на 100; через сто ста­дий, когда оста­нет­ся ровно 100 бу­тер­бро­дов, они все будут без кол­ба­сы.

За­ме­ча­ние 1. Каж­дым ходом дядя Фёдор будет съе­дать бу­тер­бро­ды с но­ме­ра­ми, да­ю­щи­ми раз­лич­ные остат­ки от де­ле­ния на 100 , даже если съе­да­ет их с двух сто­рон. Это можно по­нять, за­ме­тив, что до его хода ко­ли­че­ства бу­тер­бро­дов для каж­до­го остат­ка оди­на­ко­вы, так как общее их ко­ли­че­ство крат­но 100; и после его хода си­ту­а­ция такая же.

За­ме­ча­ние 2. Можно уточ­нить стра­те­гию кота Мат­рос­ки­на, по­ка­зав, что при он тоже вы­иг­ры­ва­ет; на каж­дой ста­дии ко­ли­че­ство бу­тер­бро­дов при этом будет умень­шать­ся в 2 раза. Для этого ему нужно стя­ги­вать кол­ба­су толь­ко с тех бу­тер­бро­дов (с но­ме­ра­ми, да­ю­щи­ми дан­ный оста­ток от де­ле­ния на 100), до ко­то­рых дядя Фёдор на дан­ной ста­дии га­ран­ти­ро­ван­но не доберётся. Не­труд­но по­нять, что такой бу­тер­брод дей­стви­тель­но все­гда найдётся.

А вот при уже вы­иг­ры­ва­ет дядя Фёдор. Дей­стви­тель­но, пер­вы­ми хо­да­ми он съест любые сотен бу­тер­бро­дов; за это время уси­ли­я­ми со­пер­ни­ка по­явит­ся не более бу­тер­бро­дов без кол­ба­сы. Далее, если перед дядей Фёдором лежит сотен бу­тер­бро­дов, из ко­то­рых не более без кол­ба­сы, то при он может съесть ту по­ло­ви­ну ряда (пра­вую или левую), в ко­то­рой бу­тер­бро­дов без кол­ба­сы боль­ше. Тогда их в ряду оста­нет­ся не более плюс, бла­го­да­ря коту Мат­рос­ки­ну, не более новых  — всего не более Про­дол­жая так и далее, при дядя Фёдор по­лу­чит сто бу­тер­бро­дов, из ко­то­рых не более 99 будут без кол­ба­сы.

Ответ: нет.

Пусть или

Ал­го­ритм. Мыс­лен­но раз­де­лим но­ме­ра на 100 участ­ков по но­ме­ров, а в слу­чае нечётного k остав­ший­ся номер объ­явим за­пас­ным. Пусть i-й ту­рист сна­ча­ла про­ве­ря­ет все но­ме­ра i-го участ­ка, дви­га­ясь слева на­пра­во, потом идёт в за­пас­ной номер (если тот есть), а потом про­ве­ря­ет но­ме­ра -го участ­ка, но спра­ва на­ле­во (если про­ве­ря­ет 1-й уча­сток). Ни­ка­кие два ту­ри­ста не по­па­дут при этом в один номер, так как сум­мар­но на двух их участ­ках (вклю­чая за­пас­ной номер, если он есть), всего но­ме­ра.

Оцен­ка. Для того чтобы каж­дый из 100 ту­ри­стов мог га­ран­ти­ро­ван­но за­се­лить­ся в номер не на ре­мон­те, он дол­жен с са­мо­го на­ча­ла иметь спи­сок из раз­лич­ных но­ме­ров, в ко­то­рые будет за­хо­дить. Можно счи­тать, что спис­ки не ме­ня­ют­ся по ходу за­се­ле­ния дру­гих ту­ри­стов (по­сколь­ку ни­ка­кой ин­фор­ма­ции о них мы не узнаём).

Рас­смот­рим для каж­до­го ту­ри­ста пер­вые но­ме­ров из его спис­ка. Все эти чисел раз­лич­ны, иначе два ту­ри­ста с сов­пав­шим чис­лом могут оба по­пасть в этот номер (если их преды­ду­щие но­ме­ра, ко­то­рых сум­мар­но не боль­ше все на ре­мон­те). Сле­до­ва­тель­но,

При чётном k этой оцен­ки до­ста­точ­но. В слу­чае нечётного k, если у ка­ко­го-то ту­ри­ста, ска­жем, Пети, -й номер сов­па­да­ет с каким-то из «пер­вых» но­ме­ров, ска­жем, с Ва­си­ным, то когда у Пети пер­вые но­ме­ров будут на ре­мон­те, а у Васи  — все но­ме­ра до сов­па­да­ю­ще­го с Пе­ти­ным (их не более m) будут на ре­мон­те, они по­па­дут в один номер. Зна­чит, все -е но­ме­ра от­лич­ны от пер­вых (хотя могут сов­па­дать друг с дру­гом), то есть

За­ме­ча­ние. Для чётного числа ту­ри­стов (а их у нас 100), ал­го­ритм можно опи­сать не­сколь­ко иначе. При чётном k мыс­лен­но пред­ста­вим план отеля как 50 ко­ри­до­ров, в каж­дом из ко­то­рых вдоль одной стены рас­по­ло­же­ны двери но­ме­ров. Каж­дой паре ту­ри­стов «от­да­дим» один ко­ри­дор по ко­то­ро­му они дви­га­ют­ся с про­ти­во­по­лож­ных кон­цов, про­ве­ряя все встре­чен­ные ком­на­ты. В сумме эта пара может об­на­ру­жить не более k ре­мон­ти­ру­ю­щих­ся но­ме­ров, по­это­му два сво­бод­ных но­ме­ра для них оста­нут­ся.

При нечётном k пред­ста­вим ко­ри­до­ры отеля как боль­шие диа­го­на­ли пра­виль­но­го 100-уголь­ни­ка: на каж­дой диа­го­на­ли по но­ме­ра, причём один номер общий для всех ко­ри­до­ров (на ри­сун­ке изоб­ра­же­на ана­ло­гич­ная кон­струк­ция для 6 ту­ри­стов и Каж­дая пара ту­ри­стов дви­га­ет­ся с про­ти­во­по­лож­ных кон­цов по сво­е­му ко­ри­до­ру. За­ме­тим, что если какой-то ту­рист дошел до цен­траль­но­го но­ме­ра, то он об­на­ру­жил ре­мон­ти­ру­ю­щих­ся но­ме­ров, по­это­му ни­ка­кой дру­гой ту­рист до цен­траль­но­го но­ме­ра не дойдёт.

Ответ: при и при

Стра­те­гия: каж­дый раз остав­лять в куче крат­ное 4 число кам­ней: при надо взять один ка­мень, при   — два камня; при надо взять p кам­ней, где p  — про­стой де­ли­тель числа n вида (такой есть, иначе все про­стые де­ли­те­ли n имеют вид а про­из­ве­де­ние чисел та­ко­го вида тоже имеет такой вид и не равно ).

Про­тив­ник из кучи с крат­ным 4 чис­лом кам­ней не может взять число кам­ней, крат­ное 4 (это будет не про­стое число), по­это­му на­чи­на­ю­щий и даль­ше может иг­рать по стра­те­гии.

Ответ: при n, не крат­ном 4.

Если в числе седь­мая цифра спра­ва  — это a, а тре­тья спра­ва  — это b, то, меняя их ме­ста­ми, мы из­ме­ним число на

Зна­чит, при такой за­ме­не де­ли­мость на не ис­пор­тит­ся, по­сколь­ку де­лит­ся на 101, а 100 де­лит­ся на 20. По­это­му боль­ше 6 цифр в числе N быть не может

Шесть цифр может быть. На­при­мер, под­хо­дит число 351480 (0 дол­жен оста­вать­ся в конце, обмен 3 и 8 ис­пор­тит де­ли­мость на 4, а обмен со­сед­них цифр или цифр, сто­я­щих через одну или через две, ис­пор­тит де­ли­мость на 101, по­сколь­ку числа и на 101 не де­лят­ся). Есть и дру­гие при­ме­ры, ска­жем, 531260.

Пяти  — или четырёхзнач­ное число, крат­ное 2020, по­лу­ча­ет­ся умно­же­ни­ем 2020 на число мень­шее 50. У числа вто­рая и четвёртая цифры равны, а у числа они равны нулю, по­это­му у суммы эти цифры равны, что нас не устра­и­ва­ет.

Ответ: при 6 циф­рах.

Решим сразу оба пунк­та. Пусть k  — любое из чисел 49 или 50. Рас­кра­сим мо­не­ты в чёрный и белый цвета (10 г  — одним цве­том, 11 г  — дру­гим). Монет ка­ко­го-то цвета, ска­жем, белых, будет нечётное ко­ли­че­ство, пусть Надо до­ка­зать, что среди k монет спра­ва и k монет слева от какой-то мо­не­ты будет по­ров­ну белых.

Пред­по­ло­жим про­тив­ное. Тогда иначе един­ствен­ная белая мо­не­та  — ис­ко­мая. Назовём белую мо­не­ту пра­вой, если среди k монет спра­ва от неё белых боль­ше, чем среди k монет слева от неё, в про­тив­ном слу­чае  — левой . Так как белых монет пра­вых и левых монет будет не по­ров­ну, пусть пра­вых боль­ше.

Пусть A  — пра­вая мо­не­та, а -я спра­ва от A белая мо­не­та (то есть на дуге, иду­щей впра­во от A к B, белых монет между A и B ровно

Если бы среди k монет спра­ва от A не было B, то среди них было бы не более белой мо­не­ты. Так как то вме­сте среди k монет слева от A и k монет спра­ва от A хотя бы белые мо­не­ты, по­это­му среди k монет слева от A было бы тогда не менее белой, то есть не мень­ше, чем спра­ва, что про­ти­во­ре­чит тому что A  — пра­вая.

Зна­чит среди k монет спра­ва от A есть B, но тогда среди k монет слева от B встре­ча­ют­ся все белые мо­не­ты, ле­жа­щие на дуге, иду­щей впра­во от A к B, и сама мо­не­та A, то есть среди них встре­ча­ет­ся не менее m монет. Так как то вме­сте среди k монет слева от B и k монет спра­ва от B не более белых, по­это­му среди k монет спра­ва от B не более m белых, то есть не боль­ше, чем слева. Зна­чит, мо­не­та B  — левая.

Итак, для вся­кой пра­вой мо­не­ты m-я спра­ва от неё белая мо­не­та  — левая. Зна­чит, левых не мень­ше, чем пра­вых, про­ти­во­ре­чие.

Пусть сред­нее ариф­ме­ти­че­ское удач­ной пары равно на­ту­раль­но­му числу m. Тогда числа из этой пары  — одной чётно­сти, и их можно пред­ста­вить в виде и где n тоже на­ту­раль­ное. Так как сред­нее гео­мет­ри­че­ское чисел пары  — на­ту­раль­ное число, их про­из­ве­де­ние  — пол­ный квад­рат: где k на­ту­раль­ное. Тогда от­ку­да и   — удач­ная пара с тем же сред­ним ариф­ме­ти­че­ским, причём (иначе что не­воз­мож­но в силу ир­ра­ци­о­наль­но­сти

За­ме­ча­ние. Если числа ис­ход­ной пары  — это a, b, то числа новой пары имеют вид

Ответ: да, верно.

а) Пусть Вася дей­ству­ет так: если Петя на­зы­вал чётное число, Вася его и за­пи­сы­ва­ет, а если Петя на­звал нечётное  — за­пи­сы­ва­ет сумму его и всех чисел на доске. Тогда Вася может за­пи­сать на доску нечётное число лишь один раз  — когда Петя впер­вые на­звал нечётное число. Зна­чит, на доске будет на­пи­са­но не более од­но­го нечётного числа, и тем самым не более одной пятёрки.

б) Как Пете до­бить­ся того, чтобы Вася на­пи­сал на доске число 10:

(2) Если сумма чисел на доске равна −5, то Петя на­зы­ва­ет число 10, и Вася либо пишет число 10 , либо пишет число 5 и по­па­да­ет в си­ту­а­цию (1).

(3) Если сумма чисел на доске равна 5 , то Петя на­зы­ва­ет число −10, и Вася либо пишет число −5 и по­па­да­ет в си­ту­а­цию (1), либо пишет число −10 и по­па­да­ет в си­ту­а­цию (2).

(4) Если сумма чисел на доске равна 10, то Петя на­зы­ва­ет число −15, и Вася либо пишет число −15 и по­па­да­ет в си­ту­а­цию (2), либо пишет число −5 и по­па­да­ет в си­ту­а­цию (3).

За­ме­тим, что если на доске дру­гая сумма чисел, ска­жем n, то Петя может на­звать число и Вася либо на­пи­шет число 10, либо попадёт в си­ту­а­цию (4). Таким об­ра­зом, имея любой набор чисел на доске, мы можем в итоге за­ста­вить Васю на­пи­сать 10. Зна­чит, мы смо­жем сде­лать так, чтобы на доске было 100 де­ся­ток.

Ответ: а) не все­гда; б) все­гда.

I спо­соб. За­ме­тим, что (про­верь­те!). До­мно­жив это ра­вен­ство на по­лу­чим: За­ме­няя на сумму из преды­ду­ще­го ра­вен­ства, по­лу­ча­ем пять кубов, да­ю­щих в сумме куб: До­мно­жив новое ра­вен­ство на и снова за­ме­няя на сумму трёх кубов, по­лу­ча­ем 7 кубов, да­ю­щих в сумме куб:

Дей­ствуя далее ана­ло­гич­но, мы смо­жем по­лу­чить и 99 кубов, да­ю­щих в сумме куб, что и тре­бу­ет­ся в за­да­че.

Ответ: су­ще­ству­ют.

II спо­соб. Вос­поль­зу­ем­ся фор­му­лой За­ме­тим, что

Пусть корни мно­го­чле­на из усло­вия  — числа Вы­бе­рем n раз­лич­ных на­прав­ле­ний на плос­ко­сти и возьмём пря­мых пер­во­го на­прав­ле­ния,   — вто­ро­го, ..., -го на­прав­ле­ния.

Тогда, по фор­му­лам Виета, число пря­мых будет рав­нять­ся a, а число их точек пе­ре­се­че­ния между собой будет рав­нять­ся b, если толь­ко ни­ка­кие три пря­мые не пе­ре­се­кут­ся в одной точке. Этого можно до­бить­ся, про­во­дя пря­мые по­сле­до­ва­тель­но: оче­ред­ную пря­мую нуж­но­го на­прав­ле­ния вы­би­ра­ем так, чтобы она не за­де­ва­ла уже име­ю­щи­е­ся точки пе­ре­се­че­ния (их на каж­дом шаге ко­неч­ное число).

Ответ: не оши­ба­ет­ся.

Обо­зна­чим через гно­мов, си­дя­щих за пер­вым сто­ли­ком, а через   — гно­мов, си­дя­щих за вто­рым сто­ли­ком.

Слу­чай нечётного n. Пусть Стра­те­гия доб­ро­го вол­шеб­ни­ка: по­дру­жить пары гно­мов и (здесь мы счи­та­ем, что Оче­вид­но, что доб­рый вол­шеб­ник по­дру­жил ровно пар гно­мов. Про­ве­рим, что при такой стра­те­гии злой вол­шеб­ник не смо­жет по­ме­шать доб­ро­му.

Дей­стви­тель­но, так как злой вол­шеб­ник ссо­рит ровно по­ло­ви­ну ука­зан­ных пар, то либо среди пар хотя бы k всё ещё дру­жат, либо среди пар хотя бы k все еще дру­жат. Тогда в пер­вом слу­чае най­дет­ся i, для ко­то­ро­го обе пары гно­мов дру­жат, и доб­рый вол­шеб­ник может рас­са­дить их за стол сле­ду­ю­щим об­ра­зом:

Вто­рой слу­чай ана­ло­ги­чен.

Слу­чай чётного n. При­ве­дем стра­те­гию злого вол­шеб­ни­ка. Пусть доб­рый вол­шеб­ник уже как-то по­дру­жил пар гно­мов; по­стро­им граф, в ко­то­ром вер­ши­ны со­от­вет­ству­ют гно­мам, а ребра  — парам гно­мов, ко­то­рые по­дру­жил доб­рый вол­шеб­ник. По­кра­сим гно­мов за пер­вым сто­ли­ком в белый и чёрный цвета в шах­мат­ном по­ряд­ке, а за вто­рым  — в крас­ный и синий. Так как сумма сте­пе­ней всех вер­шин равна 4n, найдётся цвет, для ко­то­ро­го сумма сте­пе­ней вер­шин, по­кра­шен­ных в этот цвет, не пре­вос­хо­дит n. Не ума­ляя общ­но­сти, это белый цвет, то есть гномы Пусть злой вол­шеб­ник по­ссо­рит все пары дру­зей, в ко­то­рые вхо­дят гномы бе­ло­го цвета. Тогда един­ствен­ные остав­ши­е­ся дру­зья лю­бо­го бе­ло­го гнома   — его ста­рые со­се­ди и и оче­вид­но, что доб­рый вол­шеб­ник не смо­жет рас­са­дить всех гно­мов за один стол тре­бу­е­мым об­ра­зом.

Ответ: при всех нечётных

Сори­ен­ти­ру­ем доску так, чтобы у неё было 1000 столб­цов и n строк, а жук сидел в ниж­нем левом углу. По­кра­сим клет­ки в шах­мат­ном по­ряд­ке, причём клет­ку жука сде­ла­ем белой. За­ну­ме­ру­ем столб­цы чис­ла­ми от 1 до 1000 слева на­пра­во, а стро­ки чис­ла­ми от 1 до n снизу вверх.

Рас­смот­рим не­ко­то­рый путь жука из клет­ки в клет­ку Из каж­дой клет­ки пути на­ри­су­ем стрел­ку в сле­ду­ю­щую клет­ку. Тогда из каж­дой белой клет­ки пути стрел­ка ведёт в чёрную.

Пусть i  — чётное число, причём Между стро­ка­ми i и про­ведём го­ри­зон­таль­ную пря­мую ℓ.

Ниже пря­мой ℓ ко­ли­че­ство белых кле­ток в пути пре­вос­хо­дит ко­ли­че­ство чёрных не мень­ше чем на 1000, так как 1000 чёрных кле­ток в ниж­них стро­ках на­хо­дят­ся под боем слона. По­это­му не мень­ше 1000 стре­лок идут из белых кле­ток ниже ℓ в чёрные клет­ки выше ℓ. Но так может про­хо­дить лишь стрел­ка из клет­ки в стро­ке или i. А по­сколь­ку там всего 1000 белых кле­ток, в каж­дой из них на­чи­на­ет­ся стрел­ка, иду­щая в чёрную клет­ку стро­ки или

Стрел­ка из клет­ки может идти толь­ко в Тогда стрел­ка из может идти толь­ко в По­сле­до­ва­тель­но рас­смат­ри­вая клет­ки

видим, что все 1000 стре­лок в дей­стви­тель­но­сти опре­де­ле­ны од­но­знач­но (рис. 1).

Рис 1.

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

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

По­сколь­ку стрел­ка из не может вести в белую клет­ку ниже ℓ, стрел­ки из всех осталь­ных чёрных кле­ток в стро­ках и долж­ны вести в белые клет­ки ниже ℓ. По­сле­до­ва­тель­но рас­смат­ри­вая клет­ки

видим, что все 999 стре­лок в дей­стви­тель­но­сти опре­де­ле­ны од­но­знач­но (рис. 2).

Рис 2.

Ана­ло­гич­ное рас­суж­де­ние для всех чётных зна­че­ний i между 1000 и по­ка­зы­ва­ет, что сред­няя часть пути жука опре­де­ле­на од­но­знач­но и при росте n про­дол­жа­ет­ся в виде пру­жи­ны (рис. 3).

Рис 3.

Сле­до­ва­тель­но, ко­ли­че­ство воз­мож­ных путей не за­ви­сит от n.

За­ме­ча­ние. Кон­струк­ция на ри­сун­ке 4 по­ка­зы­ва­ет, что рас­смат­ри­ва­е­мые пути дей­стви­тель­но су­ще­ству­ют.

Рис 4.

На ри­сун­ках при­ве­де­ны при­ме­ры Квадр­лан­дий. Пу­стые клет­ки  — ко­ро­лев­ства, а цифра в клет­ке обо­зна­ча­ет, сколь­ко ко­ро­левств пре­тен­ду­ет на эту спор­ную тер­ри­то­рию).

Ответ: см. рис.