Sign In

Communications of the ACM

Last byte

Puzzled: Variations on the Ham Sandwich Theorum


View as: Print Mobile App ACM Digital Library Full Text (PDF) In the Digital Edition Share: Send by email Share on reddit Share on StumbleUpon Share on Hacker News Share on Tweeter Share on Facebook
sandwich

Credit: iStockPhoto.com

The solutions of the first two puzzlesand maybe the third as wellmake 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. Bakerall 10,781 feet of itreaching 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

Author

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.

Back to Top

Footnotes

All readers are encouraged to submit prospective puzzles for future columns to puzzled@cacm.acm.org.

DOI: http://doi.acm.org/10.1145/1735223.1735250


©2010 ACM  0001-0782/10/0500  $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.


Comments


Valentin Goranko

I think the truth of 2 and 3 may depend on how you define (closed) curve, so please give your precise definitions. For instance, there are unbounded, space filling curves for which 2 would not hold, and one can make such a curve 'closed' by self-crossing. So, maybe 2 should be restricted to simple (Jordan) curves?


Kenneth Hertz

A continuous tangent should be sufficient. Are weaker conditions sufficient ?


Displaying all 2 comments