7.6.4. В прямоугольнике 6×7 закрашены какие-то 25 клеток. Докажите, что можно найти квадрат 2×2, в котором закрашено не менее трех клеток.

Предыдущий
вопрос Следующий
вопрос

Для доказательства этого утверждения возьмем любую клетку в прямоугольнике 6x7. Если взять клетку внутри прямоугольника, то у нее будет минимум 3 соседние клетки в том же ряду и минимум 3 соседние клетки в том же столбце. Таким образом, у данной клетки как минимум 3 соседние клетки по вертикали и горизонтали.

Рассмотрим 4 клетки, а именно выбранную клетку и три ее соседние. Если в данных 4 клетках нет квадрата 2x2, в котором будет закрашено не менее трех клеток, значит, одна из этих 4 клеток - угловая клетка прямоугольника. Но даже угловая клетка имеет минимум 2 соседние клетки в том же ряду или столбце, что противоречит тому, что 4 клетки не содержат квадрата 2x2 с закрашенными не менее трех клеток.

Таким образом, в прямоугольнике 6x7, где закрашены 25 клеток, всегда можно найти квадрат 2x2, в котором закрашено не менее трех клеток.