# 1998 USAMO Problems/Problem 4

(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

## Problem

A computer screen shows a $98 \times 98$ chessboard, colored in the usual way. One can select with a mouse any rectangle with sides on the lines of the chessboard and click the mouse button: as a result, the colors in the selected rectangle switch (black becomes white, white becomes black). Find, with proof, the minimum number of mouse clicks needed to make the chessboard all one color.

## Solution

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).

editor: Brian Joseph