# 1998 USAMO problem #4

A $$98 \times 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?

The solution given is:

There are $$4 \cdot 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.

I have difficulty in understanding the solution specially the bold part. Please can someone help. I understand how 98 can be achieved but cant prove its the minimum, other proofs are welcome as well.

• I don't understand this part: "A move consists of selecting a rectangular subset of the squares (with boundary parallel to the sides of the board) and changing their color". That means selecting all square of board (that is a rectangle) is a move? Commented Sep 4, 2020 at 12:34

But at least one rectangle has to include a corner square, because two of the corner squares are white. Let's look, say, at the bottom left square, which we'll presume to be white. This corner can be made black by a rectangle containing just the corner square (which fixes the two pairs adjacent to the corner square), a $1 \times n$ vertical rectangle (which fixes the horizontal pair containing the corner square and a vertical pair $n$ places higher), or a $1 \times n$ horizontal square (symmetrical), or an $m \times n$ rectangle (which doesn't fix the corner square, but does fix two pairs elsewhere). In no case can we fix four pairs, so our minimum is actually greater than 97.
Consider the rectangular subset of the squares used in a move. If this subset does not include squares adjacent to the border, then none of those $4\times 97$ pairs are fixed. If a corner is adjacent to a border (but not the corner of the $98\times 98$ square), then one pair is fixed. Since our rectangular subset has four corners, at most four pairs are fixed.