# 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

Answer: $98$.

There are $4\cdot97$ 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 moves suffice: take 49 $1\times98$ rectangles (alternate rows), and 49 $98\times1$ rectangles (alternate columns).

editor: Brian Joseph

second editor: integralarefun