При каком наибольшем k можно утверждать что при любой покраске в черный цвет k клеток белого прямоугольника 7×10 обязательно останется целиком белый квадрат 3×3 со сторонами, идущими по линиям сетки?

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

Максимальное значение k, при котором можно гарантировать наличие целиком белого квадрата 3×3 в случае любой покраски черным цветом k клеток белого прямоугольника 7×10, составляет 12.

Для того чтобы найти это значение, давайте разместим центр каждого 3×3 квадрата на пересечении 3 вертикальных и 3 горизонтальных прямых, чтобы гарантировать, что он останется целиком белым, если все свои клетки окрашены черным цветом.

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

Далее, каждый следующий квадрат будет иметь 8 клеток и, если все его клетки окрашены черным цветом, он останется целиком белым только в том случае, если не менее 5 клеток, образующих его границу, останутся белыми. Поэтому для каждого из оставшихся 11 квадратов достаточно окрасить только 5 клеток - угловые и в середине его границ.

Если окрасить 12 клеток, хотя бы один из квадратов будет окрашен полностью, и ни один из них не сохранит свою целостность. Поэтому значение k=12 является максимальным для утверждения о наличии целиком белого квадрата 3×3 при любой покраске черным цветом k клеток белого прямоугольника 7×10.