(United States 1998)

Consider a $m \times n$ chessboard whose squares are colored in the usual black and white pattern. A move consists of choosing a rectangle of squares and inverting the colors of all the squares in it. What is the minimum number of moves required to make the chessboard monochrome?
We will show that the minimum number of moves is

$$
\left\lfloor\frac{n}{2}\right\rfloor+\left\lfloor\frac{m}{2}\right\rfloor
$$

To do this, first note that this value is achievable by inverting the colors of all even rows or columns (in any order, as the operations commute). Now, let's show that we cannot do better.

Consider the $1 \times n$ column on the left of the checkerboard. We count the number of pairs of adjacent cells of different colors in this column. At the beginning, there are $n-1$ such pairs, and each operation can decrease this value by at most 2. Therefore, it takes at least $\left\lceil\frac{n-1}{2}\right\rceil$ operations to make the column all the same color, which is $\left\lfloor\frac{n}{2}\right\rfloor$.

This reasoning remains valid for the right column, the top row, and the bottom row of the grid, replacing $n$ with $m$ for the rows. However, if a rectangle touches three of these rows/columns, it necessarily contains one of them entirely, and thus does not act on it in a useful way. Therefore, each move acts usefully on at most two of these rows/columns, so the minimum number of operations is greater than

$$
\frac{1}{2}\left(2\left\lfloor\frac{n}{2}\right\rfloor+2\left\lfloor\frac{m}{2}\right\rfloor\right)=\left\lfloor\frac{n}{2}\right\rfloor+\left\lfloor\frac{m}{2}\right\rfloor
$$

hence the result.