Два квадрата с одинаковой раскраской: олимпиадное задание

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

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

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

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

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

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

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

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

Тогда всего квадратов $2 \times 2$ не более $2 \cdot 4 + 14 \cdot 2 = 36$. Но их $49$. Противоречие.