Loading [MathJax]/jax/output/SVG/jax.js

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


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

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

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