Problem 3

Consider an

n\times n

square board, where

n

is a fixed even positive integer. The board is divided into

n^2

unit squares. We say that two different squares on the board are adjacent if they have a common side.

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

Step 3 of 5: Count the construction

Previous step Next step

In plain words

Count the arithmetic progression of marks.

1+2+\cdots+m=\frac{m(m+1)}2

Detailed analysis

The numbers of marks on the selected diagonals are $1,2,\ldots,m$ in the required sequence (the two halves of the board contribute $1,3,5,\ldots$ and then $m,m-2,\ldots$ ). Thus $m(m+1)/2$ marked white squares dominate all black squares. Repeating with colors exchanged gives a configuration with $m(m+1)$ marks dominating the whole board.