Rectangle on a Chessboard
A rectangle is drawn on a chessboard with sides parallel to the sides of the latter. A sufficiently small rectangle may be included in a single chessboard square, but, in general, a rectangle will contain regions of both chessboard colors. The following supplies a condition that guarantees that the areas of those regions are equal.
A rectangle with sides parallel to the sides of a chessboard covers equal areas of the two colors if and only if one of the two conditions holds:
One of the sides of the rectangle is twice the side of a chessboard square. The dimension of the other side is irrelevant.
The center of the rectangle lies on a grid line.
Below, Nathan Bowler continues a discussion of this statement that began elsewhere.
By Nathan Bowler
Indeed, we may proceed as follows: Since rectangles of the above two types do contain equal areas of black and white, moving a side of any rectangle to the position obtained by reflecting it in a gridline or shifting it parallel to itself an even distance will not affect the difference between the areas. But by performing such operations it is possible to move all 4 corners of the rectangle into the same gridsquare; then the entire interior of the modified rectangle is the same colour. It follows that the original rectangle has area balance 0 iff the modified rectangle has area 0 iff one of its sides has length 0 iff the original rectangle either has a side of even length or has centre on a gridline. By the same ideas, we obtain the additional result that the difference in area is at most the area of 1 gridsquare.
(Let's put the above on a more rigorous footing.) A rectangle in the plane with sides parallel to the axes is completely determined by 2 unordered pairs of real numbers; the x coordinates of the 2 vertical sides, and the y coordinates of the two horizontal sides. I mention this because I wish to work with a slightly different object, which I shall call a pointed rectangle, or prectangle, completely determined by two ordered pairs of reals in the same way. A prectangle may be considered as a rectangle for which one of the corners has been marked as special.
The area of the rectangle given by
We have now built a structure in which the key result
|(1)||dparea((a, b), (c, d)) + dparea((a, b), (d, e)) + dparea((a, b), (e, c)) = 0|
holds because, by definition, this is equivalent to the obvious
An analogous result holds with x- and y-coordinates exchanged.
Now let G be the group of isometries of the real line which are symmetries of the set of even integers. We know that, for g in G,
So by (1),
Let ((a, b), (c, d)) be a prectangle of dparea 0. Without loss of generality, we have a, c in
|0||= dparea((a, b), (c, d))|
|= dparea((a, g(b)), (c, h(d)))|
|= (a - g(b))(c - h(d)).|
So either a = g(b) or c = h(d) as required.
This proof is rather cumbersome in terms of notation but is very simple conceptually. I believe it would be a candidate for a proof without words if I could draw the right diagrams. It may be made shorter with the cost of the loss of a little elegance. For example, prectangles need not be mentioned, but then the key result becomes a little clumsier. One equivalent proof has a certain charm:
As in the proof you give, we may assume that the rectangle has both side lengths less than 2. Now, depending on the location of the rectangle, if it is not entirely contained within a gridsquare, we may either slide it (as in your original proof) or squeeze it (move opposite sides in by the same distance) horizontally and vertically without changing the difference in area. We may continue sliding and squeezing until the rectangle is entirely contained within a single gridsquare. At that point since it contains either no black or no white it must have area 0 and so have one side length equal to 0. Backtracking shows that the original rectangle had either a side of even length or centre on a gridline. A small note; in this proof the original step of making the rectangle have side length at most 2 is unnecessary but it does aid visualisation and furthermore reduces the number of operations to at most one slide followed by one squeeze in each direction.
- Rectangle on a Chessboard: an Introduction
- Rectangle on a Chessboard: Nathan Bowler's Proof
- Integers and Rectangles: Peter Winkler's Proof
- Integers and Rectangles: Two Simple Proofs
- Integers and Rectangles: a Proof by Induction
Copyright © 1996-2018 Alexander Bogomolny