Question

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

Answer 1

Ответ:

32

Объяснение:

32

Answer 2

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

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

Если мы покрасим в черный цвет все клетки, кроме квадрата 3×3, тогда для каждой строки и столбца должно существовать по одной клетке (не входящей в 3×3 квадрат), которая остаётся белой. Нам нужно понять, сколько всего таких клеток (не входящих в 3×3 квадрат) существует.

В прямоугольнике 10×10 всего 100 клеток. Квадрат 3×3 занимает 9 клеток. Таким образом, если к клеток покрашено в черный цвет, остаётся \(100 - k\) белых клеток.

Чтобы удовлетворить условиям задачи, оставшиеся 91 белая клетка (100 - 9 - k) должны равномерно распределиться в каждой строке и столбце так, чтобы в каждом из них оставалась по одной белой клетке.

Поскольку в каждой строке и столбце должно быть по две нечерных клетки, а одна из них — белая, оставшиеся 91 белая клетка не могут равномерно распределиться среди строк и столбцов. Например, у нас есть 10 строк, так что в сумме мы получаем 20 клеток, и чтобы разместить в них 91 белую клетку так, чтобы в каждой строке и столбце было по одной белой клетке, это невозможно.

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