Communications of the ACM
Last byte
Puzzled: Solutions and Sources
The Intermediate Value Theorem says that if you go continuously from one real number to another, you must pass through all the real numbers in between. You can use it to prove the Ham Sandwich Theorem; here's how it can be used to solve Puzzles 1 and 2:
1. Hiking the Cascade Range.
Solution. Puzzle 1 asked us to prove that the programmers who spent Saturday climbing and Sunday descending Mt. Baker were, at some time of day, at exactly the same altitude on both days.
It's easily done. For any time t, let f(t) be the progammers' altitude on Sunday minus their altitude on Saturday; f(t) starts off positive in the morning and ends up negative at night, so at some point must be 0.
An equivalent, and perhaps more intuitive, way to see this is to imagine that the programmers have twins who were instructed to climb the mountain on Sunday exactly as the programmers climbed it the day before. Then, even if their paths up and down were different, there is some point at which the programmers and their twins must pass one another in altitude.
2. Inscribing a Lake in a Square.
Solution. Puzzle 2 asked us to show that, given any closed curve in the plane, there is a square containing the curve, all four sides of which touch the curve. The idea of the proof is both simple and elegant. Start with a vertical line drawn somewhere west of the curve. Gradually shift the line eastward until it just touches the curve. Repeat with a second line, drawn east of the curve and moving gradually west, so we now have another vertical line touching the curve on its east side. Now bring a horizontal line down from the north until it touches the curve and another from the south, thus inscribing the curve in a rectangle.
But what we want is not merely a rectangle but a square. Suppose the rectangle is taller than it is wide (as it would be in, say, Lake Champlain). Now slowly rotate the four lines together clockwise, keeping all four outside but still touching the curve. After 90 degrees of rotation, the picture is exactly the same as before, only now, the previously long vertical lines of the rectangle are the short horizontal sides.
At some point in the rotation process, the original vertical lines and horizontal lines were all the same lengthand, at exactly that point, the curve was inscribed in a square.
3. Curves Containing the Corners of a Square.
Solution. The third puzzle was (as usual) unsolved, frustrating geometers for more than a century. For a discussion see http://www.ics.uci.edu/~eppstein/junkyard/jordan-square.html, including reference to an article by mathematician Walter Stromquist ("Inscribed Squares and Square-like Quadrilaterals in Closed Curves," Mathematika 36, 2 (1989), 187197) in which he proved the conjecture for smooth curves. See also Stan Wagon's and Victor Klee's book Old and New Unsolved Problems in Plane Geometry and Number Theory (Mathematical Association of America, 1991).
Footnotes
All readers are encouraged to submit prospective puzzles for future columns to [email protected].
DOI: http://doi.acm.org/10.1145/1743546.1743575
©2010 ACM 0001-0782/10/0600 $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