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

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

Пусть тогда вы­со­та ниж­не­го жёлтого пря­мо­уголь­ни­ка равна a < 1, а ши­ри­на пра­во­го  — b < 1. От­ло­жим свер­ху и слева со­от­вет­ствен­но длины a и b и раз­де­лим квад­рат на 9 пря­мо­уголь­ни­ков как на ри­сун­ке. Через S_i будем обо­зна­чать пло­щадь i-го пря­мо­уголь­ни­ка. Тогда S₁  =  S₇, S₄  =  S₆, S₂  =  S₈ и S₃  =  S₉. Но тогда пло­щадь всех синих пря­мо­уголь­ни­ков боль­ше пло­ща­ди всех жёлтых на S₅. А долж­на быть равна (так как они со­став­ля­ют по по­ло­ви­не пло­ща­ди квад­ра­та). Ана­ло­гич­ное про­ти­во­ре­чие по­лу­ча­ет­ся, если центр квад­ра­та лежит внут­ри жёлтого пря­мо­уголь­ни­ка.

Рас­смот­рим один из цве­тов. По усло­вию из каж­дой вер­ши­ны вы­хо­дит ребро этого цвета. Всего число таких вы­хо­дов хотя бы 6, и при этом каж­дое ребро вы­хо­дит ровно из двух вер­шин. Зна­чит, всего рёбер каж­до­го цвета хотя бы 3. Из этого же сле­ду­ет, что каж­до­го цвета не более 6, так как иначе не хва­тит рёбер дру­гих цве­тов.

Как видно на ри­сун­ке, можно так по­кра­сить рёбра, что из каж­дой вер­ши­ны будет вы­хо­дить ровно по од­но­му ребру каж­до­го цвета. Всего за­кра­шен­ных рёбер будет 9, оста­нет­ся ещё 3 ребра. Эти 3 ребра можно кра­сить как угод­но. В за­ви­си­мо­сти от этого число зелёных рёбер будет ме­нять­ся от 3 до 6.

Рас­смот­рим про­из­воль­ную рас­крас­ку доски в два цвета, обо­зна­чим за x ко­ли­че­ство крас­но­ва­тых строк и за y  — ко­ли­че­ство си­не­ва­тых столб­цов в ней.

1.  Пусть сна­ча­ла n  — нечётно. Оцен­ка. Каж­дая крас­но­ва­тая стро­ка со­дер­жит не мень­ше крас­ных кле­ток, а каж­дый си­не­ва­тый стол­бец  — не мень­ше синих кле­ток, сле­до­ва­тель­но,

от­ку­да

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

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

от­ку­да

При от­сю­да сле­ду­ет При­мер. Рас­кра­сим левый ниж­ний квад­рат раз­ме­ра n − 2 на n − 2 кле­ток доски в синий и крас­ный цвета в шах­мат­ном по­ряд­ке, две верх­них стро­ки в синий цвет, а два пра­вых столб­ца  — в крас­ный цвет. Тогда n − 2 ниж­них стро­ки будут крас­но­ва­ты­ми, а n − 2 левых столб­ца  — си­не­ва­ты­ми.

3.  Остав­ши­е­ся слу­чаи малых чётных n. При n  =  2 по фор­му­ле зна­че­ние 2  =  2 + 0 до­сти­га­ет­ся при окрас­ке всех кле­ток доски в крас­ный цвет (или на­о­бо­рот в синий цвет). При n  =  4 по фор­му­ле зна­че­ние 5  =  4 + 1 до­сти­га­ет­ся при окрас­ке трёх левых столб­цов в крас­ный цвет и пра­во­го  — в синий. На­ко­нец, при n  =  6 по фор­му­ле Для до­сти­же­ния оцен­ки 9  =  6 + 3 окра­сим в крас­ный цвет все клет­ки трёх левых столб­цов, а также первую и вто­рую снизу клет­ки четвёртого, тре­тью и четвёртую снизу клет­ки пя­то­го, пятую и ше­стую снизу клет­ки ше­сто­го столб­цов. Осталь­ные 12 кле­ток кра­сим в синий.

Ответ: мак­си­маль­ное зна­че­ние суммы числа крас­но­ва­тых строк и числа си­не­ва­тых столб­цов равно:

а)  если n  — нечётно, то

б)  если n  — чётно и то

в)  для n рав­ных 2, 4, 8 со­от­вет­ствен­но 2, 5, 9.

Пусть N  — ис­ко­мое ко­ли­че­ство от­рез­ков. Вна­ча­ле най­дем N для

Сде­лан­ные на­блю­де­ния поз­во­ля­ют пред­по­ло­жить, что То есть при фик­си­ро­ван­ном n име­ют­ся от­рез­ки с раз­но­цвет­ны­ми кон­ца­ми любой длины от 1 до вклю­чи­тель­но. До­ка­жем это, пред­по­ла­гая За­ме­тим, что от­ре­зок длины по­стро­ить не­воз­мож­но, так как точки a₁ и a_n од­но­го цвета. Зна­чит, От­рез­ки длины 1 и оче­вид­но, по­стро­ить можно  — это от­рез­ки [1, 2] и По­ка­жем, что для лю­бо­го на­ту­раль­но­го m та­ко­го, что су­ще­ству­ет от­ре­зок с раз­но­цвет­ны­ми кон­ца­ми длины m. Дей­стви­тель­но, рас­смот­рим от­рез­ки длины m вида и Их левые концы окра­ше­ны в белый цвет. При этом их пра­вые концы и на­хо­дят­ся друг от друга на рас­сто­я­нии 2, а зна­чит оба окра­шен­ны­ми в белый цвет они быть не могут, так как, по усло­вию, рас­сто­я­ние между со­сед­ни­ми бе­лы­ми точ­ка­ми уве­ли­чи­ва­ет­ся с ро­стом n, и на рас­сто­я­нии 2 друг от друга лежат толь­ко две белые точки и Зна­чит, хотя бы один из от­рез­ков имеет концы раз­ных цве­тов. Таким об­ра­зом, фор­му­ла до­ка­за­на. Оста­лось по­лу­чить явную за­ви­си­мость a_n от n. Для этого дан­ные в усло­вии ра­вен­ства

сло­жим между собой. В ре­зуль­та­те по­лу­чим

Ответ:

За­ме­тим, что круж­ки можно раз­бить на груп­пы так, что линии про­ве­де­ны толь­ко между круж­ка­ми раз­ных групп (на кар­тин­ке круж­ки из раз­ных групп че­ре­ду­ют­ся). Иначе го­во­ря, это пол­ный дву­доль­ный граф, в одной доле ко­то­ро­го 3 вер­ши­ны, а в дру­гой 4. Один цвет не может при­сут­ство­вать в обеих долях. Это зна­чит, либо ис­поль­зо­ва­но всего два цвета, либо одна из долей по­кра­ше­на в один цвет, а дру­гая в два. Для двух цве­тов есть 6 ва­ри­ан­тов (3 спо­со­ба вы­брать цвет для пер­вой доли и после этого ещё 2 спо­со­ба для вто­рой). Для трех цве­тов рас­смот­рим два слу­чая.

Слу­чай 1. Доля с 3 вер­ши­на­ми по­кра­ше­на в один цвет (этот цвет вы­брать 3 спо­со­ба), а доля с 4 вер­ши­на­ми  — в два цвета (есть 2⁴ − 2=14 спо­со­бов вы­брать под­мно­же­ство, ко­то­рое будет окра­ше­но в пер­вый цвет, а осталь­ные вер­ши­ны кра­сим во вто­рой; 2 спо­со­ба вы­чи­та­ют­ся, по­сколь­ку нель­зя кра­сить все 4 вер­ши­ны в пер­вый цвет или все 4 вер­ши­ны во вто­рой). Итого 3 · 14  =  42 спо­со­ба.

Слу­чай 2. Доля с 4 вер­ши­на­ми по­кра­ше­на в один цвет (этот цвет вы­брать 3 спо­со­ба), а доля с 3 вер­ши­на­ми  — в два цвета (есть 2³ − 2  =  6 спо­со­бов вы­брать под­мно­же­ство, ко­то­рое будет по­кра­ше­но в пер­вый цвет, а осталь­ные вер­ши­ны кра­сим во вто­рой). Итого 3 · 6  =  18 спо­со­бов.

Ответ: 66 спо­со­бов.

Для каж­до­го че­ты­рех­уголь­ни­ка раз­би­е­ния вы­чис­лим ко­ли­че­ство его сто­рон с двумя чер­ны­ми кон­ца­ми, и все эти числа про­сум­ми­ру­ем. Легко ви­деть, что у че­ты­рех­уголь­ни­ка нуж­но­го вида такая сто­ро­на одна, а для осталь­ных окра­сок их число четно. Если утвер­жде­ние не­вер­но, то сумма всех этих чисел четна. При этом все внут­рен­ние сто­ро­ны учи­ты­ва­лись два раза. На пе­ри­мет­ре же че­ты­рех­уголь­ни­ка сто­рон нуж­но­го вида   — не­чет­ное число. Про­ти­во­ре­чие.

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

Ответ: за 100 ходов.

Обо­зна­чим точку пе­ре­се­че­ния трёх плос­ко­стей, раз­ре­за­ю­щих куб, через A. За­ме­тим, что объём лю­бо­го из 8 по­лу­чен­ных па­рал­ле­ле­пи­пе­дов равен про­из­ве­де­нию трёх его рёбер, вы­хо­дя­щих из A. Пусть мы хотим найти объём ка­ко­го-то бе­ло­го па­рал­ле­ле­пи­пе­да α. Пе­ре­мно­жим объёмы трёх чёрных па­рал­ле­ле­пи­пе­дов, при­мы­ка­ю­щих к α. Мы по­лу­чим про­из­ве­де­ние длин 9 от­рез­ков: рёбра па­рал­ле­ле­пи­пе­да α вы­хо­дя­щие из A, будут вхо­дить в про­из­ве­де­ние по два раза, a pёбра про­ти­во­по­лож­но­го к α чёрного па­рал­ле­ле­пи­пе­да β вы­хо­дя­щие из A,  — по од­но­му разу. Тогда, по­де­лив по­лу­чен­ное число на объём β мы по­лу­чим квад­рат объёма α.

Таким об­ра­зом, пе­ре­мно­жая трой­ки чисел из усло­вия и деля на четвёртое, мы по­лу­чим квад­ра­ты объёмов белых па­рал­ле­ле­пи­пе­дов; оста­нет­ся из­влечь корни.

Ответ: 2, 3, 4, 24.

Обо­зна­чим точку пе­ре­се­че­ния трёх плос­ко­стей, раз­ре­за­ю­щих куб, через A. За­ме­тим, что объём лю­бо­го из 8 по­лу­чен­ных па­рал­ле­ле­пи­пе­дов равен про­из­ве­де­нию трёх его рёбер, вы­хо­дя­щих из A. Пусть мы хотим найти объём ка­ко­го-то бе­ло­го па­рал­ле­ле­пи­пе­да α. Пе­ре­мно­жим объёмы трёх чёрных па­рал­ле­ле­пи­пе­дов, при­мы­ка­ю­щих к α Мы по­лу­чим про­из­ве­де­ние длин 9 от­рез­ков: рёбра па­рал­ле­ле­пи­пе­да α вы­хо­дя­щие из A, будут вхо­дить в про­из­ве­де­ние по два раза, а рёбра про­ти­во­по­лож­но­го к α чёрного па­рал­ле­ле­пи­пе­да β вы­хо­дя­щие из A  — по од­но­му разу. Тогда, по­де­лив по­лу­чен­ное число на объём β мы по­лу­чим квад­рат объёма α.

Таким об­ра­зом, пе­ре­мно­жая трой­ки чисел из усло­вия и деля на четвёртое, мы по­лу­чим квад­ра­ты объёмов белых па­рал­ле­ле­пи­пе­дов; оста­нет­ся из­влечь корни.

Ответ: 2, 3, 4, 24.

При­ве­дем при­мер. За­кра­сим клет­ки A(−505, 0) и B(505, 0). За 1515 ходов ладья дойдёт из B до любой клет­ки пра­вой по­ло­ви­ны доски (клет­ки (x, y) с не­от­ри­ца­тель­ным x): по­тре­бу­ет­ся не более 505 ходов по го­ри­зон­та­ли и не более 1010 по вер­ти­ка­ли. Ана­ло­гич­но из A ладья дойдёт до любой клет­ки левой по­ло­ви­ны.

Дадим оцен­ку. Назовём рас­сто­я­ни­ем между клет­ка­ми сумму рас­сто­я­ний между ними по вер­ти­ка­ли и по го­ри­зон­та­ли. Оно равно ми­ни­маль­но­му числу ходов, за ко­то­рое хро­мая ладья смо­жет дойти из одной клет­ки в дру­гую (и по­это­му удо­вле­тво­ря­ет «не­ра­вен­ству тре­уголь­ни­ка»). Пусть все клет­ки будут чёрными через 1514 минут. Про­ти­во­по­лож­ные уг­ло­вые клет­ки не могут быть «об­слу­же­ны» одной ладьёй: рас­сто­я­ние между ними боль­ше чем 2 · 1514. По­это­му каж­дая ладья «об­слу­жи­ла» две уг­ло­вые клет­ки с одной сто­ро­ны, на­при­мер ладья из клет­ки A  — обе левые: (−1010, ±1010), а ладья из клет­ки B  — обе пра­вые: (1010, ±1010). Но тогда вто­рая ладья не успе­ла дойти ни до одной из кле­ток (0, ±1010): рас­сто­я­ние от такой клет­ки до про­ти­во­по­лож­ной уг­ло­вой клет­ки равно 3030 > 2 · 1514. Ана­ло­гич­но и пер­вая ладья не дошла до этих кле­ток. Про­ти­во­ре­чие.

Ответ: через 1515 минут.

Рас­смот­рим 4 ва­ри­ан­та рас­крас­ки куба.

1)  Верх­няя и ниж­няя грани од­но­го цвета, левая и пра­вая грани од­но­го цвета. Вы­би­ра­ем цвет верх­ней и ниж­ней гра­ней 6 спо­со­ба­ми, затем цвет левой и пра­вой 5 спо­со­ба­ми, затем цвет пе­ред­ней 4 спо­со­ба­ми и цвет зад­ней 4 спо­со­ба­ми.

Итого, спо­со­бов.

2)  Верх­няя и ниж­няя грани од­но­го цвета, левая и пра­вая грани раз­но­го цвета. Вы­би­ра­ем цвет верх­ней и ниж­ней гра­ней 6 спо­со­ба­ми, затем цвет левой 5 спо­со­ба­ми, потом цвет пра­вой 4 спо­со­ба­ми, затем цвет пе­ред­ней 3 спо­со­ба­ми и цвет зад­ней 3 спо­со­ба­ми.

Итого, спо­со­бов.

3)  Верх­няя и ниж­няя грани раз­но­го цвета, левая и пра­вая грани од­но­го цвета. Вы­би­ра­ем цвет левой и пра­вой гра­ней 6 спо­со­ба­ми, затем цвет верх­ней 5 спо­со­ба­ми, потом цвет ниж­ней 4 спо­со­ба­ми, затем цвет пе­ред­ней 3 спо­со­ба­ми и цвет зад­ней 3 спо­со­ба­ми.

Итого, спо­со­бов.

4)  Верх­няя и ниж­няя грани раз­но­го цвета, левая и пра­вая грани раз­но­го цвета. Вы­би­ра­ем цвет верх­ней грани 6 спо­со­ба­ми, затем цвет ниж­ней грани 5 спо­со­ба­ми, потом цвет левой грани 4 спо­со­ба­ми, затем цвет пра­вой 3 спо­со­ба­ми, далее цвет пе­ред­ней грани 2 спо­со­ба­ми и зад­ней 2 спо­со­ба­ми.

Итого, спо­со­бов.

Окон­ча­тель­но имеем

Ответ: 4080.

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

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

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

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

Раз­ре­жем квад­рат, как от­ме­че­но на кар­тин­ке. Рас­смот­рим шесть рав­ных пря­мо­уголь­ни­ков: левый верх­ний, левый ниж­ний и пра­вый сред­ний по­пар­но пе­ре­во­дят­ся друг в друга с по­мо­щью па­рал­лель­но­го пе­ре­но­са на век­тор длины один. Сле­до­ва­тель­но, пло­щадь за­кра­шен­ной части не пре­вы­ша­ет трети от пло­ща­ди серых пря­мо­уголь­ни­ков. Ана­ло­гич­ные рас­суж­де­ния при­ме­ни­мы для пря­мо­уголь­ни­ков с точ­ка­ми.

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

Итого по­лу­ча­ем оцен­ку в

Ответ: 1,63...

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

Те­перь, ис­поль­зуя по­стро­ен­ный при­мер, до­ка­жем, что един­ствен­ным от­ве­том за­да­чи яв­ля­ют­ся имен­но 20 кле­ток. Рас­смот­рим раз­би­е­ние доски на 10 ча­стей, ука­зан­ных в при­ме­ре. Даль­ше везде будем на­зы­вать фи­гу­ра­ми имен­но эти части дан­но­го при­ме­ра. Назовём цен­траль­ны­ми клет­ка­ми каж­дой фи­гу­ры те, что от­ме­че­ны в при­ме­ре на ри­сун­ке. Вспом­ним, что шах­мат­ная доска имеет есте­ствен­ную рас­крас­ку кле­ток в шах­мат­ном по­ряд­ке и рас­смот­рим в каж­дой фи­гу­ре её чёрную и белую части, со­сто­я­щие из чёрных и белых кле­ток этой фи­гу­ры со­от­вет­ствен­но. За­ме­тим, что белая цен­траль­ная клет­ка фи­гу­ры со­сед­ству­ет толь­ко с чёрными клет­ка­ми толь­ко этой фи­гу­ры, причём со всеми, и чёрная цен­траль­ная клет­ка фи­гу­ры со­сед­ству­ет толь­ко с бе­лы­ми клет­ка­ми толь­ко этой фи­гу­ры, причём со всеми.

Рас­смот­рим те­перь про­из­воль­ную раз­мет­ку кле­ток на доске, удо­вле­тво­ря­ю­щую усло­вию за­да­чи, и до­ка­жем, что каж­дая фи­гу­ра со­дер­жит ровно две от­ме­чен­ные клет­ки, от­ку­да будет сле­до­вать ответ за­да­чи. Дей­стви­тель­но, если не­ко­то­рая фи­гу­ра со­дер­жит не мень­ше трёx от­ме­чен­ных кле­ток, то она со­дер­жит не мень­ше двух белых от­ме­чен­ных, либо не мень­ше двух чёрных от­ме­чен­ных, тогда цен­траль­ная клет­ка про­ти­во­по­лож­но­го цвета этой фи­гу­ры будет со­сед­ней не менее, чем с двумя от­ме­чен­ны­ми, что про­ти­во­ре­чит усло­вию. А если не­ко­то­рая фи­гу­ра со­дер­жит не боль­ше одной от­ме­чен­ной клет­ки, то в ней либо не будет белых от­ме­чен­ных кле­ток, либо не будет чёрных от­ме­чен­ных кле­ток, тогда цен­траль­ная клет­ка про­ти­во­по­лож­но­го цвета этой фи­гу­ры во­об­ще не будет со­сед­ней ни с какой от­ме­чен­ной клет­кой, что тоже про­ти­во­ре­чит усло­вию. Сле­до­ва­тель­но, каж­дая фи­гу­ра со­дер­жит по две от­ме­чен­ных клет­ки, по­это­му любой при­мер со­дер­жит ровно 20 от­ме­чен­ных кле­ток.

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

Ответ: 20.

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

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

Под­счи­та­ем сна­ча­ла ко­ли­че­ство квад­ра­тов в таб­ли­це Каж­дый такой квад­рат од­но­знач­но опре­де­ля­ет­ся по­ло­же­ни­ем своей левой ниж­ней вер­ши­ны. Этой вер­ши­ной может быть любая уз­ло­вая точка той части таб­ли­цы, ко­то­рая оста­нет­ся, если из таб­ли­цы от­ре­зать свер­ху и спра­ва ка­ем­ку в 4 клет­ки: оста­нет­ся левый ниж­ний квад­рат раз­ме­ра В таком квад­ра­те уз­ло­вых точек. Итак, име­ет­ся 25 квад­ра­тов Раз­лич­ных ва­ри­ан­тов (по ко­ли­че­ству плю­сов) за­пол­не­ния квад­ра­та име­ет­ся всего 17 (число плю­сов  — от 0 до 16). По­сколь­ку 25 > 17, най­дут­ся хотя бы два квад­ра­та с оди­на­ко­вым ко­ли­че­ством плю­сов.

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

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

Объ­яс­ним, как де­лать сле­ду­ю­щий шаг внут­ри одной пары столб­цов X и Y. Пусть в сле­ду­ю­щей стро­ке A сей­час на­хо­дят­ся чёрная и белая клет­ка, но в не­пра­виль­ном по­ряд­ке. На­при­мер, слева стоит чёрная клет­ка, а спра­ва белая, а долж­но быть на­о­бо­рот. За­ме­тим, что во всех стро­ках выше A в пер­вом столб­це сум­мар­но чёрных кле­ток не мень­ше, чем во вто­ром, так как они уже по­кра­ше­ны шах­мат­ным об­ра­зом. Зна­чит, в какой-то стро­ке B ниже A долж­на быть си­ту­а­ция, когда в левом столб­це чёрных кле­ток мень­ше, чем в пра­вом, то есть долж­на быть стро­ка белая-чёрная (это сле­ду­ет из того, что сум­мар­но в пер­вом столб­це столь­ко же чёрных кле­ток, сколь­ко и во вто­ром). Про­из­ведём опе­ра­цию со стро­ка­ми A и B и те­ку­щи­ми столб­ца­ми (см. рис. 1).

Пусть те­перь у нас в стро­ке A стоят две оди­на­ко­вые клет­ки, на­при­мер чёрные. Тогда в какой-то стро­ке B долж­ны ока­зать­ся две белые клет­ки (иначе сум­мар­но чёрных кле­ток в этих двух столб­цах будет слиш­ком много). По­нят­но, что эта стро­ка рас­по­ло­же­на ниже те­ку­щей, т. к. выше неё все стро­ки раз­но­цвет­ные. Те­перь за­ме­тим, что если по­смот­реть на эту пару строк во всей таб­ли­це, то дол­жен быть стол­бец Z пра­вее X и Y, в ко­то­ром в пер­вой стро­ке белая клет­ка, а во вто­рой  — чёрная. Тут мы поль­зу­ем­ся тем, что левее наших столб­цов в этих стро­ках по­ров­ну чёрных и белых кле­ток. Те­перь оста­лось лишь вы­брать один из столб­цов X или Y (в ко­то­ром не­пра­виль­ный цвет в стро­ке A) и стол­бец Z, а также стро­ки A и B и про­из­ве­сти опе­ра­цию с ними (см. рис. 2).

Легко ви­деть, что на каж­дом шаге урав­но­ве­шен­ность доски со­хра­ня­ет­ся. А так как мы все­гда можем сде­лать шаг в нашем ал­го­рит­ме, то в конце по­лу­чит­ся шах­мат­ная рас­крас­ка.

До­ка­жем, что мак­си­маль­ное число цве­тов в усло­ви­ях за­да­чи не боль­ше 11. Рас­смот­рим в квад­ра­те 4 на 4 пять квад­ра­тов раз­ме­ра 2 на 2 клет­ки: че­ты­ре уг­ло­вых и цен­траль­ный. Уг­ло­вые квад­ра­ты 2 на 2 не пе­ре­се­ка­ют­ся, а цен­траль­ный имеет по одной общей клет­ке с каж­дым из уг­ло­вых. По усло­вию, каж­дый уг­ло­вой квад­рат 2 на 2 со­дер­жит клет­ки не более трёх раз­лич­ных цве­тов, всего не боль­ше 12. Но если среди этих четырёх троек цве­тов в уг­ло­вых квад­ра­тах нет по­вто­ря­ю­щих­ся, то цен­траль­ный квад­рат 2 на 2 дол­жен со­дер­жать клет­ки четырёх раз­лич­ных цве­тов  — по одной из каж­дой трой­ки, что про­ти­во­ре­чит усло­вию. Сле­до­ва­тель­но, общее число раз­лич­ных цве­тов, в ко­то­рые окра­ше­ны клет­ки квад­ра­та 4 на 4 не пре­вос­хо­дит Если же хотя бы в одном из уг­ло­вых квад­ра­тов 2 на два ис­поль­зо­ва­но не боль­ше двух раз­лич­ных цве­тов, то всего раз­лич­ных цве­тов сразу не боль­ше 11. При­мер рас­крас­ки квад­ра­та 4 на 4 в 11 цве­тов, удо­вле­тво­ря­ю­щей усло­вию за­да­чи вы­гля­дит так: ниж­няя го­ри­зон­таль квад­ра­та кра­сит­ся в раз­лич­ные цвета 1, 2, 3 и 4, вто­рая го­ри­зон­таль  — вся в цвет 5, тре­тья го­ри­зон­таль в раз­лич­ные цвета 6, 7, 8 и 9, а четвёртая го­ри­зон­таль  — в цвета 10, 7, 11, 9.

Ответ: в 11 цве­тов.

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

С дру­гой сто­ро­ны, для каж­дой вер­ши­ны A 11-уголь­ни­ка най­дут­ся такие вер­ши­ны B и C крас­но­го цвета, что AB  =  AC. За­ме­тим, что точка A лежит на се­ре­дин­ном пер­пен­ди­ку­ля­ре к от­рез­ку BC и ни­ка­кая дру­гая вер­ши­на 11-уголь­ни­ка на этом пер­пен­ди­ку­ля­ре не лежит. Зна­чит, ко­ли­че­ство от­рез­ков с кон­ца­ми в вер­ши­нах крас­но­го цвета долж­но быть не мень­ше ко­ли­че­ства вер­шин, то есть 11. Про­ти­во­ре­чие для вер­шин с об­щи­ми крас­ны­ми кон­ца­ми. В силу «сим­мет­рии» за­да­чи ана­ло­гич­ные рас­суж­де­ния можно вы­пол­нить и для от­рез­ков с обо­и­ми си­ни­ми кон­ца­ми.

Ответ: такая си­ту­а­ция не­воз­мож­на.