A 98 x 98 chess board has the squares colored alternately black and white in the usual way. A move consists of selecting a rectangular subset of the squares (with boundary parallel to the sides of the board) and changing their color. What is the smallest number of moves required to make all the squares black?
Solution
Answer: 98.
There are 4·97 adjacent pairs of squares in the border and each pair has one black and one white square. Each move can fix at most 4 pairs, so we need at least 97 moves. However, we start with two corners one color and two another, so at least one rectangle must include a corner square. But such a rectangle can only fix two pairs, so at least 98 moves are needed.
It is easy to see that 98 suffice: take 49 1x98 rectangles (alternate rows), and 49 98x1 rectangles (alternate columns).
© John Scholes
jscholes@kalva.demon.co.uk
11 May 2002