What you’re about to watch is a refurbishing of an old video. But even if you’ve seen

that old one, I encourage you to stick around! The whole reason I wanted to go back to clean

up some of the mistakes and reshape a bit of the storyline is that it’s a really nice

piece of math, the kind that deserves to be preserved in its best light if it’s going

to be presented in a video existing in perpetuity.

Plus, math is deep, so there’s almost always something new to be gained from a second or

third look a given topic.

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.