|
|
 |
Условие
Каждая клетка доски 100×100 окрашена либо в чёрный, либо в белый цвет, причём все клетки, примыкающие к границе доски – чёрные. Оказалось, что нигде на доске нет одноцветного клетчатого квадрата 2×2. Докажите, что на доске найдётся клетчатый квадрат 2×2, клетки которого окрашены в шахматном порядке.
Решение
Предположим противное: на доске нет ни одноцветных, ни шахматно окрашенных квадратов 2×2. Рассмотрим все отрезки сетки, разделяющие две разноцветных клетки (назовём их разделителями); пусть их количество равно N.
В любом квадрате 2×2 есть либо ровно одна клетка одного из цветов и три клетки другого, либо две соседних белых клетки и две соседних чёрных. В обоих случаях внутри квадрата есть ровно два разделителя. Всего имеется 99² квадратов 2×2, а каждый разделитель лежит внутри ровно двух из них (по условию к границе разделители не примыкают). Значит, N = 2·99² : 2 = 99².
С другой стороны, N должно быть чётным. Действительно, в каждой строке и каждом столбце первая и последняя клетка – чёрные; поэтому там должно быть чётное число перемен цвета. Противоречие.
Замечания
1. Количество разделителей равно количеству разноцветных доминошек. Вместо него можно подсчитать количество одноцветных доминошек – оно равно 2·100·99 – N.
2. Чётность общего количества разделителей можно доказать разными методами. Например, можно заметить, что если все внутренние клетки белые, то число разделителей равно 4·98, а при любой перекраске внутренней клетки оно может измениться только на чётную величину.
