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.
I like this video a lot, though it is 80-85%* the same as this previous video about the Borsuk-Ulam Thm and the Stolen Necklace Problem. I really like the five-panel outline at 0:47 in the new video. In some ways I actually like the proof method of the old video better (first looking at points where the x-coordinates of the outputs are equal), but the new proof (making an odd function and showing it passes through the origin) has some advantages too.
\ I originally just wrote "90%" for conversational effect but then decided that I couldn't use a completely fictional percentage in a comment about u/3Blue1Brown because I would feel bad being so lazy when Grant puts so much good work into these videos. So... the proof of Borsuk-Ulam is from 7:07 to 9:12 in the original 21:54-long video, and an alternative proof is from 6:30 to 9:43 in the new 19:49-long video. Thus the proof is 14% of the original video and 16% of the new video. Since this proof is the main thing that changed between the two versions, I'm saying the videos are 85% the same in terms of pure mathematical content. Other bits of the presentation might contribute to 80% overall alignment. I'll admit I did basically guess on that number, but percentages that are multiples of 10 are often assumed to be just approximations, so I'm sticking with my "80-85%" range.)
So the next natural question is:
What is the best way to find a valid splitting of the necklace? Is there a substantially better way than just checking all the possibilities?
One of the highest quality youtube channels in existence felt they needed to replace one of their videos. That's dedication.
What was the mistake of the original video?
What happens if there are more than two thieves?
So the example shows there is always a valid antipodal pair for k cuts and k jewels. What exactly breaks down to show 3 cuts may be insufficient for >3 jewels? Won't this also be a continuous function with some p such that g(p) = 0? But it shouldn't be solvable in the general case right? By that line of reasoning, every strand is evenly divisible by 3 cuts, but thats not true.
now I know it's not pronouced anti-pod-al
It's awesome... Love maths :)
What happens with more than 2 thieves?
Also Borsuk-Ulam is about squishing a sphere ANY way to the 2D plan. But the specific splitting of the necklace into chunks that equal 1 is only ONE way of squishing the sphere.... With other squishing of the sphere, there are other analogous methods for chopping up the necklace then.... right? like, i get that the animation he rendered was just the one way of doing it, but:
Is there a way to show how the other mathematical methods for splitting the necklace match the other methods of squishes?