last byte
DOI: 10.1145/1735223.1735250
Peter;Winkler
Puzzled
Variations on the
ham sandwich theorem
Welcome to three new puzzles. Solutions to the first two will be
published next month; the third is (as yet) unsolved. In each, the issue
is how your intuition matches up with the mathematics.
The solutions of the first two puzzles—and maybe the third as
well—make good use of the Intermediate Value Theorem, which
says if you go continuously from one real number to another, you
must pass through all the real numbers in between. The most
famous application is perhaps the Ham Sandwich Theorem,
which says, given any ham-and-cheese sandwich, no matter how
sloppily made, there is a planar cut dividing the ham, cheese,
and bread, each into two equal-size portions.
The two solved problems are perhaps a bit easier than the
Ham Sandwich Theorem but still tricky and rewarding enough
to be worth your attention and effort.
1.A pair of intrepid computer programmers
spend a weekend hiking
the Cascade Range in
Washington. On Saturday
morning they begin an ascent
of Mt. Baker—all 10,781 feet
of it—reaching the summit
by nightfall. They spend the
night there and start down
the mountain the following
morning, reaching the
bottom at dusk on Tuesday.
Prove that at some
precise time of day, these
programmers were at exactly
the same altitude on Sunday
as they were on Saturday.
2.Prove that Lake Champlain can be
inscribed in a square. More
precisely, show that, given
any closed curve in the plane,
there is a square containing
the curve all four sides of
which touch the curve.
A corner counts for both
incident sides.
3.Be the first person ever to prove (or disprove)
that every closed curve in the
plane contains the corners of
some square.
All readers are encouraged to submit prospective puzzles for future columns to puzzled@cacm.acm.org.
Peter Winkler ( puzzled@cacm.acm.org) is Professor of mathematics and of computer science and albert bradley
third century Professor in the sciences at dartmouth college, hanover, nh.