Consider an $n \times n$ square board, where $n$ is a fixed positive even integer. The board is divided into $n^{2}$ unit squares. We say that two squares on the board are adjacent if they share a common side.

On the board, $N$ unit squares are marked in such a way that every square (marked or unmarked) is adjacent to at least one marked square.

Determine the smallest possible value of $N$.
Divide the square into frames according to the diagram, and starting from the outermost frame, color every second frame black. On the board, every cell is adjacent to exactly two black cells, so we must mark at least half of the black cells to ensure that every black cell has a marked neighbor. $N$ is therefore at least half the number of these. Let's calculate this in the case when $n$ is divisible by 4, and when $n$ is not divisible by 4 (the coloring in the first diagram corresponds to case a).

\[
\left.4 \mid n: \quad \frac{1}{2}\left[12+(16+12)+\cdots+\left(\frac{n-4}{4} \cdot 16+12\right)\right]=\frac{1}{2}\left[\frac{n}{4} \cdot 12+16 \cdot \frac{n-4}{4} \cdot \frac{n}{4} \cdot \frac{1}{2}\right]=\mathrm{a}\right) \quad=\frac{1}{2}\left[3 n+\frac{n(n-4)}{2}\right]=\frac{n^{2}+2 n}{4},
\]

\[
\left.4 \nmid n: \quad \frac{1}{2}\left[4+(4+16)+\cdots+\left(4+\frac{n-2}{4} \cdot 16\right)\right]=\frac{1}{2}\left[\frac{n+2}{4} \cdot 4+16 \cdot \frac{n-2}{4} \cdot \frac{n+2}{4} \cdot \frac{1}{2}\right]=\mathrm{b}\right) \quad=\frac{1}{2}\left[n+2+\frac{n^{2}}{2}-2\right]=\frac{n^{2}+2 n}{4}
\]

This value can be achieved by marking cells inside the black frames in the following manner: starting from the bottom-left corner of the black frames, mark two adjacent cells, then skip two, then mark two again, and so on, always stepping along the frame. This way, we clearly mark half of the cells in each frame, thus marking a total of $\frac{n^{2}+2 n}{4}$ cells. The cells of the black frames will have marked neighbors, and the cells of the white frames will have marked neighbors on the adjacent black frames, since we started the marking inside the black frames exactly two cells "higher" than the previous frame, thus the marked cells of the two frames alternate.

The smallest possible value of $N$ is therefore $\frac{n^{2}+2 n}{4}$. The marking for $n=2,4,6,8$ is shown in the second diagram (a, b, c, d).

Based on the solution by Kiss Gergely and Keszegh Balázs

Note. For $n=4 k+1$, $\frac{n^{2}+2 n+1}{4}$ cells need to be marked, and for $n=4 k+3$, $\frac{n^{2}+2 n-3}{4}$ cells need to be marked. The proof of this is not included here.
![](https://cdn.mathpix.com/cropped/2024_05_02_d36522ce0b3a24e14577g-1.jpg?height=1092&width=374&top_left_y=1186&top_left_x=865)[^0]

[^0]: ${ }^{0}$ Keszegh Balázs, a student at Fazekas Mihály Gyakorló Gimnázium in Budapest, participated in the competition as a member of the Slovak team.