Martin Gardner and the Ham Sandwich Theorem
In More Mathematical Puzzles and Diversions, Martin Gardner makes a passing reference to the Ham Sandwich Theorem. It goes like this
So imagine you have two roughly cut pieces of bread and a slice of ham, then you can always cut the sandwich in half such that each half has exactly half of each piece of bread and half of the ham, no matter how roughly strewn the pieces are.
According to Gardner the generalized version has been proved by Tukey and Stone: any n shapes in $\mathbb{R}^n$ can be simultaneously halved by a single $n-1$ dimensional hyperplane. But I thought I'd have a go at proving it myself in the 3D case, just for kicks.
First observe that there are at least enough degrees of freedom to make it not impossible. A plane (other than one going through the origin) can be described by the equation $k_xx+k_yy+k_zz = 1$ for some $\boldsymbol{k} \neq \boldsymbol{0}$ so there are 3 parameters we can play with in our attempt to get 3 values to all equal $\frac{1}{2}$. However, it's actually simpler if we parametize our planes slightly differently:
Each plane is defined by 3 values $r,\phi,\theta$ where $r$ is the perpendicular distance from the origin, $\phi$ is the angle made by the perpendicular with the z-axis, and $\theta$ the angle made by it's projection onto the xy plane with the x-axis. By the intermediate value theorem, for every $\phi, \theta$ there is an $r$ which halves object 1. Let's plot these:
Note that if you fix $\theta$ and add $\pi$ to $\phi$ the value of $r$ must change sign, to give us the same plane (although flipped). This means that every object that is $n\%$ on the far side of the plane must change to being $100-n\%$ on the far side. So, by the intermediate value theorem there is some place on the line between $(\theta,\phi)$ and $(\theta,\phi+\pi)$ where both object 1 and object 2 are halved by the plane. Let's plot the $\phi, \theta$ for which there is a plane that halves these two objects:
We finish off the theorem with a similar trick - yet another application of the Intermediate Value Theorem. Note that if we add $\pi$ to $\theta$ then we need to change the sign of $r$ and add $\pi$ to $\phi$ to get back the same plane, but flipped. This means that somewhere on the curve between $\theta$ and $\theta+\pi$ the plane bisects object 3 as well as objects 1 & 2.
Da dahh.
POSTSCRIPT
There's another very similar problem. Suppose you've got a four legged table whose leg ends form a perfect square. However the floor is uneven and the table wobbles. Show that you can stop the table wobbling by rotating it!
Any 3 shapes in 3 dimensional space can be simultaneously bisected by a single plane
So imagine you have two roughly cut pieces of bread and a slice of ham, then you can always cut the sandwich in half such that each half has exactly half of each piece of bread and half of the ham, no matter how roughly strewn the pieces are.
According to Gardner the generalized version has been proved by Tukey and Stone: any n shapes in $\mathbb{R}^n$ can be simultaneously halved by a single $n-1$ dimensional hyperplane. But I thought I'd have a go at proving it myself in the 3D case, just for kicks.
First observe that there are at least enough degrees of freedom to make it not impossible. A plane (other than one going through the origin) can be described by the equation $k_xx+k_yy+k_zz = 1$ for some $\boldsymbol{k} \neq \boldsymbol{0}$ so there are 3 parameters we can play with in our attempt to get 3 values to all equal $\frac{1}{2}$. However, it's actually simpler if we parametize our planes slightly differently:
Each plane is defined by 3 values $r,\phi,\theta$ where $r$ is the perpendicular distance from the origin, $\phi$ is the angle made by the perpendicular with the z-axis, and $\theta$ the angle made by it's projection onto the xy plane with the x-axis. By the intermediate value theorem, for every $\phi, \theta$ there is an $r$ which halves object 1. Let's plot these:
Note that if you fix $\theta$ and add $\pi$ to $\phi$ the value of $r$ must change sign, to give us the same plane (although flipped). This means that every object that is $n\%$ on the far side of the plane must change to being $100-n\%$ on the far side. So, by the intermediate value theorem there is some place on the line between $(\theta,\phi)$ and $(\theta,\phi+\pi)$ where both object 1 and object 2 are halved by the plane. Let's plot the $\phi, \theta$ for which there is a plane that halves these two objects:
We finish off the theorem with a similar trick - yet another application of the Intermediate Value Theorem. Note that if we add $\pi$ to $\theta$ then we need to change the sign of $r$ and add $\pi$ to $\phi$ to get back the same plane, but flipped. This means that somewhere on the curve between $\theta$ and $\theta+\pi$ the plane bisects object 3 as well as objects 1 & 2.
Da dahh.
POSTSCRIPT
There's another very similar problem. Suppose you've got a four legged table whose leg ends form a perfect square. However the floor is uneven and the table wobbles. Show that you can stop the table wobbling by rotating it!
Comments
Post a Comment