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