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 1 of 5: Set the half-size

Previous step Next step

In plain words

Use the even side length and the bipartite coloring.

n=2m

Detailed analysis

Write $n=2m$ . Color the board like a chessboard. We first count the marked white squares needed to give every black square a marked neighbor, then apply the same argument with the colors exchanged.