Problem:
A computer screen shows a 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 and white becomes black). Determine the minimum number of mouse-clicks needed to make the chessboard all one color.
Solution:
The minimum number of clicks needed is . One way to do this is to click all the even numbered rows one by one ( clicks), then all the even numbered columns one by one (another clicks).
To show that this is minimal, note that there are pairs of adjacent squares along the border, and that any such pair is mismatched. Each click can fix at most adjacent pairs along the border, so it can reduce the number of mismatched pairs by at most , and thus at least clicks are necessary. However, since the corners are not all the same color, some of the clicks also need to deal with corner squares and thus can only reduce the number of mismatched border pairs by . Thus, we need at least clicks total, so this is indeed the minimum.