Computing Applications Last byte

Puzzled: Variations on the Ham Sandwich Theorum

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.
  1. Article
  2. Author
  3. Footnotes

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.

Back to Top

Back to Top

Join the Discussion (0)

Become a Member or Sign In to Post a Comment

The Latest from CACM

Shape the Future of Computing

ACM encourages its members to take a direct hand in shaping the future of the association. There are more ways than ever to get involved.

Get Involved

Communications of the ACM (CACM) is now a fully Open Access publication.

By opening CACM to the world, we hope to increase engagement among the broader computer science community and encourage non-members to discover the rich resources ACM has to offer.

Learn More