MathLabs

Problem 3

Consider an n×n n\times n square board, where n n is a fixed even positive integer. The board is divided into n2 n^2 unit squares. We say that two different squares on the board are adjacent if they have a common side. N N unit squares on the board are marked in such a way that every square (marked or unmarked) on the board is adjacent to at least one marked square. Determine the smallest possible value of N N .
Step 2 of 5: Construct marks for one color
Previous stepNext step
In plain words

Alternate marks along alternating diagonals cover the opposite color.

1+3+⋯+(2r+1) on an odd diagonal1+3+\cdots+(2r+1)\text{ on an odd diagonal}
Detailed analysis

Look at the odd-length white diagonals in one diagonal direction. On every other such diagonal of length 2r+12r+1, mark alternate squares starting at the border; this marks r+1 r+1 squares. Every black diagonal lies next to one selected white diagonal, so each black square has a marked white neighbor.