# Using topology for discrete problems | The Borsuk-Ulam theorem and stolen necklaces

## Метаданные

- **Канал:** 3Blue1Brown
- **YouTube:** https://www.youtube.com/watch?v=yuVqxCSsE7c
- **Дата:** 18.11.2018
- **Длительность:** 19:21
- **Просмотры:** 947,837

## Описание

Solving a discrete math puzzle using topology
I was originally inspired to cover this thanks to a Quora post by Alon Amit
Help fund future projects: https://www.patreon.com/3blue1brown
An equally valuable form of support is to simply share some of the videos.
Special thanks to these supporters: http://3b1b.co/borsuk-thanks
Home page: https://www.3blue1brown.com

Want more fair division math fun?  Check out this Mathologer video
https://youtu.be/7s-YM-kcKME
(Seriously, Mathologer is great)

These videos are supported by the community.
https://www.patreon.com/3blue1brown

The original 1986 by Alon and West with this proof
https://m.tau.ac.il/~nogaa/PDFS/Publications/The%20Borsuk-Ulam%20Theorem%20and%20bisection%20of%20necklaces.pdf

VSauce on fixed points
https://youtu.be/csInNn6pfT4

EE Paper using ideas related to this puzzle
https://dl.acm.org/citation.cfm?id=802179

I first came across this paper thanks to Alon Amit's answer on this Quora post
https://www.quora.com/As-of-2016-what-do-mathematicians-on-Quora-think-of-the-3Blue1Brown-maths-videos

If you want to contribute translated subtitles or to help review those that have already been made by others and need approval, you can click the gear icon in the video and go to subtitles/cc, then "add subtitles/cc".  I really appreciate those who do this, as it helps make the lessons accessible to more people.

Music by Vincent Rubinetti:
https://vincerubinetti.bandcamp.com/album/the-music-of-3blue1brown

Time stamps:
0:00 - Introduction
0:36 - The stolen necklace problem
3:08 - The Borsuk Ulam theorem
9:15 - The continuous necklace problem
13:19 - The connection
17:30 - Higher dimensions

------------------

3blue1brown is a channel about animating math, in all senses of the word animate.  And you know the drill with YouTube, if you want to stay posted on new videos, subscribe: http://3b1b.co/subscribe

Various social media stuffs:
Website: https://www.3blue1brown.com
Twitter: https://twitter.com/3blue1brown
Reddit: https://www.reddit.com/r/3blue1brown
Instagram: https://www.instagram.com/3blue1brown_animations/
Patreon: https://patreon.com/3blue1brown
Facebook: https://www.facebook.com/3blue1brown

## Содержание

### [0:00](https://www.youtube.com/watch?v=yuVqxCSsE7c) Introduction

You know that feeling you get when 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. This is what I have in store for you today. It takes some time to set up, I have to introduce a fair division puzzle from 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 well worth the setup.

### [0:36](https://www.youtube.com/watch?v=yuVqxCSsE7c&t=36s) The stolen necklace problem

Let's start with the puzzle we're going to solve. You and your friend steal a necklace full of a bunch of jewels, maybe it's got some sapphires, emeralds, diamonds, and rubies. They're all arranged on the necklace in some random order. And let's say it happens to be an even number of each type of jewel. Here I have 8 sapphires, 10 emeralds, 4 diamonds, and 6 rubies. You and your friend want to split up the booty evenly, with each of you getting half of each jewel type, that is 4 sapphires, 5 emeralds, 2 diamonds, and 3 rubies each. Of course you could just cut off all the jewels and divvy them up evenly, but that's boring, there's not a puzzle there. Instead, the challenge is for you 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, with each of you getting half of each jewel type. For example, for the arrangement I'm showing here, I just did it with 4 cuts. If I give the top 3 strands to you, and these bottom 2 strands 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 this fair division with only N cuts, or fewer. So with 4 jewel types, no matter what random ordering of the jewels, it should be possible to cut it in 4 places 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 with 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. And if you sit down to try this, this is a shockingly hard fact to prove. Maybe the puzzle seems a little contrived, but its core characteristics, like trying to minimize sharding and allocating some collections of things in a balanced way, these are the kind of optimization issues that actually come up quite frequently in practical applications. For the computer system folks among you, I'm sure you can imagine how this is analogous to kinds of efficient memory allocation problems. Also for the curious among you, I've left a link in the description to an electrical engineering paper that applies this specific problem. Independent from the usefulness though, it certainly does make 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 we take a seemingly unrelated

### [3:08](https://www.youtube.com/watch?v=yuVqxCSsE7c&t=188s) The Borsuk Ulam theorem

sidestep to the total opposite side of the mathematical universe, topology. Imagine taking a sphere in 3D space and squishing it somehow onto the 2D plane, stretching and morphing it however you'd like to do so. The only constraint I'll ask is that you do this continuously, which you can think of as meaning never cut the sphere or tear it in any way during this mapping. As you do this, many different pairs of points will land on top of each other once they hit the plane, and that's not really a big deal. The special fact we're going to use, known as the Borsuk-Ulam theorem, is that you will always be able to find a pair of points that started off on the exact opposite sides of the sphere, which land on each other during the mapping. Points on the exact opposite like this are called antipodes, or antipodal points. For example, if you think of the sphere as Earth, and you're mapping as a straight projection of every point directly onto the plane of the equator, the north and the south pole, which are antipodal, each land on the same point. And in this example, that's the only antipodal pair that lands on the same point, and the other antipodal pair will end up offset from each other somehow. If you tweaked this function a bit, maybe shearing it during the projection, the north and the south pole don't land on each other anymore. 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 top of 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 the opposite side of the Earth where the temperature and the barometric pressure are both precisely the same. This is because associating each point on the surface of the Earth with a pair of numbers, temperature and pressure, is the same thing as mapping the surface of the Earth onto a 2D coordinate plane, where the first coordinate represents temperature, and the second represents pressure. The implicit assumption here is that temperature and pressure each vary continuously as you walk around the Earth, so this association is a continuous mapping from the sphere onto a plane, some non-tearing way to squish that surface into two dimensions. So what Borsuk-Ulam implies is that no matter what the weather patterns 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, and I think you'll agree that this is a really satisfying line of reasoning. First 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 function this is, as long as it's continuous, you'll be able to find some point p so that f of p equals f of negative where negative p is the antipodal point on the other side of the sphere. The key idea here, which might seem small at first, is to rearrange this and say f of p minus f of negative p equals zero zero, and focus on a new function g of p that's defined to be this left-hand side here, f of p minus f of negative p. This way, what we need to show is that g maps some point of the sphere onto the origin in 2D space. So rather than finding a pair of colliding points which could land anywhere, this helps limit our focus to just one point of the output space, the origin. This function g has a pretty special property which is going to help us out, that g of negative p is equal to negative g of p. Basically negating the input involves swapping these terms. In other words, going to the antipodal point of the sphere results in reflecting the output of g through the origin of the output space, or rotating the output 180 degrees around the origin. Notice what this means if you were to continuously walk around the equator and look at the outputs of g. What happens when you go halfway around? Well, the output needs to have wandered to the reflection of the starting point through the origin. Then, as you continue walking around the other half, the second half of your output path must be the reflection of the first half, or equivalently, it's the 180 degree 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 were done early. But otherwise, what we have here is a path that winds around the origin at least once. Now, look at that path on the equator, and imagine continuously deforming it up to the north pole, cinching that loop tight. As you do this, the resulting path in the output space is also continuously deforming to a point, since the function g is continuous. Now, because it wound around the origin at some point during this process, it must cross the origin, and this means there is some point p on the sphere where g of p has the coordinates 0,0, which means f of p minus f of negative p equals 0,0, meaning f of p is the same as f of negative p, the antipodal collision we're looking for. Isn't that clever? And it's a pretty common style of argument in the context of topology. 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 lands on top of each other.

### [9:15](https://www.youtube.com/watch?v=yuVqxCSsE7c&t=555s) The continuous necklace problem

At this point, maybe you're thinking, yeah yeah, lovely math and all, but we've strayed pretty far away 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 that's what 3D space is to a mathematician at least, all possible triplets of numbers. And the simplest sphere to describe with coordinates is the standard unit sphere centered at the origin, the set of all points a distance 1 from the origin, meaning all triplets of numbers so that the sum of their squares is 1. So the geometric idea of a sphere is related to the algebraic idea of a set of positive numbers that add up to 1. That might sound simple, but tuck that away in your mind. 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 the Borsuk-Ulam theorem is saying symbolically. Trust me, this will help with getting back to the necklace problem. For any function that takes in points on the sphere, triplets of numbers who square sum to 1, and spits out some point in 2D space, some pair of coordinates like temperature and pressure, as long as the function is continuous, there will be some input so that flipping all of its signs doesn't change the output. With that in mind, look back at the necklace problem. Part of the reason these two things feel so very 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 the connection between necklace divisions and points on the sphere. For right now, let's limit ourselves to the case where there's only two jewel types, say sapphires and emeralds, and we're hoping to make a fair division of this necklace after only two cuts. As an example, just to have up on the screen, let's say there's 8 sapphires and 10 emeralds on the necklace. Just as a reminder, this means the goal is to cut the necklace in two different spots, and divvy up those three segments so that each thief ends up with half of the sapphires and half of the emeralds. Notice the top and bottom each have 4 sapphires and 5 emeralds. For our continuousification, think of the necklace as a line with length 1, with the jewels sitting evenly spaced on it, and 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 each segment, 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, and 10 18ths would be painted emerald. The continuous variant of the puzzle is now to ask if we can find two cuts anywhere on this line, not necessarily on the 1 18th interval marks, that lets 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 18ths of sapphire colored segments, and 5 18ths of emerald colored segments. An important but somewhat subtle point here is that if you can solve the continuous variant, you can also solve the original discrete version. To see this, let's say you did find a fair division whose cuts didn't happen to fall cleanly between the jewels. Maybe it cuts only part way through an emerald segment. Well, because this is a fair division, the length of emerald in both top and bottom has to add up to 5 total 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 right, and more specifically in such a way that the total length adds up to a whole number multiple of the segment length. What that means is that you can adjust each cut without affecting the division so that they ultimately do line up on the 1 18th marks. Now why are we doing all this? Well, in the continuous case, where you can cut wherever you want on this line

### [13:19](https://www.youtube.com/watch?v=yuVqxCSsE7c&t=799s) The connection

think about all of the choices going into dividing the necklace and allocating the pieces. First you choose two locations to cut the interval, but another way to think about that is to choose three positive numbers that add up to one. For example, maybe you choose 1 6th, 1 3rd, and 1 half, which correspond to these two cuts. Any time you find three positive numbers that add up to one, it gives you a way to cut the necklace, and vice versa. After that, you have to make a binary choice for each of these pieces, for whether it goes to thief 1 or thief 2. Now compare that to if I asked you to choose some arbitrary point on a sphere in three-dimensional space, some point with coordinates x, y, z, so that x2 plus y2 plus z2 equals 1. Well, you might start off by choosing three positive numbers that add to one. Maybe you want x2 to be 1 6th, y2 to be 1 3rd, and z2 to be 1 half. Then you have to make a binary choice for each one of them, choosing whether to take the positive square root or the negative square root, in a way that's completely parallel to dividing the necklace and allocating the pieces. Alright, hang with me now, because this is the key observation of 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 x2 plus y2 plus z2 is 1, you can cut the necklace so that the first piece has a length x2, the second has a length y2, and the third has a length z2. For that first piece, if x is positive, give it to thief 1, otherwise 2. For the second piece, if y is positive, give it to thief 1, otherwise give it to thief 2, and 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 that you divide up the necklace and divvy up the pieces gives us a unique point on the sphere. It's as if the sphere is a weirdly perfect way to encapsulate the idea of all possible necklace divisions, just with a geometric object. And here we are tantalizingly close. Think of 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 negative x, negative y, and negative z correspond to? Well, the squares of these three coordinates are 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 with exchanging the pieces. Now remember what it is that we're actually looking for. We want the 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, you might 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 of the pieces wouldn't change those two numbers. Because of this back and forth between necklace allocations and the points of 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. And the animation you're looking at right now is that literal map for the necklace I was showing. 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 the thieves. That, my friends, is what beautiful math feels like.

### [17:30](https://www.youtube.com/watch?v=yuVqxCSsE7c&t=1050s) Higher dimensions

Alright, and 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 what we actually want to solve is the more general stolen necklace problem, with any number of jewel types. Luckily, we've now done 95% of the work. Generalizing is pretty brief. The main thing to mention is that there is a more general version of the Borsuk-Ulam theorem, one that applies to higher dimensional spheres. As an example, Borsuk-Ulam applies to mapping hyperspheres in 4D space into three dimensions. And what I mean by a hypersphere is the set of all possible lists of four coordinates where the sum of their squares equals one. Those are the points in 4D space a distance one from the origin. Borsuk-Ulam says that if you try to map that set, all those special quadruplets of numbers, into three-dimensional space, continuously associating each one with some triplet of numbers, there must be some antipodal collision, an input x1, x2, x3, x4, where flipping all of the signs wouldn't change the output. I'll leave it to you to pause and ponder and think about how this could 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 of why mathematicians care about things like higher dimensional spheres, regardless of whether or not they exist in physical reality. It's not always about the sphere per se, it's about what other problems in math they can be used to encode.

---
*Источник: https://ekstraktznaniy.ru/video/16232*