1
$\begingroup$

A $98 \times 98$ chess board has the squares colored alternately black and white in the usual way. A move consists of selecting a rectangular subset of the squares (with boundary parallel to the sides of the board) and changing their color. What is the smallest number of moves required to make all the squares black?

The solution given is:

There are $4 \cdot 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.

I have difficulty in understanding the solution specially the bold part. Please can someone help. I understand how 98 can be achieved but cant prove its the minimum, other proofs are welcome as well.

$\endgroup$
2
$\begingroup$

If two adjacent squares on an edge are different colors, they can only be made the same color (this is what they mean by "fixed") if one square is in the rectangle being inverted and one of them isn't. This is only possible if one square is a vertex of the rectangle; every rectangle has at most 4 vertices, so you need at least (number of different-colored pairs of adjacent squares)/4 rectangles, presuming every rectangle can actually fix four pairs.

But at least one rectangle has to include a corner square, because two of the corner squares are white. Let's look, say, at the bottom left square, which we'll presume to be white. This corner can be made black by a rectangle containing just the corner square (which fixes the two pairs adjacent to the corner square), a $1 \times n$ vertical rectangle (which fixes the horizontal pair containing the corner square and a vertical pair $n$ places higher), or a $1 \times n$ horizontal square (symmetrical), or an $m \times n$ rectangle (which doesn't fix the corner square, but does fix two pairs elsewhere). In no case can we fix four pairs, so our minimum is actually greater than 97.

$\endgroup$
2
$\begingroup$

Consider the rectangular subset of the squares used in a move. If this subset does not include squares adjacent to the border, then none of those $4\times 97$ pairs are fixed. If a corner is adjacent to a border (but not the corner of the $98\times 98$ square), then one pair is fixed. Since our rectangular subset has four corners, at most four pairs are fixed.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.