|
|
|
|
|Store|
|
|
|
|
CTK Exchange
sfwc
Member since Jun-19-03
|
Jun-28-05, 03:26 PM (EST) |
|
"Rectangles on chessboards"
|
At the page about rectangles on chessboards the claim 'A rectangle with sides parallel to the sides of a chessboard covers equal areas of the two colors if only if one of its sides is twice the side of a chessboard square' is made. A faulty proof is given (the problem is when the rectangle slides: this is not always possible). The proof must be faulty due to the fact that any rectangle with its centre on a gridline must also contain equal areas of black and white by symmetry. 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 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. Fortunately, the proof at the end of the page may be saved; it is merely necessary to add the phrase 'in such a way that its centre does not lie on a gridline' at the end of the first sentence. Thankyou
sfwc <>< |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
alexb
Charter Member
1569 posts |
Jun-28-05, 05:39 PM (EST) |
|
1. "RE: Rectangles on chessboards"
In response to message #0
|
>The proof must be faulty Yes, indeed. The diagram with the two moves - one down, one right - it may haooen that one of the moves does not produce the desired result. For example, if the width of the rectangle is less than 1/2, the move to the right can't preserve the color balance. Many thanks for that. Must think of what I want to preserve and what to remove.
|
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
sfwc
Member since Jun-19-03
|
Jun-29-05, 05:11 PM (EST) |
|
2. "A small correction and some embellishment of the proof."
In response to message #0
|
At the same page, where an update has now been made, there is a new problem. The claim 'In all cases, 0 < x1, x2, x1 + x2 < 1 and 0 < y1, y2, y1 + y2 < 1' is made. It is false in the second two cases. In particular, in case 2 we may have x1 + x2 >= 1, and in case 3 either x1 + x2 >= 1 or y1 + y2 >= 1. Of course, this doesn't in any way disrupt the main flow of your argument. I would like also to take this opportunity to clarify the proof provided in the second paragraph of my original post. 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 ({a, b}, {c, d}) is |a-b|*|c-d|; the parea of a prectangle given by ((a, b), (c, d)) is defined to be (a-b)(c-d). Note that whilst this a natural definition of parea, it may be negative. Now consider a prectangle P = ((a, b), (c, d)) on a chessboard. We shall define the parea difference, or paread, of P to be the parea of black enclosed by P minus the parea of white enclosed by P (these pareas are to sum to the parea of P, so it is natural to define them to be the areas multiplied by the sign of the parea of P). We have now built a structure in which the key result paread((a, b), (c, d)) + paread((a, b), (d, e)) + paread((a, b), (e, c)) = 0 holds(probably best visualised with a diagram). 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 ((a, g(a)), (c, d)) has paread 0. So by the result above, paread((a, b), (c, d)) = paread((a, g(b)), (c, d)). Let ((a, b), (c, d)) be a prectangle of paread 0. w.l.o.g. we have a, c in <0, 1). Let n be the nearest even integer to b. Let g in G take n to 0 in such a way that g(c) >= 0. So g(c) is in [0, 1>. Similarly we may choose h in G with h(d) in <0, 1>. By the above result, 0 = paread((a, b), (c, d)) = paread((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. Thankyou sfwc <>< |
|
Alert | IP |
Printer-friendly page |
Reply |
Reply With Quote | Top |
|
|
You may be curious to have a look at the old CTK Exchange archive. Please do not post there.
|Front page|
|Contents|
Copyright © 1996-2018 Alexander Bogomolny
|
|