Talk:Ham sandwich theorem

From Wikipedia, the free encyclopedia

Mathematics Portal This article is within the scope of WikiProject Mathematics, which collaborates on articles related to mathematics.
Mathematics rating:	B Class	Mid Priority	Field: Topology
Please update this rating as the article progresses, or if the rating is inaccurate. Click to show/hide comments. Please add to or update the comments to suggest improvements to the article. 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)

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)

[edit] 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/

[edit] 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)