МОШ 2021, 9 класс, задача 2

Решение 1. Предположим, что вырезать такие два квадрата Арсению не удастся. Это означает, что любые два квадрата, совпадающие по раскраске, пересекаются хотя бы по одной клетке.

Разобьём наш квадрат на квадратов , как отмечено на рис. 1a; все они должны быть раскрашены по-разному. Так как всего разных способов раскрасить квадрат в два цвета ровно , то все раскраски среди них присутствуют по одному разу.

Теперь выделим квадратов-«потомков» , отмеченных на рис. 1b, каждый из которых пересекается с двумя квадратами-«родителями» первого разбиения, состыкованными горизонтально. Заметим, что каждый «потомок» совпадает по раскраске с одним из «родителей» (так как он должен совпасть с одним их квадратов первого разбиения, и он не может совпасть с теми, с которыми он не пересекается).

Но если два квадрата, смещённые друг относительно друга на одну клетку по горизонтали, совпадают по раскраске, то их верхние клетки должны быть одного цвета, и их нижние клетки тоже одного цвета. Это даёт всего четыре варианта раскраски для таких квадратов-«потомков». Но всего их , значит, какие-то два их них совпадут по раскраске; при этом они все попарно не пересекаются. Противоречие.

Решение 2. Как и в предыдущем решении, предположим, что вырезать такие два квадрата Арсению не удалось.

Рассмотрим все квадратов . Так как всего возможных раскрасок таких квадратов , то по принципу Дирихле некоторые четвёрки квадратов совпадают по раскраске.

Во-первых, заметим, что более чем квадрата по раскраске совпасть не могут. Действительно, в этом случае либо их вертикальные координаты, либо горизонтальные принимают хотя бы три различных значения, то есть у двух квадратов одна из координат отличается хотя бы на (для определенности можно рассматривать координаты центров квадратов). Такие квадраты пересекаться не могут.

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

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

Тогда из совпадения раскрасок следует, что клетки , , имеют одинаковый цвет; аналогично с тройками клеток {2, 3, 5}, {4, 5, 7}, {5, 6, 8}. Получается, что у всех этих клеток один и тот же цвет.

Ясно, что для четырёх квадратов с одинаковой раскраской вывод будет аналогичен. Это означает, что в тройке или четвёрке квадратов с совпадающей раскраской они все либо целиком первого цвета, либо целиком второго. Значит, все остальные способов раскрасить квадрат могут быть представлены не более чем экземплярами.

Тогда всего квадратов не более . Но их . Противоречие.