last byte

DOI: 10.1145/1743546.1743575
Peter;Winkler
Puzzled
solutions and sources

Last month (May 2010, p. 120) we posted a trio of brainteasers, including
one as yet unsolved, concerning variations on the Ham Sandwich Theorem.

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 length— and, 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), 187–197) 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).

 

All readers are encouraged to submit prospective puzzles for future columns to [e-mail].

Peter Winkler ( [e-mail]) is Professor of Mathematics and of Computer Science and Albert bradley Third Century Professor in the Sciences at Dartmouth College, Hanover, nH.