Communications of the ACM
Last byte
Puzzled: Solutions and Sources
Solution. We were given a large rectangle in the plane, partitioned into a finite number of smaller rectangles, each with either integer width or integer height. Our mission was to prove the big rectangle also has integer width or height.
The puzzle was the subject of a famous article "Fourteen Proofs of a Result About Tiling a Rectangle" by Stan Wagon of Macalester College, St. Paul, MN, in The American Mathematical Monthly 94 (1987). Here, we provide one of several solutions not found among Wagon's 14. Letting epsilon be less than the smallest tolerance in the partition, color each small rectangle of integral width green, except for a red horizontal strip of width epsilon across the top and another across the bottom. Next, color each remaining small rectangle red, except for a green vertical strip of width epsilon along the left side and another along the right side. Now place the lower-left point of the big rectangle at the origin.
There is either a green path from the left side of the big rectangle to the right side or a red path from the bottom to the top. Suppose the former. Every time the green path crosses a vertical border of the partition, it is at an integral coordinate. The big rectangle thus has integral width. Similarly, a red path from bottom to top forces integral height.
2. Blocking the Enemy.
Solution. Recall we were in a large rectangular room with mirrored walls, while elsewhere in the same room was our mortal enemy, armed with a laser gun. Our only defense was our ability to summon graduate students to stand at designated spots in the room blocking all possible shots by the enemy. How many students would we need? We assume for the purposes of the problem that we, our enemy, and the students are all thin enough to be considered points. So, for example, if we had continuum many students, we could place them around us in a circle (with the enemy outside). But we can do better.
This wonderful puzzle seems to have begun life at the Leningrad Mathematics Olympiad of 1990 and has since spurred some serious mathematics by, among others, Benjamin Schmidt and Jean-Francois Lafont of The Ohio State University and Eugene Gutkin of the University of Southern California.
First, view the room as a rectangle in the plane, with us at P and the enemy at Q. We can now tile the plane with copies of the room by repeatedly reflecting the room about its walls, with each copy containing a new copy of our enemy. Every possible shot by the enemy can be represented on this image by a straight line from some copy of the point Q to P. Every time such a line crosses a boundary between rectangles, the real laser beam bounces off a wall. This observation already tells us there is only a countably infinite number of ways for the enemy to shoot us, so a countable number of students is enough.
But the shots (once folded into the original room) intersect one another frequently, and, conceivably, a well-placed student could block infinitely many shots. Indeed, it takes only 16 students to block every possible shot at exactly its halfway point. To see how it works, "trace" a copy of the plane tiling onto a piece of paper, pin it to the plane at our position P, and shrink the paper copy by a factor of two vertically and horizontally. The many copies of Q on the shrunk copy will be the students' positions, serving our purpose because each copy of Q on the original tiling appears halfway between it and us on the shrunk copy. There are infinitely many such points, but all are copies of a set of 16 points in the original room.
3. Covering a Big Rectangle.
Unsolved. The third problem is open. No one can prove we can even get the small rectangles to cover at least 1% of the big rectangle. Another mystery is its origin. I heard it 20 years ago from Bill Pulleyblank (now professor of operations research at the U.S. Military Academy, West Point, NY), though he doesn't recall where he got it.
Footnotes
All readers are encouraged to submit prospective puzzles for future columns to [email protected].
DOI: http://doi.acm.org/10.1145/1859204.1859232
©2010 ACM 0001-0782/10/1200 $10.00
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. To copy otherwise, to republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee.
The Digital Library is published by the Association for Computing Machinery. Copyright © 2010 ACM, Inc.
No entries found