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

На клетчатой доске размером $2014 \times 2014$ закрашено несколько (не меньше одной) клеток так, что в каждом квадратике размером $3 \times 3$ клетки закрашено чётное число клеток. Каково наименьшее возможное число закрашенных клеток? ( М. Антипов )

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

Комментарии от администратора Комментарии от администратора №1.     Ответ. 1342.
Решение. Пример. Закрасим в первой вертикали доски вторую, третью, пятую, шестую, $\dots$, 2012-ую и 2013-ую клетки. Тогда во всех квадратах $3 \times 3$, примыкающих к левому краю доски, закрашено ровно по две клетки, а во всех остальных закрашенных клеток нет. Всего в этом случае закрашено $2 \cdot 2013/3 = 1342$ клетки.
Оценка. Пусть на доске закрашено меньше 1342 клеток. Назовём тройку горизонталей доски, идущих подряд, слабой, если в ней есть хотя бы две горизонтали, не содержащие закрашенных клеток. Покажем, что слабые тройки есть. В самом деле, разобьём все горизонтали доски, кроме первой, на тройки идущих подряд. Получим 671 тройку. Если среди них нет слабых, то в каждой содержится не меньше двух закрашенных клеток, и всего закрашено не меньше, чем $671 \cdot 2 = 1342$ клетки — противоречие.
Заметим, что найдётся слабая тройка, в которой есть закрашенные клетки. Действительно, возьмём произвольную слабую тройку. Если в ней нет закрашенных клеток, то, двигая её в сторону одной из закрашенных клеток, мы рано или поздно наткнёмся на строку, где закрашенные клетки есть, и получим искомую тройку. Зафиксируем её, удалим из прямоугольника $2014 \times 3$, составленного из её горизонталей, три крайние правые клетки, а оставшийся прямоугольник $2013 \times 3$ разобьём на 671 квадрат $3 \times 3$. В каждом из этих квадратов либо две закрашенных клетки, либо ни одной. Если в каждом по две, то всего закрашено не меньше 1342 клеток — противоречие. Значит, найдётся квадрат без закрашенных клеток. Будем двигать его по горизонтали в сторону ближайшей закрашенной клетки. Когда в него впервые попадёт закрашенная клетка, получим квадрат, в котором закрашена ровно одна клетка — противоречие.