The Turkey Sandwich Theorem

In honor of the holiday, we thought we should talk about one of our favorite food-related theorems, the Turkey Sandwich Theorem (actually, it’s called the Ham Sandwich Theorem or the Stone-Tukey Theorem).

It’s the answer to a problem faced by everyone with brothers and sisters:  How to evenly divide delicious Thanksgiving treats?

The theorem states that if you have n objects* in n dimensional space, then you can find a single n-1 dimensional hyperplane which will slice all n objects exactly into two halves of equal volume.

But is two equal halves?

 

What does that mean and what does it have to do with turkey sandwiches?  A sandwich lives in our 3 dimensional world and is made of 3 objects (two slices of bread and the turkey).  The theorem says that with a single slice by a knife, you can cut the sandwich so that all three parts are cut into equal halves!  And notice, the theorem doesn’t say anything about the size of the parts, or where they are located!

So you can cut everything into equal halves with a single slice (using a very big knife!), even if one piece of bread is in Norman, one is in Australia, and the turkey is the size of the moon and in orbit around Omicron Persei 8!

Let’s back up and talk about the smaller dimensional cases.  First, let’s start with a single object (let’s call it Edwin) in a n=1 dimensional world.  A 1-dimensional world means you are living on the real line.  So image Edwin is living on the real line.  Then the “volume” of Edwin is just its length!  A “hyperplane” is a n-1=0 dimensional object, so just a point.

The theorem says that you can place the point on the real line so exactly 1/2 pf Edwin’s length is to the left of the point, and 1/2 is to the right.

This case is small enough, that we can even prove it using the Intermediate Value Theorem (IVT) from Calc I:

For each x on the real line, let L(x) be the length of Edwin on the left side of the point x, and let R(x) be the length of Edwin on the right hand side of the point x.   We can then define a function f(x) with inputs from the real numbers and outputs to the real numbers given by the rule

f(x) = R(x) – L(x).

Then when x is a very large negative number, all of Edwin is to the right of the point, so f(x) will be a positive number (it will be Edwin’s total length).  When x is a very large positive number, all of Edwin will be to the left of x and so f(x) will be a negative number (it will be the negative of Edwin’s length).  This means that as x goes from left to right, f(x) moves continuously from positive to negative.  By the IVT, there must be an x where    f(x) = 0.  But then R(x) = L(x), which means that Edwin is split down the middle if we put our point right at x!  And that’s exactly what we were looking for!

 

Now let’s go up a dimension.  Let’s now say that there are two objects in living in a n=2 dimensional world.   Now we have two objects (let’s call them Edwin and Abbott) living in the plane.  Then “volume” is just area.  A hyperplane is now a 2-1 =1 dimensional line in the plane.  So the theorem says we can draw a line which cuts both Edwin and Abbott exactly in half by area.

We can again sketch a proof** using the IVT just like in the previous case:

First, for each angle t between 0 and 180 degrees, you can use the IVT just like we did above to show that there is a line which makes an angle of t degrees with the x-axis and cuts Edwin exactly in half.  Let’s call that line E(t).  Doing exactly the same, we can use the IVT to find a line which makes an angle of t degrees with the x-axis and cuts Abbott exactly in half.  let’s call that line A(t).

 

Now define a function f(t) which gives as its output the distance from E(t) to A(t).  If there is a t which makes f(t)=0, then this exactly means that we have one line which cuts both Edwin and Abbott in half, which is exactly what we want!

 

To see that this happens, all we need to do is notice that f(0) = -f(180).  So if one is positive, the other is negative.  That is, as t goes from 0 to 180, then f(t) goes from positive to negative (or negative to positive).  By the IVT, there is a t between 0 and 180 such that f(t)=0.  And that’s just what we wanted!

 

Now we’re back to 3 dimensions.  Seeing a proof is more difficult, but the theorem is equally true in 3 and higher dimensions!

So when your Uncle Mike tries to get the larger piece of pumpkin pie by claiming you can’t cut it into equal pieces, you can apply the Turkey Sandwich Theorem!

Footnotes:

* By “object”  all that is really needed is that you have a subset of n dimensional space which has a volume.   The technical name for such a set is measurable.  It can be of any size and in any location.  In particular, that means the object can have multiple subparts (so the turkey sandwich could have the bread as one part, the turkey as a second part, and the lettice, tomato, and cheese together as the third part).

To use the IVT we are assuming more, that the length/area/volume varies continuously as you change where you’re slicing.  But any reasonable object from the real world will be okay.  Only strange shapes (like the Vitali set) are out.

** We’re cheating here.  Since the IVT is only an existence theorem, it alone is not enough to know that if we move the angle by a little bit that the line also only moves by a little bit.  That is, we don’t know that E(t) and A(t) are continuous, so we don’t know f(t) is continuous, so we don’t know that we can use the IVT.  But if we’re more careful, these details can be sorted out.

Advertisements