In measure theory, a branch of mathematics, the ham sandwich theorem, also called the Stone–Tukey theorem after Arthur H. Stone and John Tukey, states that given n "objects" in n-dimensional space, it is possible to divide each one in half (according to volume) with a single (n − 1)-dimensional hyperplane. In Mathematics the concept of a measure generalizes notions such as "length" "area" and "volume" (but not all of its applications have to do with Mathematics is the body of Knowledge and Academic discipline that studies such concepts as Quantity, Structure, Space and Arthur Harold Stone ( September 30 1916 &ndash August 6 2000) was a British mathematician born in London, who worked mostly John Wilder Tukey ( June 16, 1915 &ndash July 26, 2000) was an American Statistician. In mathematics the dimension of a Space is roughly defined as the minimum number of Coordinates needed to specify every point within it A hyperplane is a concept in Geometry. It is a higher-dimensional generalization of the concepts of a line in Euclidean plane geometry and a Here the "objects" should be sets of finite measure (or, in fact, just of finite outer measure) for the notion of "dividing the volume in half" to make sense. In Mathematics, a set is called finite if there is a Bijection between the set and some set of the form {1 2. In Mathematics the concept of a measure generalizes notions such as "length" "area" and "volume" (but not all of its applications have to do with In Mathematics, in particular in Measure theory, an outer measure is a function defined on all subsets of a given set with values in the

Naming

The ham sandwich theorem takes its name from the case when n = 3 and the three objects of any shape are a chunk of ham and two chunks of bread — notionally, a sandwich — which can then each be bisected with a single cut (i. Ham is the Thigh and Rump of Pork, cut from the Haunch of a Pig or Boar. Bread is a Staple food prepared by Baking a Dough of Flour and Water. A sandwich is a food item made of two or more slices of Bread with one or more layers of a filling e. , a plane). In two dimensions, the theorem is known as the pancake theorem of having to cut two infinitesimally thin pancakes on a plate each in half with a single cut (i. Pancakes are a type of Flatbread prepared from a sweet batter that is cooked on a hot Griddle or in a Frying pan. e. , a straight line).

The ham sandwich theorem is also sometimes referred to as the "ham and cheese sandwich theorem", again referring to the special case when n = 3 and the three objects are

1. a chunk of ham,
2. a slice of cheese, and
3. two slices of bread (treated as a single disconnected object). Ham is the Thigh and Rump of Pork, cut from the Haunch of a Pig or Boar. Cheese is a Food made from Milk, usually the milk of cows, Buffalo, Goats or sheep, by coagulation. Bread is a Staple food prepared by Baking a Dough of Flour and Water. In Topology and related branches of Mathematics, a connected space is a Topological space which cannot be represented as the disjoint union of

The theorem then states that it is possible to slice the ham and cheese sandwich in half such that each half contains the same amount of bread, cheese, and ham. It is possible to treat the two slices of bread as a single object, because the theorem only requires that the portion on each side of the plane vary continuously as the plane moves through 3-space.

The ham sandwich theorem has no relationship to the "squeeze theorem" (sometimes called the "sandwich theorem"). In Calculus, the squeeze theorem (known as the pinching theorem, the sandwich theorem and sometimes the squeeze lemma) is a Theorem

History

According to Beyer and Zardecki (2004), the earliest known paper about the ham sandwich theorem, specifically the d = 3 case of bisecting three solids with a plane, is by Steinhaus and others (1938). Beyer and Zardecki's paper includes a translation of the 1938 paper. It attributes the posing of the problem to Hugo Steinhaus, and credits Stefan Banach as the first to solve the problem, by a reduction to the Borsuk–Ulam theorem. Władysław Hugo Dionizy Steinhaus ( January 14, 1887 &ndash February 25, 1972) was a Polish Mathematician and Stefan Banach ( Ukrainian: Степан Степанович Банах 1892–1945 was a Polish Mathematician who worked in interwar Poland and in The Borsuk–Ulam theorem states that any Continuous function from an ''n''-sphere into Euclidean ''n''-space maps some pair of Antipodal points The paper poses the problem in two ways: first, formally, as "Is it always possible to bisect three solids, arbitrarily located, with the aid of an appropriate plane?" and second, informally, as "Can we place a piece of ham under a meat cutter so that meat, bone, and fat are cut in halves?" Later, the paper offers a proof of the theorem.

A more modern reference is Stone and Tukey (1942), which is the basis of the name "Stone–Tukey theorem". This paper proves the n-dimensional version of the theorem in a more general setting involving measures. The paper attributes the n = 3 case to Stanisław Marcin Ulam, based on information from a referee; but Beyer & Zardecki (2004) claim that this is incorrect, given Steinhaus's paper, although "Ulam did make a fundamental contribution in proposing" the Borsuk–Ulam theorem. Stanisław Marcin Ulam ( April 13, 1909 &ndash May 13, 1984) was a Polish Mathematician who participated in the Manhattan The Borsuk–Ulam theorem states that any Continuous function from an ''n''-sphere into Euclidean ''n''-space maps some pair of Antipodal points

Reduction to the Borsuk–Ulam theorem

The ham sandwich theorem can be proved as follows using the Borsuk–Ulam theorem. The Borsuk–Ulam theorem states that any Continuous function from an ''n''-sphere into Euclidean ''n''-space maps some pair of Antipodal points This proof follows the one described by Steinhaus and others (1938), attributed there to Stefan Banach, for the n = 3 case. Stefan Banach ( Ukrainian: Степан Степанович Банах 1892–1945 was a Polish Mathematician who worked in interwar Poland and in

Let A₁, A₂, . . . , A_n denote the n objects that we wish to simultaneously bisect. Let S be the unit (n − 1)-sphere in , centered at the origin. In Mathematics, a unit Sphere is the set of points of Distance 1 from a fixed central point where a generalized concept of distance may be used a closed "Globose" redirects here See also Globose nucleus. A sphere (from Greek σφαίρα - sphaira, "globe In Mathematics, the origin of a Euclidean space is a special point, usually denoted by the letter O, used as a fixed point of reference For each point p on the surface of the sphere S, we can define a continuum of oriented hyperplanes perpendicular to the (normal) vector from the origin to p, with the "positive side" of each hyperplane defined as the side pointed to by that vector. In Mathematics, the word continuum has at least two distinct meanings outlined in the sections below A hyperplane is a concept in Geometry. It is a higher-dimensional generalization of the concepts of a line in Euclidean plane geometry and a By the intermediate value theorem, every family of such hyperplanes contains at least one hyperplane that bisects the bounded object A_n: at one extreme translation, no volume of A_n is on the positive side, and at the other extreme translation, all of A_n's volume is on the positive side, so in between there must be a translation that has half of A_n's volume on the positive side. In Mathematical analysis, the intermediate value theorem states that for each value between the upper and lower bounds of the image of a Continuous function If there is more than one such hyperplane in the family, we can pick one canonically by choosing the midpoint of the interval of translations for which A_n is bisected. Thus we obtain, for each point p on the sphere S, a hyperplane π(p) that is perpendicular to the vector from the origin to p and that bisects A_n.

Now we define a function f from the (n − 1)-sphere S to (n − 1)-dimensional Euclidean space as follows:

f(p) = (

volume of A₁ on the positive side of π(p),

volume of A₂ on the positive side of π(p),

. . . ,

volume of A_n−1 on the positive side of π(p)

).

This function f is continuous. In Mathematics, a continuous function is a function for which intuitively small changes in the input result in small changes in the output By the Borsuk–Ulam theorem, there are antipodal points p and q on the sphere S such that f(p) = f(q). The Borsuk–Ulam theorem states that any Continuous function from an ''n''-sphere into Euclidean ''n''-space maps some pair of Antipodal points In Mathematics, the antipodal point of a point on the surface of a sphere is the point which is diametrically opposite it — so situated that a line drawn from the Antipodal points p and q correspond to hyperplanes π(p) and π(q) that are equal except that they have opposite positive sides. Thus, f(p) = f(q) means that the volume of A_i is the same on the positive and negative side of π(p) (or π(q)), for i = 1, 2, . . . , n − 1. Thus, π(p) (or π(q)) is the desired ham sandwich cut that simultaneously bisects the volumes of A₁, A₂, . . . , A_n.

Measure theoretic statement

In measure theory, a more general form of the ham sandwich theorem is due to Stone and Tukey (1942): for any n subsets X₁, X₂, . . . , X_n of any set X with a Carathéodory outer measure, there is a suitably restricted real function , where Sⁿ is the n-sphere, that simultaneously divides each of the n subsets in half with respect to the measure. Constantin Carathéodory (or Constantine Karatheodoris ( Greek: Κωνσταντίνος Καραθεοδωρή ( September 13, 1873 &ndash February In Mathematics, in particular in Measure theory, an outer measure is a function defined on all subsets of a given set with values in the The Mathematical concept of a function expresses dependence between two quantities one of which is given (the independent variable, argument of the function "Globose" redirects here See also Globose nucleus. A sphere (from Greek σφαίρα - sphaira, "globe

Discrete and computational geometry versions

A ham-sandwich cut of eight red points and seven blue points in the plane.

In discrete geometry and computational geometry, the ham sandwich theorem usually refers to the special case in which each of the sets being divided is a finite set of points. Discrete geometry or combinatorial geometry may be loosely defined as study of geometrical objects and properties that are discrete or Combinatorial, either Computational geometry is a branch of Computer science devoted to the study of algorithms which can be stated in terms of Geometry. In Mathematics, a set is called finite if there is a Bijection between the set and some set of the form {1 2. In Geometry, Topology and related branches of mathematics a spatial point describes a specific point within a given space that consists of neither Volume Here the relevant measure is the counting measure, which simply counts the number of points on either side of the hyperplane. In Mathematics, the counting measure is an intuitive way to put a measure on any set: the "size" of a Subset is taken to be the number In two dimensions, the theorem can be stated as follows:

For a finite set of points in the plane, each colored "red" or "blue", there is a line that simultaneously bisects the red points and bisects the blue points, that is, the number of red points on either side of the line is equal and the number of blue points on either side of the line is equal.

There is an exceptional case when a point lies on the line. In this situation, we count the point as being on either both sides of the line or on neither side of line. This exceptional case is actually required for the theorem to hold, in case the number of red points or the number of blue is odd, and still each set must be bisected.

In computational geometry, this ham sandwich theorem leads to a computational problem, the ham sandwich problem. In two dimensions, the problem is this: given a finite set of n points in the plane, each colored "red" or "blue", find a ham sandwich cut for them. First, Nimrod Megiddo described an algorithm for the special, separated case. Here all red points are on one side of some line and all blue points are on the other side, a situation where there is a unique ham sandwich cut, which Megiddo could find in linear time. Later, Edelsbrunner and Waupotitsch gave an algorithm for the general two-dimensional case; the running time of their algorithm is O(n log(n)). Finally, Lo and Steiger (1990) found an optimal O(n)-time algorithm. In mathematics big O notation (so called because it uses the symbol O) describes the limiting behavior of a function for very small or very large arguments In Mathematics, Computing, Linguistics and related subjects an algorithm is a sequence of finite instructions often used for Calculation It was extended to higher dimension by Lo, Matousek, and Steiger (1994). Given d sets of points in general position in d-dimensional space, the algorithm computes a (d-1)-dimensional hyperplane that has equal numbers of points of each of the sets in each of its half-spaces - i. e, a ham-sandwich cut for the given points.

"Leftovers"

Byrnes, Cairns, and Jessup (2001) showed that it is not always possible to position the hyperplane correctly just by cutting through the objects' centers of gravity.

References

• Beyer, W. A. & Zardecki, Andrew (Jan. 2004). "The early history of the ham sandwich theorem". American Mathematical Monthly 111 (1), 58–61. The American Mathematical Monthly ( is a mathematical journal founded by Benjamin Finkel in 1894.

• Lo, Chi-Yuan & Steiger, W. L. (1990). "An optimal time algorithm for ham-sandwich cuts in the plane". In Proceedings of the Second Canadian Conference on Computational Geometry, pp. 5–9.

• Lo, Chi-Yuan; Matoušek, Jirí; & Steiger, William L. (1994). "Algorithms for Ham-Sandwich Cuts". In Discrete and Computational Geometry 11, 433–452.

• Steinhaus, Hugo & others (1938). "A note on the ham sandwich theorem". Mathesis Polska(Latin for "Polish Mathematics") 9, 26–28.

• Stone, A. H. & Tukey, J. W. (1942). "Generalized "sandwich" theorems". Duke Mathematical Journal 9, 356–359. Duke Mathematical Journal is an American mathematical research journal published by Duke University Press.

• Byrnes, G. B. ; Cairns, G. ; & Jessup, B. (2001). "Left-overs from the Ham-Sandwich Theorem". American Mathematical Monthly 108 246–9

• Eric W. Weisstein, Ham Sandwich Theorem at MathWorld. Eric W Weisstein (born March 18, 1969, in Bloomington Indiana) is an Encyclopedist who created and maintains MathWorld MathWorld is an online Mathematics reference work created and largely written by Eric W

External links

• ham sandwich theorem on the Earliest known uses of some of the words of mathematics