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 5 of 5: Finish the minimum
Previous stepNext step
In plain words

Combine the two color classes.

N≥2⋅m(m+1)2=m(m+1)N\ge2\cdot\frac{m(m+1)}2=m(m+1)
Detailed analysis

The same lower bound applies to marked black squares needed to dominate the white squares. Hence every valid marking has at least m(m+1) m(m+1) squares, while the two-color construction attains this number. Therefore the minimum is m(m+1)=n(n+2)4 m(m+1)=\frac{n(n+2)}4.