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.