14th Mexico 2000 Problem B2 Given an n x n board with squares colored alternately black and white like a chessboard. An allowed move is to take a rectangle of squares (with one side greater than one square, and both sides odd or both sides even) and change the color of each square in the rectangle. For which n is it possible to end up with all the squares the same color by a sequence of allowed moves?
n ≠ 2 Solution For n odd we can invert a 1 x n rectangle, so we invert alternate columns. That gives the first row black, the second white, the third black and so on. So by inverting alternate rows we get all squares the same color. Now if we can do n, then we can do 2n, because we can divide the 2n x 2n board into 4 equal parts and do each part separately. We can do n = 4 by four 3 x 1 moves and two 2 x 2 moves as follows: B W B W B W B B B W B B B B W W B B W W W W W W W W W W W B W B W B W W W B W W W B W W B B W W W W W W W W W W B W B W B W B B B W B B B W B B W W B B W W B B W W W W W B W B W B W B B W B B B W B B W W B B W W B B W W W W Hence we can do all n ≥ 3. n = 2 is obviously impossible. n = 1 is trivially possible (do nothing). 14th Mexican 2000 © John Scholes jscholes@kalva.demon.co.uk 9 March 2004 Last corrected/updated 9 Mar 04