The Ham Sandwich Theorem

Theorem

Ever wondered if there is a guaranteed way to cut through your ham sandwich so that the bread, the ham, and the other slice of bread are all divided equally in half? Maths can help!! This is cool theorem I came across recently.

Oh! And read to the end to find out how you can tell the weather in Australia when you are in the UK.

Theorem (Ham Sandwich Theorem): For any three compact connected sets in three dimensional space, there is a plane that simultaneously splits each of them into two equal parts.

I particularly like the idea of the proof, but first off, let’s understand what this theorem is saying. It says if we take any three “blobs” (aka two slices of bread and a slice of ham) in three dimensional space, there is a plane that splits each of them in equally. Each of them! Equally! Personally I find it easy to imagine a plane that might touch each of the “blobs”, but one that will divide all of them equally is much harder to imagine.

Compact and connected are mathematical terms that essentially mean the shapes are “nice” shapes. In three dimensions ( \mathbb{R}^3), this is the shapes are closed, bounded and connected. The exact definitions aren’t too important here, but have a think – what do you think they mean? Can you think of some sort of shape that isn’t connected, or bounded, or closed (closed might be the hardest one)?

So how would you go about proving it? Maybe by constructing a plane that goes through two of the “blobs” and seeing if you can tilt it somehow to go through the third?

It’s actually a great corollary to the Borsuk-Ulam theorem:

Theorem (Borsuk-Ulam): Let f \colon S^2 \to \mathbb{R}^2 be any continuous function from the sphere to two dimensional space. Then there is a point p on the sphere such that f has the same value at its opposite (antipodal) point -p, i.e. f(p)=f(-p).

Think about it:

Can you see how to apply this theorem to the above problem?

Let’s give it a go.

Proof

Put the sphere, S^2 at the origin in three dimensional space. Let the three “blobs” be called A_1, A_2 and A_3 respectively. For any point p on the sphere, we have can regard it as a direction or vector that goes through the origin out through the point p. Let P_i be a plane perpendicular to the direction given by p that divides the “blob” A_i equally into two pieces (it’s easy to think about one of these existing. Something like the Intermediate Value theorem would work here).

Imagining the planes that make up the proof of the Ham Sandwich Theorem.

Imagining the planes that make up the proof of the Ham Sandwich Theorem.

Then let d_1, d_2 be the distance along the direction of p between P_3 and P_1P_2 respectively. Now we have a continuous function that takes a point p \in S^2 on the sphere, and assigns a value f(p)=(d_1,d_2) in two dimensions. Also, in this case, draw a picture to see that f(-p)=(-d_1, -d_2).

Now let’s think about the Borsuk-Ulam theorem. It tells us there is a point p such that f(p)=f(-p), which means at this p, f(p)=(d_1,d_2)=(-d_1,-d_2)=f(-p). This can only be true when d_1=0, d_2=0, and this means the distance between the planes is zero, or rather, there’s now just one plane!   \square

Phew!

There’s been quite a lot of info here. There’s a lot of notation, but the proof itself isn’t that complicated. Have another read over it with some pens and paper, and draw some pictures as you go along.

Alternatively, dissemble your lunch next time and work out if you can divide each piece in half.

Note: after a proof, mathematicians draw a little square (either empty or filled in) to signify the proof is finished.

Also note: the real maths here is simply showing that a plane exists, not how to find one!! That’s a job left up to engineers…

Other reading

There’s a lot on the internet about the Borsuk Ulam and Ham Sandwich theorems which both have a number of applications, such as in computer science! I first came across them in Chapter 1.1  of Algebraic Topology by Allen Hatcher (proving the Ham Sandwich theorem is an exercise), but since many universities only cover topology in third year at the earliest, this book might be a bit advanced.

There’s a cool application of the Borsuk Ulam theorem that’s commonly stated with it: Think of the surface of the Earth as a sphere. Think of any two variables,  like temperature and pressure. The Borsuk Ulam theorem says there’s a point on the Earth’s surface where the point on the exact opposite side of the Earth has equal temperature and pressure.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s