Talk:Ham sandwich theorem

Major hole in the proof of "Two-dimensional variant: proof using a rotating-knife"

The two-dimensional proof seems to have a fairly large hole in its logic:

• At the first step, we determine an angle and a corresponding translation offset for that angle, such that pancake #1 will be bisected. This is in fact a function--let's call it $t(\alpha )=x$, where $x$ is the translation offset for the line with rotation $\alpha$.

• In step two, we run through all the angles 0-180 ("every angle $\alpha \in [0,180^{\circ }]$") and use the intermediate value theorem to conclude that there is some angle that bisects pancake #2. That is our angle and we're done.

So here is the problem: In step two, we can't just take a line through the origin and rotate it continuously through angles 0-180 degrees. At step one, each rotation angle ALSO had a translation amount--our $t(\alpha )$. So as you work your way from $\alpha =0$ to $\alpha =180$ you have to rotate the AND also apply the relevant translation $t(\alpha )$ to the line.

And here is the problem: We haven't shown that $t(\alpha )$ is continuous. If $t(\alpha )$ is not continuous, then we cannot apply the intermediate value theorem.

Even though we are changing $\alpha$ continuously, $t(\alpha )$ might have some *very* significant discontinuities and if it does, $p(\alpha )$ is going to be discontinuous as well.

In fact, in some situations, $t(\alpha )$ is not continuous at all. Here is one example:

• Pancake #1 consists of union of two unit discs, one centered at (100,0) and the other centered at (200,0). So for any line oriented within, say, 45 degrees of vertical, you can choose $t(\alpha )$ to be anything between, say, 102 and 198 and it will split pancake #1 very nicely into two equal parts. So in this very large range, $t(\alpha )$ is not guaranteed to be continuous at all.

Perhaps $t(\alpha )$ can be constructed so as to be continuous. But if so, a construction must be given for cases such as this, an argument must be made that it can be done for every such pancake, and so on. It can't just be assumed to be continuous.

The typical hypothesis for the ham sandwich theorem is something like "Given n compact sets in $\mathbb {R} ^{n}$". There is no requirement that the "pancakes" be connected. (The example above takes advantage of the possibility that pancakes could be split into two equal & separated parts.) But even if the pancakes were required to be compact and connected, you still would have to make some sort of argument that function $t$ is continuous.

Obviously, the theorem is true so there must be some way to fix it up. But I can't see a simple way at all. Can anyone?

At minimum, the article should state that there must be a proof that $t$ is continuous but it is beyond the scope of this article or such.

Bhugh (talk) 06:19, 4 April 2019 (UTC)

 Done Your objection to the given proof was correct; the proof is now fixed. AxelBoldt (talk) 16:46, 19 January 2022 (UTC)

And, the same issue applies to the n-dimensional variant: proof using the Borsuk–Ulam theorem

In this proof, there is the flat statement, "This function f is continuous." In a typical more rigorous proof (e.g. Brian Libgober) it takes maybe a page of dense argument to establish this. In Libgober it is half of page 14 and all of page 15.

We don't need to duplicate that kind of argument here but we can at least acknowledge that an argument is required rather than simply stating the conclusion baldly--as though it is either easy or obvious.

Bhugh (talk) 06:19, 4 April 2019 (UTC)

 Done AxelBoldt (talk) 16:46, 19 January 2022 (UTC)

No butter?

What, no butter? I heard it as bread/ham/butter.

Charles Matthews 20:23, 4 Jun 2004 (UTC)

I heard it as bread/ham/cheese, same shit, but it really makes more sense, since it also conveys the fact that the objects need not be separated (ie. we cannot separate the 2 slices of bread from the ham/cheese (or butter) with a hyperplane) - at least after the sandwich has been put together and ready for eating anyways =] 216.8.167.246 (talk) 19:31, 10 June 2008 (UTC)

I'd always assumed that the 'ham' was the bisecting line/plane itself. The idea being that you cut each piece of bread into two equal slices, and then insert the ham. -- Smjg 15:15, 5 Jul 2004 (UTC)

Well, I suppose there is a planet somewhere with sandwiches made of three slices of bread ... Charles Matthews 15:24, 5 Jul 2004 (UTC)

This so desperately needs a picture. -- Cyrius|✎ 08:39, 10 August 2005 (UTC)

So the theory states that it is possible to cut things in half? No shit, Sherlock. W guice 13:49, 14 April 2006 (UTC)

You are quite correct that the 1-dimensional variant of the theorem is trivial. That is the only situation where you are simply cutting one thing in half.

In every other variant proven here, you're cutting multiple things exactly in half, with exactly one cut. Multiple things means--2, 4, 100, thousands, millions, whatever. And keep in mind that each of these "things" is not just a nice neat circle, but can be just about any bizarre irregular shape you can draw. Cut them ALL in half with exactly one cut.

*There* is the trick. Bhugh (talk) 06:26, 4 April 2019 (UTC)

Given \binom{k+n}{n}-1 measures in an n-dimensional space, there exists an algebraic surface of degree k which bisects them all.

But has it been proven that there exists an algebraic surface to bind them? 98.222.199.14 (talk) 22:30, 3 April 2016 (UTC)

Sandwich, kent

There seems to be a ham street in the Kent town of Sandwich. I wonder if it bisects it? [1]

Ham and Sandwich are separate towns in Kent. The signpost nearby reads Ham

                                                                       Sandwich

Try this link: http://www.flickr.com/photos/11373869@N00/85970476/

Proof of discrete case

I have cut the following part from the page since it contains a false proof of the discrete case. The proof could possibly be transformed into a proof of the continuous case (the opposite of discrete) and inserted back:

The discrete two-dimensional form of the ham-sandwich theorem can be proved directly using continuity as follows.

First we show that, for every angle θ, there is an oriented line of angle θ that bisects the red set of points. To see this, just slide an oriented line of angle θ perpendicularly; at one extreme, all the red points are on the left side of the line, and at the other extreme, all the red points are on the right side of the line, so by continuity there is a position in between where they are equal. More precisely, we can consider the continuous function f mapping the perpendicular offset of the line to the difference between the number of red points on the left and the number of red points on the right; at one extreme, f is r (the number of red points), and at the other extreme f is −r, so by the intermediate value theorem, somewhere in between, f must be zero, corresponding to a red bisector.

Second we argue the existence of a red bisector that is also a blue bisector. Look at the red bisector of angle 0 obtained from the previous step. This line has some number b₁ of blue points on its left, and some number b₂ of blue points on its right. Now consider a red bisector of angle 180°, namely, the reverse of the previous line. This line has b₂ blue points on its left and b₁ points on its right. If we define g(θ) to be the difference between the number of blue points on the left and right of the red bisector of angle θ, then g(0) = b₁ − b₂ and g(180°) = b₂ − b₁. By the intermediate value theorem, there must be an angle θ for which g(θ) = 0, corresponding to a simultaneous red and blue bisector. (Here we omit the proof that g is in fact continuous.)

Here f is not continuous in the discrete case: it 'jumps' at every point. In particular, if θ is vertical and we have one point with x-coordinate 0, two points with x-coordinate 1 and two point with x-coordinate 2, then any vertical line not going through the leftmost point has an even number of points on one side and an odd number of points on the other side. The line through the leftmost point has more points on the right hand side than on the left.

Marco Streng 18:09, 20 August 2007 (UTC)

The usual technique for handling this complication is to approximate the discrete distribution by a sufficiently similar continuous distribution (e.g. one that assigns uniform weight to a sufficiently small disk around each discrete point), apply the proof above for this continuous case, and then argue that any solution for the continuous approximation also solves the discrete case. One could also use a similar idea based on the fact that the function takes integer values and changes by one at each step. But I agree that without some such argument this is not a good enough proof for the discrete case. —David Eppstein 20:05, 20 August 2007 (UTC)

Continuum

• Citation: 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, [...]
  • Why is there a continuum of oriented hyperplanes? For example in R3, with a 2-sphere, I can only find one unique hyperplane (that is, a plane touching the unit sphere at point p). Thanks for any corrections to my misconception. --Abdull (talk) 13:38, 9 August 2008 (UTC)

If you have one such hyperplane, you can create a continuum of such hyperplanes by translating (moving parallelly) the given one. Note that a hyperplane does not need to pass through the origin. AxelBoldt (talk) 16:46, 19 January 2022 (UTC)

No cheese

I removed 'The ham sandwich theorem is also sometimes referred to as the "ham and cheese sandwich theorem"' - none of the cited sources seems to mention it, and it appears to have been called the "ham sandwich theorem" for many decades.--mcld (talk) 13:37, 25 February 2013 (UTC)

Hole in proof

The reduction to the Borsuk-Ulam theorem is incorrect as stated, because the function defined is not obviously continuous in the case where the hyperplane choice is ambiguous. I think continuity actually does hold, but an argument to this effect seems warranted. GIrving (talk) 21:38, 12 March 2013 (UTC)

The standard method for this is to replace A_i by a volume distribution that is within ε of its original distribution, but nowhere zero (e.g. take (1 − ε) times the original distribution plus ε times a Gaussian), giving a unique and continuous choice of the splitting hyperplane, and then apply a limiting argument as ε → 0. —David Eppstein (talk) 21:56, 12 March 2013 (UTC)

Definition Correctness

Seems to me that even the illustration on the page is a counter example for the phrasing. I see nothing that indicates that the number of dots of each color is equivalent so I assume it should read that the bisect equally divides each set such that the number of red and blue dots matches the number of red and blue dots on the other side of the line respectively. As an example 8 red 2 blue would need to be bisected to 4 red and 1 blue on each side of the line.

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.(198.135.124.85 (talk) 20:23, 5 May 2015 (UTC))

Assessment comment

The comment(s) below were originally left at Talk:Ham sandwich theorem/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

Needs more pictures, as Cyrius already noted. Also, could use material describing related partition theorems, and algorithmic and statistical applications such as Rousseeuw's catline or ham sandwich tree data structures (that is, not just how to compute ham sandwich cuts, but why one would want to). —David Eppstein 19:05, 14 April 2007 (UTC)

Last edited at 23:09, 19 April 2007 (UTC). Substituted at 02:10, 5 May 2016 (UTC)

Legal values for the number of sets, n

There is no mention of legal values for the number of sets, n, in the article. Clearly it works for n ≥ 2. It seems to work trivially for n = 1, where it the solution is the median. It looks like it even works for algebraic curves of higher order when n = 1; for example, I think we can always find two points on a line that bisect two sets by virtue of containing half of each set between the two points. I could try to put that all in, but in my hands it is original research. Does anyone have an authoritative citation or so much familiarity with the material that it is obvious to them? Also, Is there a reasonable interpretation for n = 0? 𝕃eegrc (talk) 12:07, 15 June 2016 (UTC)

It is in the first sentence: "n measurable "objects" in n-dimensional space". That is, the number of sets equals the dimension of the space they are in. —David Eppstein (talk) 16:10, 15 June 2016 (UTC)

My question is which values of n are applicable in that sentence? I suspect that non-real values, non-integer values, and negative values are out and that integers n ≥ 2 are in, but am curious about the possibilities of n = 0 and n = 1. 𝕃eegrc (talk) 17:54, 15 June 2016 (UTC)

I went bold. Please feel free to correct my edit. 𝕃eegrc (talk) 19:16, 15 June 2016 (UTC)

3D Hyperplane Problem

See YouTube. Numberphile in search bar and then The Ham Sandwich Problem. https://www.youtube.com/watch?v=YCXmUi56rao You need to watch the video by Dr Hannah Fry.

The beneath is my comment on the video, which is self explanatory and raises doubt about the validity of the theorem based on the video as cited.

As I understand it the Claim is that there should be a hyperplane that bisects any three 3d objects; each situated anywhere you might find it, in situ, in standard 3d Euclidean space. Each object of any volume you might find and each of any shape you might find - each object being of uniform density with no restriction placed on how many can be of the same density. I have a circular piece of bread and an isosceles shaped piece of ham situated on it so that all three corners in plan view touch the circumference of the bread. If I take an identical piece of bread there seems to be a limit to where I can put it so that there is a hyperplane that bisects all 3 objects. I.e. there does not to my intuition (how something seems as opposed to any claim that that something is the case), necessarily have to be, a hyperplane that cuts at an angle to rather than normally to, the plane that the first two layers of this 'sandwich' can be considered to be sitting on, that satisfies the bisecting of all three if the third object can be placed anywhere - [Note though it might not seem to be at first, that this is intrinsically different to a second intuition that there could be a case of three found objects not mutually bisectable by a hyperplane [the anti-Claim] and that if this second intuition is wrong, two objects in isolation or considered as two of a set of three, found objects, always are bisectable by at least one ('magic line') hyperplane]. Further, if it makes sense to talk of a limit: we do not know why this second intuition does not hold - the Claim fall - and if it does not fall, why a third object will always be found, as if by magic, on an appropriate hyperplane (compare 'makes it the case' - see below). Our unease here hinges, in the first instance, not on finding a group of three objects in space but on constructing ['building up'] a group of three objects in space.

Why isn't an infinite number of hyperplanes ('filling' the volume of space!) bisecting two objects noetically entailed (compare 'always at least one magic line' [hyperplane!]) for a third object to be 'placeable' anywhere? - if the Claim holds, it seems because placement of the third makes it the case that there will be a hyperplane bisecting the three objects! [Note from the video itself, that whatever hyperplane ends up bisecting all three layers does not seem to have to be any of all the hyperplanes [the limiting case being one only, 'magic line' (hyperplane)] bisecting the (any) first two layers (objects) before the third is placed - and that although there may be an infinite number of ways (places/placements) the third layer (object) could be bisected by any of the hyperplanes bisecting the first two layers (objects), it would be less an infinity than the larger infinity of all the places the third layer (object) could be put (the real anywhere)].

Why in our isosceles case at the two layer stage (specific) and in the general case of finding two objects that are not bisected by that 'larger infinity' of hyperplanes (we knowingly use 'larger infinity' from the paragraph immediately above without any concern as to the number being the same!), does it seem that there is a necessary third object placement ('building up') - which will lie within a set of places; all of which allow the third object to intersect one or one of more than one hyperplanes that bisect the first two objects - as opposed to a real anywhere placement?

There is a paradox if it makes sense to talk of a limit, to talk of one man's 'non-necessary' third object placement at a given time entailing three objects not mutually hyperplane bisectable, and at one and the same time as the placement is made (simultaneity!?) to talk of another man's finding of those three objects, in situ, when that is not subject here to any argument, regardless of how uneasy I may feel, as to their being impossible to be mutually hyperplane bisectable nor for that matter as to their being necessarily spatially related. ( i.e. our aim here was not to prima facie dispute the original Claim! I'm too respectful of clever mathematicians).

Is my intuition [related, in the second instance, to my feeling that I am blindly accepting that third object placement anywhere [in the real sense] makes it the case that the original Claim will be upheld! - that not being a thing I am being explicitly asked to accept as opposed to the 'fact' that there is a priori always a 'magic plane' that bisects three objects] as to limit of third object placement, in construction ('building up') of three objects in space that satisfy the original Claim, a mental prejudice forcing me, as a definite non-mathematician, to bite the mathematical bullet: (http://mathworld.wolfram.com/HamSandwichTheorem.html - G. Beck pers. comm., Feb. 18, 2005 - as a simple explanation which I can't fathom but which claims given a small amount of mathematics, to provide an intuition as to why the Claim is correct), whether any such bullet is a layer at a time proof or not? - This biting, implying 'knowing' something is the case but not necessarily being able to find it in the real world ( Hannah's thought, though G. Beck might argue differently); one in the eye for any empiricist philosopher.

In summary: Why can there be a 'magic hyperplane' that bisects three objects that is not already there bisecting two objects? Any explanation appreciated.

82.25.128.13 (talk) 11:40, 20 September 2019 (UTC) 82.25.128.13 (talk) 07:41, 21 October 2019 (UTC)

Any hyperplane that bisects each of the three given objects will certainly also bisect the first two of them.

If I understand your objection correctly, you believe that there are not "enough" hyperplanes that bisect the first two objects, and because of that you believe that there ought to be a way to place the third object so that it won't be bisected by any hyperplane that also bisects the first two.

This objection is invalid: there is always an entire continuum (i.e. a large infinity) of hyperplanes that bisect two given objects in 3D-space. Take your example of a circular piece of bread of a certain fixed thickness, sitting horizontally in 3D space, with an isosceles piece of ham of a certain fixed thickness on top of it, so that the vertices of the ham are just above the circumference of the bread. You can surely bisect these two with a vertical hyperplane that passes through the triangle's apex and through the midpoint of its base. But there are many more bisecting hyperplanes, namely non-vertical ones; this has to do with the non-zero thickness of bread and ham. Consider the point P which is the centroid of the (cylindrical) piece of bread: right in the middle of it, half up the thickness. For symmetry reasons, each plane passing through P will bisect the bread. Pick such a plane whose angle with the vertical axis is α, where α is a small non-zero angle. Now rotate this plane about the vertical axis through P, so that the rotated versions all pass through P and all still have angle α with the vertical axis. Because there's more ham near the base than near the apex, some of these rotated hyperplanes will have less than 50% of the ham on one side, while others will have more than 50% of the ham on that same side. [This is because α is small enough; if α is too big, most of the ham will remain on one side of the rotating hyperplane.] So by turning, you can always find a plane that divides the ham exactly in half, and you have found a new oblique bisecting hyperplane. This construction works for any value of α in an entire range, giving you a continuum of bisecting planes. AxelBoldt (talk) 21:38, 19 January 2022 (UTC)

"Steinhaus 1938"

I went ahead and amended the citation to "Steinhaus 1938", it's certainly not titled "A Note on the Ham Sandwich Theorem". Rather there isn't really a title per se, but it's in the journal's regular "Notatki z tolologii" [Topology notes] section. Steinhaus also isn't listed as an author, per se. Rather the author is presumably one of the journal's editors (Stanisław Warhaftman with the participation of Edward Stenz & Kazimierz Zarankiewicz). The note relays information from Steinhaus, but it seems inaccurate to cite this as if he wrote this himself. The volume is also clearly labeled "Tom XI." -- is there a reason it was cited as being volume 9? Umimmak (talk) 20:54, 28 August 2020 (UTC)

I changed the reference; it shouldn't list Steinhaus as author. AxelBoldt (talk) 16:46, 19 January 2022 (UTC)

Why is position of third object guaranteed to support theorem?

Can someone please confirm that there are cases when 2 objects are only bisectable mutually by 1 (magic line) hyperplane when found or placed in a particular spatial relationship? (no particular spatial relationship being required by the theorem as I understand it and thus not any spatial relationship verboten).

If the answer is yes in an absolute sense (somebody does) and adherents wish to claim the mathematical proof of the theorem is irrefutable we have a paradox; metaphysical: in the mathematical or linguistic realm or both.

82.29.184.92 (talk) 11:17, 23 November 2020 (UTC)

Can Objects Be Treated As Points For The Purpose of Bisection?

https://www.youtube.com/watch?v=YCXmUi56rao </Numberphile The Ham Sanwich Problem>

It is not clear that Centroid is taken universally by the mathematical community to be the point, such that only hyperplanes it lies on can be equal volume bisectors of a compound object and no hyperplane it lies on cannot be.

It is not true that a hyperplane that bisects an object's volume must pass through the object's centroid. Take for instance, in the plane, a large disk, connected with a thin long rod to another, smaller disk (like in the figure O--o). If the rod is long enough, the centroid will be somewhere between the two disks, on the rod. If the volume of the rod is small enough, any volume-bisecting line will pass through the larger disk, and there will be many volume-bisecting lines that don't pass through the centroid.

It is true that there will always be at least one volume-bisecting hyperplane that passes through the object's centroid, but the same is true for any other point, not just the centroid: just rotate the hyperplane until there's equal volume on both sides. AxelBoldt (talk) 16:28, 19 January 2022 (UTC)

To those who believe the answer lies in: the consideration of each object's centroid and/or center of mass and consequent hyperplane through three (3) points:

You do or do not constrain your "point" with regard to its being inside or outside a given object and you evoke the notion of it being a 'centroid'. Wikipedia tells us that for an object of uniform density, the 'centroid' is also its center of mass; which can lie outside a body. Unproductive attempts to confirm via Google: 'that when the centre of mass lies outside a body, there can be a hyperplane through it that does not bisect', preventing the consideration of a given object as the "point" above, could unhinge a paranoiac as could attempts to find an unambiguous definition of 'centroid'. The limit to the number of hyperplanes bisecting two objects given in the video (a video whose content I find inconsistent), meaning that objects cannot be considered as points, is the best of a bad situation.

The theorem is not about arranging spatial and orientational relationships of three objects to ensure their mutual equal volume bisection but the avowal that, a priori, there will always be a mutually bisecting hyperplane. I doubt the theorem; below and in my other two comments, near the top of one or another Sort By list under the video.

Hyperplanes have a directional property. According to the video there can be more than one hyperplane and on occasion only one [" at least one 'magic line' "] hyperplane bisecting two objects. I'd ask adherents why one of all of the hyperplanes available bisecting two objects does not have to be the mutual bisector of the third. Unless they answer as at the paragraph below I'd then ask adherents why it is necessarily true that one of the hyperplanes available bisecting two objects has to be able to bisect the third given the directionality of each of the hyperplanes and the freedom to place/find the third object anywhere... and the adherents are in zugzwang! FUBAR.

For some time, I have been asking people - including Hannah Fry - to correct me if I am wrong. In my case and summarilly: that adherents inconsistently, erroneously and implicitly hold as fact, unwittingly or otherwise, that there can be a hyperplane bisecting 3 objects that was not there bisecting 2 objects. There are important considerations for the Cosmological Principle and Quine's Analytic/Synthetic dissolution dependent on the truth or untruth of the theorem.

82.29.184.92 (talk) 11:26, 23 November 2020 (UTC)

Your crankery is off-topic here. This talk page should only be about improvements to the article, based on reliable sources, not on personal reflections. —David Eppstein (talk) 16:44, 19 January 2022 (UTC)

"without bothering to automatically state the theorem in the n-dimensional case"

Without bothering implies that the original authors being discussed here considered the generalisation too obvious or trivial to devote much attention to. Is this really what was intended? If so, then the formulation can stand as it is (but omitting automatically which certainly cannot mean in context what the likely non-native speaker who put this in wanted to convey). If not, without taking the trouble (or similar) would be clearer. 2A01:CB0C:CD:D800:CD80:544B:3131:E36A (talk) 12:51, 29 April 2022 (UTC)

 Done. Thanks! AxelBoldt (talk) 19:07, 2 July 2022 (UTC)