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 4 of 5: Prove the lower bound for white marks

Previous step Next step

In plain words

Odd diagonal lengths force a ceiling after dividing by two.

\text{at least }1+2+\cdots+m

Detailed analysis

For necessity, consider the alternate odd-length black diagonals, whose lengths are $1,3,\ldots,2m-1$ . A white square is adjacent to squares in only one of these diagonals and to at most two squares in it. A diagonal of length $2r+1$ therefore requires at least $r+1$ marked white squares. Summing gives at least $1+2+\cdots+m=m(m+1)/2$ white marks.