IMO 1999 Problem A3 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.
: 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. 40th IMO 1999 (C) John Scholes jscholes@kalva.demon.co.uk 22 Aug 1999 Last corrected/updated 19 Aug 03