You know that feeling when to things that seem completely unrelated turn out to have
a key connection? In math especially, there’s a certain tingly sensation I get whenever
one of those connections starts to fall into place. That is what I have in store for you
today.
It takes some time to set up, I have to introduce a fair division puzzle for discrete math,
called the “stolen necklace” problem, as well as a topological fact about spheres
that we’ll use to solve it, called the Borsuk-Ulam theorem, but trust me, seeing these two seemingly
disconnected pieces of math come together is worth the setup.
So here’s the puzzle we’re going to solve, the stolen necklace problem. You and your
friend steal a necklace full of a whole bunch of jewels. Maybe it’s got some sapphires,
emeralds, diamonds, and rubies. And they’re all arranged on the necklace in some random
order. And let’s say there happens to be an even number of each type of jewel. Right
here, I have 8 sapphires, 10 emeralds... 4 diamonds... and 6 rubies. You and your friend
want to split the booty evenly, with each of you getting half of each jewel type; 4
sapphires, 5 emeralds, 2 diamonds and 3 rubies each.
Of course, you could just cut all the jewels off the necklace and divvy them up evenly,
but that’s boring, there’s no puzzle here. Instead, the challenge is to make as few cuts
to the necklace as possible, so that you can divvy up the resulting segments between you
and your co-conspirator, and still have each of you end up with half of each jewel type.
For example, with the arrangement shown here, I just did it in 4 cuts. If I give these top
three strands to you, and these bottom two to your co-conspirator, each of you ends up
with 4 sapphires...5 emeralds...2 diamonds...and 3 rubies. The claim; the thing I want to prove
in this video, is that if there are n different jewel types, it’s always possible to do
a fair division with only n cuts, or fewer. So with 4 jewel types in this example, it
should always be possible to find a way to make only 4 cuts and divvy up the 5 necklace
pieces so that each thief has the same number of each jewel type. With 5 jewel types, you
should be able to do it in 5 cuts, no matter the arrangement, and so on.
It’s kind of hard to think about, right? You need to keep track of all of these different
jewel types, ensuring they’re divided fairly while making as few cuts as possible.
Maybe this puzzle seems a little contrived, but it’s core characteristics, like trying
to minimize sharding and allocating some collection of things in a balanced way; these are the
kind of optimization issues that actually come up frequently in practical applications.
For the computer systems folk out there, you can probably imagine how this could relate
to some kind of efficient memory allocation problem. Also, I’ve left a link in the video
description to an electrical engineering paper using this problem.
Independent from its usefulness, though it certainly makes for a good puzzle; can you
always find a fair division using only as many cuts as there are types of jewels.
So that’s the puzzle, remember it, and now let’s take a seemingly unrelated sidestep
to the total opposite side of the math universe: Topology. Imagine taking a sphere in 3d space,
and squishing it somehow onto a 2d plane; stretching and morphing it however you’d
like as you do so. The only constraint I’ll ask is that you do this continuously, which
you can think of as meaning you never cut the sphere or tear it in any way during the
mapping.
As you do this, many different pairs of points will land on top of each other once it hits
the plane, and that’s no big deal. The special fact that we’ll use, known as the Borsuk-Ulam
theorem, is that you will always be able to find a pair of points that started off on
exact opposite sides of the sphere, which land on each other during the mapping. Points
on the exact opposite side of a sphere are called “antipodes”, or “antipodal points”.
For example, if you think of the sphere as earth, and your mapping as a projection of
every point directly onto the plane of the equator, the north and south pole, which are
antipodal, each land on the same point. And in this example, that’s the only antipodal
pair that land on the same point, any other antipodal pair will end up offset from each
other.
If you tweaked this function a bit, maybe shearing it during the projection, the north
and south pole may no longer land on each other. But when the topology gods close a
door, they open a window, because the Borsuk-Ulam theorem guarantees that no matter what, there
must be some other antipodal pair that now land on each other.
The classic example to illustrate this idea, which math educators introducing Borsuk-Ulam
are required by law to present, is that there must exist some pair of points on opposite
sides of the earth, where the temperature and the barometric pressures are both precisely
the same. This is because associating each point on the earth with a pair of numbers,
temperature, and pressure, is the same as mapping the surface of earth onto a 2d coordinate
plane, where the first coordinate represents temperature and the second represents pressure.
Since each of those values varies continuously as you wander around the earth, this association
is a continuous mapping from the sphere onto the plane; some non-tearing way to squish
the surface of the earth into 2 dimensions. So what Borsuk-Ulam implies is that no matter
what the weather patterns are on earth, or any other planet for that matter, two antipodal
points must land on top of each other, which means they map to the same (temperature, pressure)
pair.
Since you’re watching this video, you’re probably a mathematician at heart, so you
want to see why this is true, not just that it’s true. So let’s take a little sidestep
through topology proof land; I think you’ll agree this is a really satisfying line of
reasoning.
So, rephrasing what it is we want to show slightly more symbolically: If you have some
function f that takes in a point p of the sphere, and spits out some pair of coordinates,
you want to show that no matter what crazy choice of this function f is, as long as it’s
continuous, you’ll be able to find some point p so that f(p) = f(-p), where -p is
the antipodal point on the other side of the sphere.
The key idea here is to first rearrange this to say f(p) - f(-p) = (0, 0) and focus on
a new function g(p) defined to be f(p) - f(-p). This way, we need to show that g maps some
point of the sphere to the origin of 2d space, (0, 0). So rather than finding a pair of colliding
points which could land anywhere, this helps us limit our focus to one point of the output
space. This function g has a very special property which will help us out: g(-p) = -g(p),
meaning if you negate the input of g, it negates the output. Basically, these two terms get
swapped. In other words, going to the antipodal point on the sphere results in reflecting
the output through the origin in the output space. Or maybe you think of it as rotating
that output 180 degrees about the origin.
Notice what this means if you were to continuously walk around the equator, and look at the outputs
of g. By the time you get halfway around, the output needs to have wondered to the reflection
of the starting point through the origin. Then, as you continue walking around, the
second half of your path must be the reflection of the first half, which is actually the same
as the 180o rotation of that first path.
Now, there’s a slim possibility that one of these points happens to pass through the
origin, in which case you’ve lucked out and we’re done early. But otherwise, what
we have is a path that winds around the origin at least once. Now look at that path along
the equator, and imagine continuously deforming it towards the north pole. As you do this,
the resulting path in the output space also must continuously deform to a point, since
our function g is continuous. Because it wound around the origin, at some point in this process
it must cross the origin. That means there’s some point p on the sphere where g(p) = (0,
0), which means f(p) = f(-p), which is the antipodal collision we were looking for!
Isn’t that clever? It doesn’t matter what particular continuous function from the sphere
to the plane you define, this line of reasoning will always zero in on an antipodal pair that
land on top of each other.
At this point, you might be feeling like we’ve strayed extremely far from the necklace problem,
but just you wait! Here’s where things start getting clever. First, answer me this: What
is a sphere, really. Well, points in 3d space are represented with three coordinates. In
some sense what 3d space is, to a mathematician at least, is all possible triplets of numbers.
The simplest sphere to describe with coordinates is a standard unit sphere centered at the
origin; the set of all points a distance 1 from the origin, meaning all triplets with
the special property that the sum of their squares is 1. So the geometric idea of a sphere
is related to the algebraic idea of some set of positive numbers that add to 1. Remember
that.
If you have one of these triplets, the point on the opposite side of the sphere, the corresponding
antipodal point, is whatever you get by flipping the sign of each coordinate, right? So let’s
just write out what Borsuk-Ulam is saying symbolically; this will help connect back
to the necklace problem. For any function that takes in points on the sphere –triplets
of numbers whose squares sum to 1–and spits some point in 2d space – some pair of coordinates
like temperature and pressure – as long as that function is continuous, there will
be some input so that flipping all the signs doesn’t change the output.
With that in mind, look back at the stolen necklace problem. Part of the reason these
two things feel so unrelated is that the necklace problem is discrete, while the Borsuk-Ulam
theorem is continuous, so our first step is to translate the stolen necklace problem into
a continuous version, seeking a connection between necklace division and points on a
sphere.
For right now, let’s limit ourselves to the case where there are 2 jewel types, sapphires,
and emeralds, and we’re hoping to make a fair division of the necklace after only 2
cuts. As an example to have up on the screen, let’s say there are 8 sapphires and 10 emeralds
on the necklace. Just as a reminder, this means the goal is to cut the necklace in two
spots and divvy up the 3 segments so that each thief ends up with half of the sapphires
and half of the emeralds. Notice how the top and bottom here each have 4 sapphires and
5 emeralds.
Think of the necklace as a line with length 1, with the jewels sitting evenly spaced on
it. Now divide up that line into 18 evenly-sized segments, one for each jewel, and rather than
thinking of each jewel as a discrete indivisible entity on its segments, remove the jewel itself
and just paint that segment the color of the jewel. So in this case, 8/18ths of the line
would be painted sapphire, while 10/18ths would be painted emerald.
The continuous version of the puzzle is to now ask whether we can find two cuts anywhere
on this line, not necessarily on these 1/18th interval marks, that let us divide up the
pieces so that each thief has an equal length of each color; in this case each thief should
have a total of 4/18th of sapphire colored segments, and 5/18ths of emerald-colored segments.
An important and somewhat subtle point is that if you can solve this continuous variant
of the puzzle, you can also solve the original discrete version. Let’s say you do find
a fair division whose cuts don’t happen to fall cleanly between jewels, maybe it cuts
part way through an emerald segment. Well, because this is a fair division, the length
of emerald in both the top and bottom group has to add up to exactly 5 emerald segments,
a whole number multiple of the segment lengths.
So even if the division cut partially into an emerald segment on the left, it has to
cut partially into an emerald segment on the right as well so that the total length adds
up to a whole number multiple of the segment length. This means we can adjust each cut
without affecting the division until they do ultimately line up on these 1/18th marks.
Now, in this continuous case, in which you can cut wherever you want on the line, think
about all choices that go into cutting the necklace and allocating the pieces. First,
you choose two places to cut the interval. But another way to think of that is to choose
3 positive numbers that add up 1. For example, maybe you choose ⅙, ⅓ and ½, which corresponds
to these two cuts.
Any time you find 3 positive numbers that add to 1, it gives you a way to cut the necklace
and vice versa. And after that, you have to make a binary choice for each of these three
pieces as to whether it goes to Thief 1 or Thief 2.
Now compare that to if I asked you to choose some arbitrary point on the sphere in 3d space;
some point with coordinates (x, y, z) to that x^2+y^2+z^2=1. Well, you might also start
off choosing 3 positive numbers that add to 1, maybe you want x^2 to be ⅙, y^2 to be
⅓, and z^2 to be ½. Then, you have to make a choice for each one, choosing whether to
take the positive square root, or the negative square root.
So in a way that’s completely parallel to choosing a necklace division, choosing a point
on the sphere involves first finding 3 positive numbers that add to 1, then making a binary
choice for what to do with each one.
Alright, hang with me now, because this is the key observation for the whole video! It
gives a correspondence between points on the sphere and necklace divisions. For any point
(x, y, z) on the sphere, because x^2 + y^2 + z^2 = 1, you can cut the necklace so that
the first piece has length x^2, the second has length y^2, and the third has length z^2.
For the first piece, if x is positive, give it to Thief 1, otherwise, give it to Thief
2. For the second piece, if y is positive, give it to Thief 1, otherwise, give it to
Thief 2. Likewise, give the third piece to Thief 1 if z is positive, and to Thief 2 if
z is negative.
And you could go the other way around; any way to divide up the necklace and divvy up
the pieces gives us a unique point on the sphere. It’s as if the sphere is the perfect
way to encapsulate the idea of all possible necklace divisions with a geometric object.
We’re tantalizingly close now. Think about the meaning of antipodal points under this
association. If the point (x, y, z) on the sphere corresponds to some necklace allocation,
what does the point (-x, -y, -z) correspond to? Well, the squares of these coordinates
are all the same, so each one corresponds to making the same cuts on the necklace. The
difference is that every piece switches which thief it belongs to. So jumping to an antipodal
point on the opposite side of the sphere corresponds to exchanging all the pieces.
Now remember what it is that we’re actually looking for; we want to total length of each
jewel type belonging to Thief 1 to equal that for Thief 2. Or in other words, in a fair
division, performing this antipodal swap doesn’t change the amount of each jewel belonging
to each thief.
Your brain should be burning with the thought of Borsuk Ulam at this point.
Specifically, let’s construct a function that takes in a given necklace allocation
and spits out two numbers: The total length of sapphire belonging to Thief 1, and the
total length of emerald belonging to Thief 1. We want to show that there must exist a
way to divide the necklace with two cuts and divvy up the pieces so that these two numbers
are the same as what they would be for thief 2; or, said differently, where swapping all
the pieces wouldn’t change these two numbers for Thief 1.
Because of this back and forth between necklace allocations and points on the sphere, and
because pairs of numbers correspond with points on the xy plane, this is, in effect, a map
from the sphere onto the plane. So the Borsuk-Ulam theorem guarantees that some antipodal pair
of points on the sphere land on each other in the plane, which means there must be some
necklace division using two cuts that gives a fair division between thieves.
That, my friends, is what beautiful math feels like.
If you’re anything like me, you’re just basking in the glow of what a clever proof
that is, and it might be easy to forget that we actually want to solve the more general
stolen necklace problem, with more than just two jewel types. Luckily, we’ve now done
95% of the work, generalizing is very brief.
The main thing to mention is that there’s a more general version of the Borsuk-Ulam
theorem, one which applies to higher-dimensional spheres.
As an example, Borsuk-Ulam also applies to mapping hyperspheres in 4d space into 3d space.
What I mean by hypersphere is the set of all possible lists of 4-coordinates where the
sum of their squares equals 1; those are points in 4d space a distance 1 from the origin.
Borsuk-Ulam says that if you try to map that set, all those special quadruplets, into 3-dimensional
space, continuously associating each one some triplet of numbers, there must be some antipodal
collision. An input (x1, x2, x3, x4) where flipping all the signs won’t change the
output.
I’ll leave it to you to pause and ponder to think about how this can apply to the 3-jewel
case, and about what the general statement of Borsuk-Ulam might be and how it applies
to the general necklace problem. And maybe, just maybe, this gives you an inkling for
why mathematicians care about higher dimensions spheres, regardless of whether or not they
exist in physical reality. It’s not about the spheres, per se, but about what problems
in math they can encode.