Integers and Rectangles

It's a desirable feature of a problem when it could be classified as belonging to one of common branches of mathematics: geometry, algebra, calculus. Classifiable problems could be included in a textbook and discussed in class. Curriculum developers would know when students are prepared to tackle such problems.

Some problems, many of which are instructive and exciting, defy classification. One such problem has been discussed in 1987 by Stan Wagon in the American Mathematical Monthly (also, in [Which Way Did The Bicycle Go?, #14].

Is it geometry, algebra, arithmetic ...? Wagon gave fourteen essentially different proofs that ranged from elementary to those that used integrals, graph theory, or Sperner's lemma.

The applet below helps with understanding the problem and its solution (apparently #15) by Peter Winkler.

Assume a big rectangle is tiled with small ones, each of which has an integer side. In the applet the ones with integer width are colored green and those with integer height red: H- and V-tiles, respectively. In case where both dimensions are integer, the color assignment is arbitrary and can be changed be clicking twice on the rectangle. (Clicking twice is not the same as a double click.)

The applet allows one to add or remove rectangles, select one at a time, and change dimensions of the selected rectangle. All rectangles are draggable.

The start up configuration is taken from Winkler's book. So, the H-tiles are green, the V-tiles are red. The big rectangle is thus split into two regions: green and red, which we are going to modify just a little. The gist of the proof is to decorate the tiles with narrow strips of the opposite color. The strips are drawn along the integer edges. To proceed with the proof, imagine the standard x- and y-axes and assume that the big rectangle is located in the first quadrant with the lower left corner at the origin. Then one of the two: either there is a path (curve) inside the green regions that connects the left and right edges of the big rectangle, or there is a path (curve) inside the red region that connects its top and bottom edges.

Why? The proof of this statement is similar to the one used to establish a property of the game of Hex. The similarity of the two proofs has in fact confused me, so that I needed help to grasp Winkler's proof. Peter graciously held my hand and patiently explained the difference between the two. The difference is that in the present case the path we are after is just a line - a curve - that may cross the boundaries of the small rectangles even at their corners.

If the left edge of the ambient rectangle is entirely red, we are done. Otherwise, consider the maximal green region that abuts the left edge of the rectangle. By region here I mean the union of all green rectangles that share at least one point. If this region reaches as far as the right border, we are again done. Otherwise, its boundary is shared by a red region that stretches from top to bottom. (Unlike in the game of Hex, there may be paths of both kinds.)

The best way to see how the proof works is to check the "Decorate" box and uncheck the "Show borders" box.

What if applet does not run?

But what do we do with such a path? a path that lies entirely in the green rectangles and, perhaps, the rectangles' corners crosses vertical edges at integer points. The one inside the red rectangles crosses the horizontal edge at integer point. Thus, either leads from an integer edge to an integer edge. So the proof is complete.

Now, what was the purpose of introducing those strips on the sides of the rectangles? Their main role was to prevent unwanted paths, such as, for example, a path within the green region from bottom to top of the ambient rectangle.

(We also have discussed two other solutions to this problem. One is completely elementary, the other using the math induction.)

References

1. J. Konhauser, D. Velleman, S. Wagon, Which Way Did the Bicycle Go?, MAA, 1996
2. S. Wagon, Fourteen Proofs of a Result About Tiling a Rectangle, Am Math Monthly, Vol. 94, No. 7 (Aug. - Sept., 1987), 601-617.
3. P. Winkler, Mathematical Puzzles: A Connoisseur's Collection, A K Peters, 2004, pp.6-7

Integer Rectangles

• 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

|Contact| |Front page| |Contents| |Algebra|

Copyright © 1996-2018 Alexander Bogomolny