Олимпиада имени Леонарда Эйлера 2017-2018 учебный год, II тур регионального этапа

На клетчатой белой доске размером $25\times25$ клеток несколько клеток окрашено в чёрный цвет, причём в каждой строке и каждом столбце окрашено ровно 9 клеток. При каком наименьшем $k$ заведомо можно перекрасить $k$ клеток в белый цвет таким образом, чтобы нельзя было вырезать чёрный квадрат $2\times2$? ( С. Берлов )

Комментарий/решение

Комментарии от администратора Комментарии от администратора №1.     Решение. Оценка. Заметим, что если в строчке закрашено 9 клеток, то можно перекрасить четыре из них так, чтобы никакие две закрашенные клетки не были соседними: достаточно перенумеровать закрашенные клетки слева направо и перекрасить клетки с чётными номерами. Если сделать такие перекрашивания со всеми чётными строками, то перекрасится 48 клеток и не будет закрашенных квадратов $2\times2,$ поскольку не будет двух соседних закрашенных клеток в одной чётной строке.
Пример. Закрасим расположенные вдоль главной диагонали непересекающиеся квадраты: первый со стороной 9 и два со стороной 8 --- и клетки, расположенные по незакрашенной главной диагонали квадрата $16\times16,$ содержащего квадраты $8\times 8.$ Тогда на доске можно будет выделить 48 не пересекающихся квадратов $2\times 2,$ все клетки которых закрашены. Поэтому в этом примере надо перекрасить не менее 48 клеток.