United States 1998

We color a $98 \times 98$ checkerboard in a chessboard pattern. A move consists of selecting a rectangle made up of small squares and inverting their colors. What is the minimum number of moves required to make the checkerboard monochrome?
More generally, on an $n \times m$ grid, it suffices to $\left\lfloor\frac{n}{2}\right\rfloor+\left\lfloor\frac{m}{2}\right\rfloor$ moves by acting on the even rows and columns (the order of operations does not matter).

Let's first consider a $1 \times 98$ rectangle, which has 97 problematic cell boundaries. Selecting a sub-rectangle from this removes at most 2, so at least 49 such sub-rectangles need to be activated. Consider the 4 "boundary" $1 \times 98$ rectangles on the edge of the rectangle. Each of these must therefore intersect at least 49 of the chosen rectangles. If one of these rectangles intersects three of the four boundary rectangles, it must cross two opposite ones and contain the third. A chosen rectangle thus acts usefully on at most two boundary rectangles. Therefore, we will need at least $49 \times 4 / 2=98$ moves.