(Image credit: Flicker user stephanie vacher)
by Marc Abrahams, Improbable Research staffThe Ham Sandwich Theorem has been a treat and a spur to mathematicians for more than half a century. It first cropped up in a branch of mathematics called algebraic topology. The theorem describes a particular truth about certain shapes. Most published papers on the topic make a hash of explaining it to anyone who is not an algebraic topologist. But the authors of a 2001 paper called “Leftovers from the Ham Sandwich Theorem” wrapped up an important little leftover: they put the idea into clear language.
“Leftovers from the Ham Sandwich Theorem,” Graham Byrnes, Grant Cairns, and Barry Jessup, The American Mathematical Monthly, vol. 108, no. 3, March 2001, pp. 246-9.
The authors are at La Trobe University, Melbourne, Australia, and University of Ottawa, Ottawa, Canada. The Ham Sandwich Theorem, they wrote, “rescues the careless sandwich maker by guaranteeing that it is always possible to slice the sandwich with one cut so that the ham and both slices of bread are each divided into equal halves, no matter how haphazardly the ingredients are arranged.”
For a while, most ham sandwich theorizing dealt with simple cases. A paper called “Computing a Ham-Sandwich Cut in Two Dimensions,” published in 1986, is typical.
[caption id="attachment_55198" align="aligncenter" width="339" caption="Detail from the Edelsbrunner/Waupotitsch study “Computing a Ham-Sandwich Cut in Two Dimensions.”"][/caption]
“Computing a Ham-Sandwich Cut in Two Dimensions,” H. Edelsbrunner and R. Waupotitsch, Journal of Symbolic Computation, vol. 2, no. 2, June 1986, pp. 171–8.
It considered only ham sandwiches that had been flattened flatter than even the chintziest cook would dare devise. Mathematicians often do things this way, first considering the extreme cases, digesting those thoroughly, and only then moving on to more substantial versions. Indeed, the “Computing a Ham-Sandwich Cut in Two Dimensions” paper itself contains a section called “Getting Rid of Degenerate Cases”.
People did solve the mystery of slicing a thick ham sandwich. And inevitably, they developed a hunger for more substantial problems.
In 1990, Yugoslavian theorists wrote in the Bulletin of the London Mathematical Society about “An Extension of the Ham Sandwich Theorem.”
“An Extension of the Ham Sandwich Theorem”, Rade T. Živaljevi? and Sinisa T. Vre?ica, Bulletin of the London Mathematical Society, vol. 22, no. 2, 1990, pp. 183–6.
The authors are at Mathematics Institute Knez Mihailova and at Faculty of Mathematics Studentski, both in Beograd, Yugoslavia.
The Ham Sandwich Theorem Revisited…
Partly from nostalgia, partly with an eye to the future, these two mathematicians paused in 1992 to take a refreshing look back at the ham sandwich question:
“The Ham Sandwich Theorem Revisited,” Sinisa T. Vre?ica and Rade T. Živaljevi?, Israel Journal of Mathematics, vol. 78, no. 1, February 1992, pp. 21–32.
(Image credit: Flickr user jeffreyw)
Elsewhere in 1992, a theorist at Yaroslav State University in Russia published a paper called “A Generalization of the Ham Sandwich Theorem.”
“A Generalization of the Ham Sandwich Theorem,” V.L. Dol’nikov and P.G. Demidov, Matematicheskie Zametki [Mathematical Notes], vol. 52, no. 2, 1992, pp. 27–37.
The authors explain:
[We] consider a group of problems connected with the “three-layered sandwich problem,” posed by Ulam, and the Neumann-Rado theorem on division of measures. In the ham sandwich problem it is required to cut a ham sandwich of bread with butter and cheese such that each part contains exactly half of each of the three ingredients.
That same year, a team of hungry American, Czech, and German mathematicians assembled a master collection of recipes for slicing ham sandwiches. Mathematicians almost never use the word “recipe”, so they called their paper “Algorithms for Ham-Sandwich Cuts.”
“Algorithms for Ham-Sandwich Cuts,” Chi-Yuan Lo, J. Matoušek, and W. Steiger, Discrete and Computational Geometry, vol. 11, no. 1, December 1994, pp. 433–52.
Research then moved on to exotic, distantly-related questions, exemplified by a 1998 monograph called “Green Eggs and Ham.”
“Green Eggs and Ham,” M.J. Kaiser and S. Hossaien Cheraghi, Mathematical and Computer Modeling, vol. 28, no. 1, 1998, pp. 91–99.
The authors, at Wichita State University, Kansas, U.S.A., explain:
A dish of ham and eggs is required to be divided equally by a single straight knife cut. A constructive solution procedure is described through the introduction of a balance functional and a geometric optimization problem. The two- and three-, dimensional cases are illustrated by example.
Whence the Ham Sandwich Theorem?
And who started this? A 2004 paper called “The Early History of the Ham Sandwich Theorem” took care of another lingering leftover: it identified the inventor. Mathematico- historians W.A. Beyer and Andrew Zardecki of Los Alamos National Laboratory in New Mexico, U.S.A., say that it was a Jewish theorist who introduced the ham sandwich into mathematical theory. Beye and Zardecki trace the theorem back to a 1945 paper by the Polish mathematician Hugo Steinhaus that “represents work Steinhaus did in Poland on the ham sandwich problem in World War II while hiding out with a Polish farm family.”
“The Early History of the Ham Sandwich Theorem,”
W.A. Beyer and Andrew Zardecki, The American Mathematical Monthly, vol. 111, no. 1, January 2004, pp. 58–61.
The authors say:
The following theorem is the well-known ham sandwich theorem: for any three given sets in Euclidean space, each of finite outer Lebesgue measure, there exists a plane that bisects all three sets, i.e., separates each of the given sets into two sets of equal measure. The early history of this result seems not to be well known. Stone and Tukey attribute the theorem to Ulam. They say they got the information from a referee. Is this correct? The problem appears in The Scottish Book as problem 123. The problem is posed by Steinhaus. A reference is made to the pre-World War II journal Mathesis Polska (Latin for “Polish Mathematics”). This journal is not easy to locate...
The Miraculous Years 2009 and 2010
The years 2009 and 2010 were anni mirabili for Ham Sandwich Theorem research. Consider just a few of the papers published during that time.
“Dynamic Ham-Sandwich Cuts in the Plane,” Timothy G. Abbott, Michael A. Burr, Timothy M. Chan, Erik D. Demaine, Martin L. Demaine, John Hugg, Daniel Kane, Stefan Langerman, Jelani Nelson, Eynat Rafalin, Kathryn Seyboth, and Vincent Yeung, Computational Geometry, vol. 42, no. 5, July 2009, pp. 419–28. “Ham Sandwich with Mayo: A Stronger Conclusion to the Classical Ham Sandwich Theorem,” John H. Elton and Theodore P. Hill, arXiv:0901.2589v2, 2009.
The authors of the latter paper, at Georgia Institute of Technology, Georgia, U.S.A., report:
The conclusion of the classical ham sandwich theorem of Banach and Steinhaus may be strengthened: there always exists a common bisecting hyperplane that touches each of the sets, that is, intersects the closure of each set. Hence, if the knife is smeared with mayonnaise, a cut can always be made so that it will not only simultaneously bisect each of the ingredients, but it will also spread mayonnaise on each. A discrete analog of this theorem says that n finite nonempty sets in n-dimensional Euclidean space can always be simultaneously bisected by a single hyperplane that contains at least one point in each set.
Other discussions followed:
“Generalized Ham-Sandwich Cuts,” William Steiger and Jihui Zhao, Discrete and Computational Geometry, vol. 44, no. 3, 2010, 535-45. “Uneven Splitting of Ham Sandwiches,” Felix Breuer, Discrete and Computational Geometry, vol. 43, no. 4, 2010, pp. 876–92.
From the Ham Sandwich to the Pizza Pie
The future, which of course is not truly predictable (according to most current theories, anyway), appears to include the continued diversification of Ham Sandwich theorizing. We conclude with a mention of a possible harbinger of things to come:
“From the Ham Sandwich to the Pizza Pie: A Simultaneous Z m Equipartition of Complex Measures,” Steven Simon, arXiv:1006.4614v8, 2010.
Acknowledgement
Thanks to Stanley Eigen for bringing the Ham Sandwich Theorem to our attention.
_____________________
This article is republished with permission from the May-June 2011 issue of the Annals of Improbable Research. You can download or purchase back issues of the magazine, or subscribe to receive future issues. Or get a subscription for someone as a gift!Visit their website for more research that makes people LAUGH and then THINK.