Задача из журнала «Квант» (2000 год, 1 выпуск)

Условие

В квадрате клетчатой бумаги размером $n\times n$ клеток отмечены $N$ клеток таким образом, что каждая клетка квадрата (отмеченная или не отмеченная) имеет хотя бы одну отмеченную соседнюю клетку. Определите наименьшее возможное значение $N$, если соседними считать клетки, имеющие общую сторону.

Решение

Рассмотрим случай четного $n$.

Сначала раскрасим доску в черный и белый цвета в шахматном порядке. Пусть $f\left(n\right)$ — это искомое число, а $f_{\omega}\left(n\right)$ — минимальное число белых клеток, которые должны быть отмечены таким образом, чтобы каждая черная клетка имела соседнюю отмеченную белую. Определим подобным образом $f_{b}\left(n\right).$ Благодаря симметричности шахматной доски $\left(n = 2k\right)$, мы имеем $f_{\omega}\left(n\right) = f_{b}\left(n\right)$; кроме этого, $f\left(n\right) = f_{\omega}\left(n\right) + f_{b}\left(n\right)$.

Было бы более удобно посмотреть на доску, развернув ее таким образом, чтобы главная черная диагональ (самая длинная) располагалась горизонтально. Тогда длины остальных черных диагоналей были бы $2, 4, \ldots, 2k, \ldots, 4, 2.$

Зачеркнем «нечетные» клетки белых диагоналей, расположенных под черными диагоналями длины $4i — 2$ в первом случае и под черными диагоналями длины $4i + 2$ во втором случае (см. рисунок).

В первом случае зачеркнутыми окажутся $2i$ белых клеток, а во втором случае $2i + 1$ белых клеток. Таким образом, всего мы зачеркнем
$$2 + 4 + \ldots + k + \ldots + 3 + 1 = \frac{k\left(k+1\right)}{2}$$
белых клеток. Легко видеть, что каждая черная клетка имеет белую зачеркнутую соседнюю клетку. Из этого следует, что
$$f_{\omega}\left(n\right) \leqslant \frac{k\left(k+1\right)}{2}.$$

Рассмотрим $\displaystyle\frac{k\left(k+1\right)}{2}$ зачеркнутых белых клеток: у них нет общих черных соседних клеток, следовательно, нам нужно по крайней мере $\displaystyle\frac{k\left(k+1\right)}{2}$ черных отмеченных клеток с тем, чтобы «охватить» все эти белые клетки. Поэтому
$$f_{b}\left(n\right) \geqslant \frac{k\left(k+1\right)}{2}.$$
Отсюда мы имеем
$$f_{\omega}\left(n\right) = f_{b}\left(n\right) = \frac{k\left(k+1\right)}{2},$$
$$f\left(n\right) = k\left(k+1\right).$$

Аналогично доказывается, что
$$\begin{equation*} f\left(n\right) = \begin{cases} 4k^2 — 1 &\text{при $n = 4k — 1$,}\\ \left(2k + 1\right)^2 &\text{при $n = 4k + 1$.} \end{cases} \end{equation*}$$

Е. Баранов, И. Воронович