Consider a n by 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.
M 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 M.
Source: IMO 1999
Split the squares on the board into two groups by checkerboard parity, call then white and black. Every white square must be adjacent to a marked black square and similarly every black square must be adjacent to a marked white square.
By symmetry any pattern which minimizes the number of marked white squares will also minimize the number of marked black squares. So determining which white squares need to be marked and doubling the result will yield the answer.
Mark alternating white diagonals parallel to the longest black diagonal (example: n=6, NW-SE orientation):
bMb.bM
.bMb.b
b.bMb.
Mb.bMb
bMb.bM
.bMb.b
Every black tile is adjacent to at least one marked tile. For any even n there are 1 + 3 + ... + (n-1) = (n/2)^2 white marked tiles.
But an improvement can be made; notice that other than on the edges every black tile is adjacent to two marked tiles. Almost half of those tiles can be unmarked. Specifically for a marked diagonal with 2k+1 tiles, k of them can be unmarked.
bMb.bM
.b.b.b
b.bMb.
Mb.b.b
b.b.bM
.bMb.b
Every black tile is adjacent to exactly one marked white tile. Now there are only 1 + 2 + ... + (n/2) = (n/2)*(n/2+1)/2 = (n^2+2n)/8 marked white tiles. Marking the black tiles similarly makes a total number of marked tiles equal to (n^2+2n)/4 = M.
Solution
