Given an n x n square board, with n even. Two distinct squares of the board are said to be adjacent if they share a common side, but a square is not adjacent to itself. Find the minimum number of squares that can be marked so that every square (marked or not) is adjacent to at least one marked square.
Answer
Answer: n/2 (n/2 + 1) = n(n + 2)/4.
Solution
Let n = 2m. Color alternate squares black and white (like a chess board). It is sufficient to show that m(m+1)/2 white squares are necessary and sufficient to deal with all the black squares.
This is almost obvious if we look at the diagonals.
Look first at the odd-length white diagonals. In every other such diagonal, mark alternate squares (starting from the border each time, so that r+1 squares are marked in a diagonal length 2r+1). Now each black diagonal is adjacent to a picked white diagonal and hence each black square on it is adjacent to a marked white square. In all 1 + 3 + 5 + ... + m-1 + m + m-2 + ... + 4 + 2 = 1 + 2 + 3 + ... + m = m(m+1)/2 white squares are marked. This proves sufficiency.
For necessity consider the alternate odd-length black diagonals. Rearranging, these have lengths 1, 3, 5, ... , 2m-1. A white square is only adjacent to squares in one of these alternate diagonals and is adjacent to at most 2 squares in it. So we need at least 1 + 2 + 3 + ... + m = m(m+1)/2 white squares.
(C) John Scholes
jscholes@kalva.demon.co.uk
22 Aug 1999
Last corrected/updated 19 Aug 03