Пред­по­ло­жим, что уда­лось так раз­ме­стить от­ре­зок XY. По какую-то сто­ро­ну от пря­мой XY ока­жут­ся три вер­ши­ны пя­ти­уголь­ни­ка  — пусть A, B и C. Тогда точки A, B, C, X и Y лежат на одной окруж­но­сти. Она сов­падёт с окруж­но­стью, опи­сан­ной около пра­виль­но­го пя­ти­уголь­ни­ка, по­сколь­ку имеет с ней три раз­лич­ные общие точки. Сле­до­ва­тель­но, точки X и Y лежат не внут­ри пя­ти­уголь­ни­ка. Про­ти­во­ре­чие.

Ответ: нель­зя.

За­ме­тим, что 1 + 2  — не квад­рат. Пусть

Разобьём эти числа на четвёрки под­ряд иду­щих, и, если надо, шестёрку пер­вых чисел. Из четвёрок об­ра­зу­ем

из шестёрки  —

Ответ: все

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

Если n чётно, то

яв­ля­ет­ся квад­ра­том. Если n нечётно, то

так же яв­ля­ет­ся квад­ра­том.

За­ме­ча­ние.

Для n  =  2, 3 раз­би­е­ние един­ствен­но, в осталь­ных слу­ча­ях  — нет.

a)  До­ста­точ­но за­ме­тить, что

б)  Вы­чтем из числа, ко­то­рое нужно пред­ста­вить, такой куб (0, 1 или −1), чтобы ре­зуль­тат имел вид 3k − 2, и при­ме­ним пункт а).

Пусть k  — ко­ли­че­ство жи­те­лей в го­ро­де. Будем изоб­ра­жать си­ту­а­цию в игре таб­ли­цей с n стро­ка­ми и k столб­ца­ми: в i-й стро­ке будут пе­ре­чис­ле­ны бла­го­со­сто­я­ния всех жи­те­лей i-го го­ро­да в по­ряд­ке не­убы­ва­ния. Пусть S_i  — сумма чисел в j-м столб­це.

а)  Стра­те­гия Рок­фел­ле­ра. Если вы­брать всех жи­те­лей из j-го столб­ца.

Пред­по­ло­жим, что тогда при всех i. После марк­со­ва пе­ре­рас­пре­де­ле­ния числа не умень­шат­ся. С дру­гой сто­ро­ны, у од­но­го из вы­бран­ных жи­те­лей (пусть он в i-м го­ро­де) бла­го­со­сто­я­ние ста­нет боль­ше чем Это зна­чит, что одна из сумм S_k при уве­ли­чит­ся (та, в ко­то­рую по­па­ло новое число). По­это­му по­сле­до­ва­тель­ность лек­си­ко­гра­фи­че­ски уве­ли­чит­ся. Это не может про­дол­жать­ся бес­ко­неч­но долго (ибо на­бо­ров из k чисел с фик­си­ро­ван­ной сум­мой ко­неч­ное ко­ли­че­ство), так что в не­ко­то­рый мо­мент все числа ока­жут­ся раз­лич­ны­ми.

Пусть Тогда при всех i, от­ку­да

то есть Про­ти­во­ре­чие. Зна­чит, S₁  =  0, и Рок­фел­лер по­бе­дил..

б)  Пусть k  =  2n−1. При­ме­няя стра­те­гию из пунк­та а), Рок­фел­лер либо вы­иг­ра­ет, либо добьётся со­сто­я­ния при всех По­ка­жем, как ему вы­иг­рать, на­чи­ная с такой по­зи­ции.

Ска­жем, что игра на­хо­дит­ся в i-й си­ту­а­ции если (воз­мож­но, после пе­ре­ну­ме­ра­ции строк) вы­пол­не­ны сле­ду­ю­щие усло­вия:

1)  при в j-м столб­це стоят j еди­ниц в верх­них клет­ках, а осталь­ные числа  — нули;

2)  в i-м столб­це ниж­ние эле­мен­тов  — нули.

По­ка­жем, что в рас­смат­ри­ва­е­мый мо­мент игра на­хо­дит­ся в i-й си­ту­а­ции при не­ко­то­ром i. Пе­ре­ста­вим стро­ки так, чтобы ко­ли­че­ства нулей в них не убы­ва­ли свер­ху вниз. Пусть при не­ко­то­ром в i-м столб­це не стоит i еди­ниц; вы­бе­рем наи­мень­шее такое i. Тогда (из усло­вия на нули в стро­ках) в преды­ду­щих столб­цах еди­ни­цы стоят «тре­уголь­ни­ком», а в i-м столб­це есть нулей, то есть игра в i-й си­ту­а­ции. Если же та­ко­го i нет, то в пер­вых n столб­цах еди­ни­цы стоят «тре­уголь­ни­ком», и игра в -й си­ту­а­ции.

По­ка­жем, что при i > 1, если игра в i-й си­ту­а­ции, Рок­фел­лер может умень­шить номер си­ту­а­ции одним ходом. Так он рано или позд­но добьётся 1-й си­ту­а­ции, то есть сво­е­го вы­иг­ры­ша.

Дей­стви­тель­но, Рок­фел­лер вы­би­ра­ет (i−1)-й стол­бец. Пусть j  — наи­мень­ший ин­декс, при ко­то­ром число в j-й стро­ке умень­шит­ся (т. е. пре­вра­тит­ся в 0) в ре­зуль­та­те дей­ствия Марк­са. По­сколь­ку то после этого хода (и упо­ря­до­чи­ва­ния строк, при ко­то­ром этот 0 пе­ре­ме­стит­ся в на­ча­ло стро­ки) будет на­блю­дать­ся j-я си­ту­а­ция (здесь мы уже не тре­бу­ем ра­венств S_k  =  k), что и тре­бо­ва­лось.

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

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

Оцен­ка. I спо­соб. Пусть   — числа на глав­ной диа­го­на­ли (по­ря­док, в ко­то­ром они там стоят, нам не­из­ве­стен). Для каж­до­го по­кра­сим само и все числа, сто­я­щие либо под в том же столб­це, либо слева от в той же стро­ке, в цвет номер k. Тогда чисел каж­до­го цвета будет ровно n, и каж­дое число ле­сен­ки, кроме чисел глав­ной диа­го­на­ли, будет по­кра­ше­но ровно в два цвета  — «цвет стро­ки» и «цвет столб­ца» (а каж­дое число на глав­ной диа­го­на­ли  — толь­ко в один свой цвет).

За­ме­тим, что боль­ше всех осталь­ных чисел цвета k и боль­ше всех чисел, цвет ко­то­рых имеет номер мень­ше k (так как Тем самым не мень­ше, чем ко­ли­че­ство чисел с цве­та­ми от 1 до k. Но таких чисел ровно

по­сколь­ку чисел цвета ровно n, чисел цвета 2, но не цвета ровно чисел цвета k, но ни од­но­го из цве­тов   — ровно От­сю­да

II спо­соб. Пусть   — числа на глав­ной диа­го­на­ли. Рас­смот­рим не­ко­то­рое Если число из ле­сен­ки на­хо­дит­ся в одной стро­ке или в одном столб­це с одним из диа­го­наль­ных чисел то оно не пре­вос­хо­дит его, и, зна­чит, не пре­вос­хо­дит числа могут на­хо­дить­ся толь­ко в стро­ках и столб­цах с чис­ла­ми   — таких чисел всего Все осталь­ные чисел ле­сен­ки не боль­ше то есть Скла­ды­вая, по­лу­ча­ем точ­ную оцен­ку на

III спо­соб. Про­ну­ме­ру­ем все диа­го­на­ли, па­рал­лель­ные глав­ной и ле­жа­щие не выше её, чис­ла­ми от 1 до n снизу вверх. Пусть   — числа на глав­ной диа­го­на­ли. Про­ведём из чисел еди­нич­ные стрел­ки влево или вниз в по­пар­но раз­лич­ные клет­ки -й диа­го­на­ли (это, оче­вид­но, воз­мож­но). Из же про­ведём одну из двух стре­лок на -ю диа­го­наль.

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

Те­перь не­труд­но до­ка­зать оцен­ку. Из кле­ток ведут k путей, причём их на­ча­ла длины со­от­вет­ствен­но не имеют общих кле­ток. Число не мень­ше всех чисел, встре­ча­ю­щих­ся на этих путях; по­это­му

Сум­ми­руя, по­лу­ча­ем

За­ме­ча­ние. Это же ре­ше­ние можно офор­мить по-дру­го­му. Рас­смот­рим толь­ко рас­ста­нов­ку раз­лич­ных на­ту­раль­ных чисел в диа­го­на­лях До­ка­жем, что если в каж­дой диа­го­на­ли по­ста­вить числа свер­ху вниз по воз­рас­та­нию, то рас­ста­нов­ка чисел в этом тре­уголь­ни­ке по-преж­не­му будет удо­вле­тво­рять усло­ви­ям. Для этого, если и   — числа в k-й и -й диа­го­на­лях, надо до­ка­зать, что при всех Это до­ка­зы­ва­ет­ся, на­при­мер, тем же про­ве­де­ни­ем стре­лок; есть и дру­гие спо­со­бы. После этого в новой рас­ста­нов­ке число не мень­ше, чем все числа в пер­вых k столб­цах тре­уголь­ни­ка, то есть

от­ку­да и сле­ду­ет оцен­ка.

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

К концу вось­мо­го дня каж­дый шах­ма­тист сыг­рал 8 пар­тий, зна­чит, не сыг­рал одну. Не­сыг­ран­ные пар­тии раз­би­ва­ют шах­ма­ти­стов на 5 не­пе­ре­се­ка­ю­щих­ся пар. По прин­ци­пу Ди­ри­х­ле, среди любых шести шах­ма­ти­стов все­гда най­дут­ся двое, при­над­ле­жа­щих одной паре, то есть, не сыг­рав­шие друг с дру­гом даже к концу пред­по­след­не­го дня тур­ни­ра. Сле­до­ва­тель­но,

По­ка­жем, что в конце седь­мо­го дня тур­ни­ра, не­за­ви­си­мо от рас­пи­са­ния, обя­за­тель­но най­дут­ся пять шах­ма­ти­стов, уже сыг­рав­ших между собой все по­ло­жен­ные пар­тии, от­ку­да будет сле­до­вать, что n  =  5. По­стро­им сле­ду­ю­щую це­поч­ку шах­ма­ти­стов: пер­вый  — любой, вто­рой  — тот, с кем сыг­рал пер­вый в вось­мой день, тре­тий  — тот, с кем сыг­рал вто­рой в де­вя­тый день, четвёртый  — тот, с кем сыг­рал тре­тий в вось­мой день и т. д. Шах­ма­ти­стов ко­неч­ное число, по­это­му в це­поч­ке какой-то мо­мент впер­вые про­изойдёт по­втор. Он не может слу­чить­ся ни на каком из шах­ма­ти­стов, кроме пер­во­го, иначе по­вто­рив­ший­ся шах­ма­тист дол­жен был бы сыг­рать не мень­ше трёх пар­тий за два дня. Сле­до­ва­тель­но, це­поч­ка замкнётся в цикл чётной длины, так как при дви­же­нии вдоль неё дни рас­смат­ри­ва­е­мых пар­тий че­ре­ду­ют­ся. Если по­стро­ен­ный цикл со­дер­жит всех 10 шах­ма­ти­стов, оста­нав­ли­ва­ем­ся, если нет  — вы­би­ра­ем лю­бо­го шах­ма­ти­ста, не во­шед­ше­го в него и по­вто­ря­ем про­це­ду­ру по­стро­е­ния цикла. Новый цикл не пе­ре­сечётся с уже по­стро­ен­ным. После не­сколь­ких шагов мы по­стро­им не­сколь­ко цик­лов чётной, не мень­шей 4, длины, вклю­ча­ю­щих всех 10 шах­ма­ти­стов (ва­ри­ан­тов не­мно­го  — либо 10, либо 6 + 4). Вы­бе­рем из каж­до­го цикла по­ло­ви­ну его участ­ни­ков, через од­но­го, всего 5 шах­ма­ти­стов. Ни­ка­кие двое из них не рас­по­ло­же­ны в цик­лах радом, по­это­му не иг­ра­ли между собой в вось­мой и де­вя­тый дни. Сле­до­ва­тель­но, все пар­тии между собой они сыг­ра­ли в пер­вые 7 дней. Зна­чит, от­ку­да в итоге n  =  5. При этом k  =  7.

Ответ: n  =  5.

Всего за тур­нир было сыг­ра­но игр. В каж­дой игре разыг­ры­ва­лось либо 5 очков (в слу­чае по­бе­ды-по­ра­же­ния), либо 4 очка (в слу­чае ни­чьей). Если бы все игры были сыг­ра­ны вни­чью, то сум­мар­ное ко­ли­че­ство очков у всех участ­ни­ков рав­ня­лось бы 120 · 4  =  480, что на 70 мень­ше, чем ре­аль­ная сумма очков всех участ­ни­ков. В слу­чае не ни­чей­ной игры два её участ­ни­ка сум­мар­но по­лу­ча­ют на 1 очко боль­ше, чем в слу­чае ни­чей­ной игры. Это озна­ча­ет, что ровно 70 игр за­вер­ши­лись по­бе­дой од­но­го из участ­ни­ков, а осталь­ные 50 игр за­кон­чи­лись вни­чью.

Пред­по­ло­жим, что хотя бы 6 участ­ни­ков ни разу не сыг­ра­ли вни­чью. Тогда ни­чей­ные пар­тии могли прой­ти толь­ко между остав­ши­ми­ся 10 участ­ни­ка­ми, а всего они между собой сыг­ра­ли игр, что мень­ше 50. Про­ти­во­ре­чие. Сле­до­ва­тель­но, не более 5 участ­ни­ков ни разу не сыг­ра­ли вни­чью.

Не­труд­но опи­сать при­мер для 5 участ­ни­ков. За­фик­си­ру­ем 11 участ­ни­ков, они сыг­ра­ли между собой игр. Вы­бе­рем любые 50 из этих игр, пусть они были сыг­ра­ны вни­чью (ясно тогда, что каж­дый из за­фик­си­ро­ван­ных 11 участ­ни­ков хотя бы раз сыг­ра­ет вни­чью), а все осталь­ные игры тур­ни­ра за­кон­чи­лись по­бе­дой лю­бо­го из участ­ни­ков. Сле­до­ва­тель­но, 16 - 11  =  5 че­ло­век ни разу не сыг­ра­ли вни­чью. Ясно, что все усло­вия за­да­чи вы­пол­ня­ют­ся.

Ответ: 5.

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

От­ме­тим также, что всего в тур­ни­ре сыг­ра­но пар­тий и, со­от­вет­ствен­но, разыг­ра­но 190 очков; по­это­му

где S  — сумма очков, на­бран­ных 20 – n участ­ни­ка­ми, не во­шед­ши­ми в це­поч­ку A₁, A₂, ..., A_n.

При это ра­вен­ство при­об­ре­та­ет вид от­ку­да Но число на­бран­ных шах­ма­ти­стом очков не может быть таким.

При по­лу­ча­ет­ся ра­вен­ство от­ку­да По­ка­жем, что ре­зуль­та­ты тур­нир­ных пар­тий могли быть та­ки­ми, что не­ко­то­рые 19 иг­ро­ков A₁, A₂, ..., A₁₉ об­ра­зо­ва­ли це­поч­ку с тре­бу­е­мым свой­ством. Пусть (то есть остав­ший­ся, 20-й, шах­ма­тист про­иг­рал все свои пар­тии), а при участ­ник A_i вы­иг­рал у A_j в том и толь­ко в том слу­чае, если вы­пол­не­но не­ра­вен­ство Легко убе­дить­ся, что тогда для

Ответ: 19.

При­ве­дем при­ме­ры: −1, 2 и −3, −1, 1, 3. Дадим оцен­ку: если чисел боль­ше 4 , то среди них есть три од­но­го знака (пусть по­ло­жи­тель­ных). Вы­бе­рем три наи­мень­ших их них: a, где Об­рат­ные числа будут идти в об­рат­ном по­ряд­ке: но

Ответ: 3 или 4.

За­ме­ча­ние.

Оба при­ме­ра  — един­ствен­ные с точ­но­стью до по­сто­ян­но­го мно­жи­те­ля.

На пер­вом ходу Вася не про­иг­ра­ет, так как нет точ­ных дву­знач­ных квад­ра­тов с циф­рой 7. По­ка­жем, что далее каж­дый может при­пи­сать в конец те­ку­ще­го числа 2 или 3 так, чтобы со­пер­ник не вы­иг­рал сле­ду­ю­щим ходом.

Пусть у нас было число A, и со­пер­ник может сде­лать квад­рат, при­пи­сав цифру как к числу так и к числу По­сколь­ку точ­ные квад­ра­ты не окан­чи­ва­ют­ся ни на 2, ни на 3, он при­пи­шет цифру в конец: ска­жем, x  — в пер­вом слу­чае и y  — во вто­ром. Тогда оба числа и   — точ­ные квад­ра­ты, раз­ность между ко­то­ры­ми мень­ше 20. Но каж­дое из этих чисел хотя бы трёхзнач­ное, и тогда раз­ность между со­сед­ни­ми точ­ны­ми квад­ра­та­ми не мень­ше Про­ти­во­ре­чие.

Ответ: нет.

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

Пусть среди плю­шек с нечётными но­ме­ра­ми не мень­ше де­ся­ти с са­ха­ром (если с ко­ри­цей, то рас­суж­де­ния ана­ло­гич­ны). Тогда Малыш на­чи­на­ет с того, что берёт плюш­ки с нечётными но­ме­ра­ми и после каж­до­го хода Карлсо­на вы­чис­ля­ет такую ве­ли­чи­ну: ко­ли­че­ство по­лу­чен­ных плю­шек с са­ха­ром + ко­ли­че­ство остав­ших­ся на столе плю­шек с са­ха­ром с чётными но­ме­ра­ми. В на­чаль­ный мо­мент эта ве­ли­чи­на не боль­ше 10, а если Малыш будет брать плюш­ки толь­ко с нечётными но­ме­ра­ми, то в конце она будет не мень­ше 10. При этом после каж­дой пары ходов Ма­лы­ша и Карлсо­на эта ве­ли­чи­на из­ме­ня­ет­ся не более чем на 1. Сле­до­ва­тель­но, в какой-то мо­мент (воз­мож­но, на­чаль­ный) она будет равна 10. После этого Малыш может брать толь­ко плюш­ки с чётными но­ме­ра­ми и в итоге по­лу­чит ровно 10 плю­шек с са­ха­ром, а зна­чит, и 10 плю­шек с ко­ри­цей, что и тре­бу­ет­ся.

Ответ: при любом.

За­ме­ча­ние.

Верно более общее утвер­жде­ние: если в ряд лежит чётное число плю­шек, и из них на нечётных ме­стах ровно L с са­ха­ром, а на чётных - ровно R с са­ха­ром, то для вся­ко­го k между (не­стро­го) чис­ла­ми R и L Малыш может дей­ство­вать так, чтобы взять ровно k плю­шек с са­ха­ром.

Для ре­ше­ния ис­ход­ной за­да­чи до­ста­точ­но до­ка­зать это утвер­жде­ние, ибо в нашем слу­чае и одно из чисел не мень­ше 10, а дру­гое не боль­ше 10.

До­ка­зы­ва­ем ин­дук­ци­ей по ко­ли­че­ству плю­шек. Если их две, то утвер­жде­ние оче­вид­но. Шаг ин­дук­ции: по­кра­сим плюш­ки в шах­мат­ном по­ряд­ке, чтобы нечётные стали бе­лы­ми; если то Ма­лы­шу до­ста­точ­но каж­дым ходом есть белую плюш­ку, если   — то чёрную. Если же k за­клю­че­но стро­го между L и R, то Малыш может сде­лать пер­вый ход про­из­воль­ным об­ра­зом, а далее до­бить­ся сво­е­го по пред­по­ло­же­нию ин­дук­ции. В самом деле, не ума­ляя общ­но­сти, тогда белых плю­шек с са­ха­ром оста­нет­ся либо L, либо чёрных - либо R, либо а Ма­лы­шу далее надо взять либо k, либо плюш­ку с са­ха­ром, причём

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

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

Пе­ре­мно­жив, по­лу­чим от­ку­да Рас­крыв скоб­ки и пе­ре­не­ся всё в левую часть, по­лу­чим Тогда про­ти­во­ре­чие.

Вто­рой спо­соб. Раз­берём воз­мож­ные слу­чаи:

1)   Если то если то

2)   Можно счи­тать, что (иначе за­ме­ним все числа на об­рат­ные). Пусть и Тогда

Зна­чит, Сле­до­ва­тель­но,

Улуч­шить ре­зуль­тат нель­зя: для чисел все шесть раз­но­стей не мень­ше

Ответ: при

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

Также за­ме­тим, что после каж­до­го тура ко­ли­че­ство ко­манд умень­ша­ет­ся мак­си­мум вдвое, по­то­му что не боль­ше по­ло­ви­ны ко­манд тер­пит по­ра­же­ние. В част­но­сти, в по­след­нем туре могли участ­во­вать толь­ко 2 ко­ман­ды, и они сыг­ра­ли один матч. В пред­по­след­нем туре участ­во­ва­ли мак­си­мум 4 ко­ман­ды и сыг­ра­ли мак­си­мум 2 матча. За тур до этого было сыг­ра­но мак­си­мум 4 матча, а ещё за тур до этого мак­си­мум 8. Итого в по­след­них 4 турах было сыг­ра­но не боль­ше 15 мат­чей.

Зна­чит до этого было сыг­ра­но ещё хотя бы 78 мат­чей. В каж­дом из осталь­ных туров было сыг­ра­но не боль­ше 16 мат­чей, зна­чит, всего этих туров хотя бы 5. Итого по­лу­ча­ем не мень­ше 4 + 5  =  9 туров.

За 9 туров ко­ман­ды могли упра­вить­ся. Дей­стви­тель­но, в пер­вых 4 турах ко­ман­ды могли раз­бить­ся на пары, после чего в каж­дой паре на­не­сти друг другу по 2 по­ра­же­ния. После этого каж­дой ко­ман­де оста­лось про­иг­рать один раз и мы по­лу­ча­ем обыч­ную олим­пий­скую си­сте­му из 5 туров, в каж­дом из ко­то­рых по­ло­ви­на ко­манд вы­бы­ва­ет.

Ответ: 9.

Пусть это уда­лось. Числа в со­сед­них углах раз­ли­ча­ют­ся на 1, так как каж­дое из них до­пол­ня­ет че­ты­ре клет­ки между ними до пря­мо­уголь­ни­ка Пусть a  — наи­мень­шее число из уг­ло­вых. Тогда в со­сед­них с ним углах стоят числа a + 1. Про­ти­во­ре­чие.

Ответ: нель­зя.

Если n крат­но k, то 1_n де­лит­ся на па­лин­дром 1_k причём част­ное  — тоже па­лин­дром, со­сто­я­щий из еди­ниц, раз­делённых груп­па­ми из k − 1 нуля. Оста­лось вы­брать число, име­ю­щее более 100 соб­ствен­ных де­ли­те­лей. На­при­мер, 2¹⁰¹.

Ответ: су­ще­ству­ет, рас­смот­рим па­лин­дром

За­ме­ча­ние.

Число 6_n де­лит­ся не толь­ко на 1_k, но и на 2k, 3k и 6. Это поз­во­ля­ет умень­шить n до числа, име­ю­ще­го более 25 соб­ствен­ных де­ли­те­лей, на­при­мер, го­дит­ся

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

За­ме­тим, что если при умно­же­нии па­лин­дро­мов не про­ис­хо­дит пе­ре­но­сов из од­но­го раз­ря­да в дру­гой, то про­из­ве­де­ние - тоже па­лин­дром. Рас­смот­рим про­из­ве­де­ние

Можно до­ка­зать, что при умно­же­нии лю­бо­го числа этих со­мно­жи­те­лей пе­ре­но­сов не про­ис­хо­дит и по­лу­ча­ет­ся па­лин­дром из нулей и еди­ниц. По­сколь­ку 8 мно­жи­те­лей можно спо­со­ба­ми раз­бить на две груп­пы, можно по­лу­чить 128 раз­лич­ных (по­сколь­ку мно­жи­те­ли вза­им­но про­сты) пред­став­ле­ний числа 1₂₅₆ в виде про­из­ве­де­ния двух па­лин­дро­мов.

За­ме­ча­ние.

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

Пусть уда­лось рас­кра­сить числа в синий, крас­ный и зелёный цвета. Можно счи­тать, что число 2 синее, а 4 не крас­ное. Возьмём крас­ное число k. Тогда число 2k зелёное, а 2 · (2k) крас­ное. С дру­гой сто­ро­ны, 4 · k не крас­ное. Про­ти­во­ре­чие.

Ответ: нель­зя.

Обо­зна­чим мо­не­ты A, B, C, D, E, F, G, H. Петя отдаёт H и про­сит Васю срав­нить A + B с C + D.

1.  Вася от­ве­ча­ет, что весы в рав­но­ве­сии. Тогда мо­не­ты на­сто­я­щие (не­за­ви­си­мо от того, какая мо­не­та до­ста­лась Васе). Петя отдаёт G за срав­не­ние A с E. Если Вася от­ве­тит, что их веса не равны, то мо­не­та F на­сто­я­щая. В про­тив­ном слу­чае мо­не­та E на­сто­я­щая.

2.  Вася от­ве­ча­ет, что A + B тя­же­лее. Тогда мо­не­ты E, F, G на­сто­я­щие. Петя отдаёт D за срав­не­ние A с B. Если Вася от­ве­ча­ет, что их веса не равны, то более лёгкая из этих двух и мо­не­та C на­сто­я­щие. В про­тив­ном слу­чае мо­не­ты A и B на­сто­я­щие.

Слу­чай, когда C + D тя­же­лее рас­смат­ри­ва­ет­ся ана­ло­гич­но.

Ответ: может.

Можно счи­тать, что от­ме­чен­ные точки - целые числа от 1 до 2022. До­ста­точ­но по­ка­зать, что сумма S длин всех от­рез­ков с раз­но­цвет­ны­ми кон­ца­ми нечётна.

Пусть крас­но-чётных точек x, тогда крас­но-нечётных и сине-чётных  — по y  =  1011–x, зна­чит, сине-нечётных  — x. «Раз­но­цвет­ные» от­рез­ки чётной длины не вли­я­ют на чётность S, а ко­ли­че­ство таких от­рез­ков нечётной длины равно Оста­лось за­ме­тить, что числа x и y раз­ной чётно­сти.

Ответ: не может.

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

Пусть k  — ко­ор­ди­на­та крас­но­го конца от­рез­ка, а c  — си­не­го. За­ме­ним длину |k–c| этого от­рез­ка на k + c  — чётность S не из­ме­нит­ся. Но те­перь в сумме по всем «раз­но­цвет­ным» от­рез­кам каж­дое число встре­тит­ся ровно 1011 раз, то есть сумма равна 1011(1 + Она нечётна, так как в скоб­ках 1011 нечётных сла­га­е­мых.

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

При­ведём толь­ко идею. Можно про­ве­рить, что S чётна, для какой-то кон­крет­ной рас­крас­ки (на­при­мер, когда слева на­пра­во идут сна­ча­ла все синие точки, а потом все крас­ные), после чего про­ве­рить, что чётность у S со­хра­ня­ет­ся, если ме­нять ме­ста­ми цвета со­сед­них точек.

а)  Оцен­ка. Ко­ли­че­ство про­доль­ных ходов не пре­вос­хо­дит ко­ли­че­ства 2N² до­ми­но­шек (так как в каж­дой до­ми­нош­ке не более од­но­го про­доль­но­го хода).

При­мер. Возьмём любой обход ла­дьей и за­ну­ме­ру­ем клет­ки в по­ряд­ке об­хо­да. Пусть клет­ки 2k − 1 и 2k об­ра­зу­ют до­ми­нош­ку для всех k от 1 до 2N². Тогда число про­доль­ных ходов равно числу до­ми­но­шек.

б)  Слу­чай N  =  1 оче­ви­ден.

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

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

Ответ: а)  2N² ходов; б)  1 ход при N  =  1; 2 хода при