Pop Video: Who (Else) Cares about Topology? Stolen Necklaces and Borsuk-Ulam

Video Transcript

You know that feeling you get when two things that seem completely unrelated turn out to have a key connection. In math especially, there’s a certain tingly sensation that I get whenever one of those connections starts to fall into place. That is what I have in store for you today. It takes a little time to set up. I have to introduce this fair division puzzle in discrete math; it’s called the stolen necklace problem. And we also have to set up a certain topological fact about spheres that we’ll use to solve it, called the Borsuk–Ulam theorem. But trust me, seeing how these two seemingly disconnected pieces of math come together is well worth the setup.

And more fun, I coordinated this video with Mathologer, who just put out a video solving a very similar fair division problem, but with a completely different tactic. So after this video, if you’re eager to learn more, head on over to his channel. If somehow you don’t already know about Mathologer, his stuff is some of the best math on YouTube, definitely poke around the rest of the channel and subscribe if you like his stuff as much as I do.

So here’s the puzzle that we’re gonna solve, the stolen necklace problem. You and your friend steal a necklace, full of a whole bunch of very valuable jewels. Maybe, it’s got some sapphires, emeralds, diamonds, and rubies. And let’s say they’re all arranged on the necklace in some totally random order. Moreover, let’s say that there happened to be an even number of each type of jewel. Right here, I have eight sapphires, 10 emeralds, four diamonds, and six rubies. You and your friend want to split the booty evenly, with each of you getting half of each jewel type. Four sapphires, five emeralds, two diamonds, and three rubies each.

And, of course, you could just cut all of the jewels off the necklace and divvy them up evenly, but that’s boring. There’s not really a puzzle there. 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, I just did it using four cuts. If I give these top three strands to you and these bottom two strands to your co-conspirator. Notice how each of you ends up with four sapphires. Each of you has five emeralds, two diamonds, and three rubies.

The claim, the thing, that I wanna prove in this video is that if you have 𝑛 different types of jewels, it’s always possible to find a fair division using only 𝑛 cuts or fewer. So with four jewel types, like this example, you should always be able to find a way to make four cuts and divvy up the five resulting pieces so that each thief has the same number of each jewel type. If there were five jewel types, you should be able to do it in five cuts, no matter what the arrangement is. It’s kinda hard to think about, right? I mean you need to keep track of all of these different types of jewels, ensuring that they’re divided fairly. But at the same time, you have to try to minimize how many cuts you’re making.

Depending on your disposition to puzzles in math, maybe this feels a little contrived. But the core characteristics that make this problem hard. Like trying to minimize sharding and trying to allocate some collection of things in a balanced way. These are the kinds of optimization issues that actually come about a fair amount in practical applications. For the computer system folk out there, I’m sure you can imagine how this could relate to some kind of efficient memory allocation problem. Also, if you’re curious to actually see it in action. I’ve left a link in the video description to a certain electrical engineering paper that uses this very 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, we’re gonna take a seemingly unrelated sidestep to the total opposite side of the mathematical universe, topology. Imagine taking a sphere in three-dimensional space and squishing it somehow onto the 2D plane, stretching and morphing it however you want as you do so. The only constraint is that you do this continuously, which you can think of as meaning just never cut the sphere or tear it in any way during the mapping. Now, as you do this, continuously squishing that sphere onto the plane. Many different pairs of points on the sphere are gonna land on top of each other once it hits the plane. And that’s not really a big deal.

The special fact that we’re gonna 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 for 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, let’s say you’re thinking of the sphere as Earth and the mapping you choose is to just project every point directly onto the plane of the equator. Well, in that case, 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. Any other antipodal pair will end up somehow offset from each other. But let’s say you tweak this function a bit, maybe shearing it during the projection. Well, in that case, the north and south pole probably 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 any math educator introducing the Borsuk–Ulam theorem is 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. Think about it for a moment. Associating each point on the Earth with a pair of numbers, temperature, and pressure is the same as mapping the surface of the Earth into a 2D coordinate plane. Where the first coordinate represents temperature and the second one represents pressure. Also, each of those values varies continuously as you wander around the Earth. So this association is a continuous mapping from the surface of a sphere onto the plane, some nontearing way to squish that surface into two dimensions.

So what the Borsuk–Ulam theorem guarantees is that no matter what the weather patterns on Earth, or any other planet for that matter, some pair of antipodal points somewhere must land on top of each other. Which means they map to the same temperature pressure coordinates. Now, I imagine if you’re watching this video, you’re probably a mathematician at heart and you wanna see why this is true, not just that it’s true. Vsauce actually talked about the Borsuk–Ulam theorem in a great video that he recently did about fixed points. And he gave a really beautiful line of reasoning to explain it intuitively, which I’m just gonna shamelessly coopt for my own use here.

Given some function from the sphere onto the plane, imagine walking around the equator. The corresponding outputs on the plane are gonna form some kind of closed loop. And let’s say that your sister is on the exact opposite side of the globe. And as you walk around, she continues keeping herself perfectly antipodally opposite from you. Since the two of you eventually swap places, at some point along the way, the 𝑥-coordinates of your corresponding outputs have to line up. The first time this happens, I want you to mark where you are on the sphere, as well as where your antipodal sister is. Then if you tilt the equator slightly and walk along a slightly different great circle, the corresponding loop in the output space is gonna alter a bit.

But by the same line of reasoning, there has to be some point on your walk where you and your antipodal sister land on outputs with the same 𝑥-coordinate, lining up vertically. Mark those two points on the sphere as well. If you repeat this, continuously turning that equator 180 degrees around the full circle, your marked points are gonna make up some new closed loop around the sphere. Here is what that might look like in the output space, keeping track of all of the points where you and your antipodal sister first line up vertically. Every point on this new loop is one where you and your antipodal sister, by definition, end up with the same 𝑥-coordinate. So if the two of you are walking around this new loop, you always line up vertically.

But what’s more, since the two of you are eventually gonna swap places, there must be some point along the way where you also have the same 𝑦-coordinate, aligning horizontally. That gives a point where you and your antipodal sister must land on the same output. Pretty cool, right? To help set the stage for how the heck this applies to the necklace problem, I wanna write what this means a little more symbolically. Points in 3D space are represented with three coordinates, right? I mean, in some sense, that’s what 3D space is, to a mathematician at least, all possible triplets of numbers. Now, the simplest sphere to describe with coordinates is a standard unit sphere centered at the origin, the set of all points a distance one from that origin. Meaning, all triplets of numbers with the special property that the sum of their squares equals one.

So the geometric idea of a sphere is related to the algebraic idea of some set of positive numbers that add up to one, 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 the Borsuk–Ulam theorem is saying symbolically. This is gonna help for where we’re going. For any function that takes in points on the sphere, triplets of numbers whose squares sum to one, and spits out 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. And with that on the table, let’s turn back to the stolen necklace problem.

Part of the reason that these two things feel so unrelated is that the necklace problem is discrete. But the Borsuk–Ulam theorem applies to a continuous situation. So our first step is to translate the stolen necklace problem into a continuous version. For right now, let’s limit ourselves to the case where there are only two jewel types, sapphires and emeralds. And we’re hoping to make a fair division of the necklace after only two cuts. As an example to have upon the screen, let’s say that we have eight sapphires and 10 emeralds on the necklace. Just as a reminder, this means that the goal is to cut the necklace in two different spots and divvy up those three segments so that each thief has half of the sapphires and half of the emeralds. Notice how the top and bottom here each have four sapphires, and each have five emeralds.

Think of this necklace as a line with length one, with the jewels sitting evenly spaced on it. Now, divide up that line into 18 evenly sized segments, one for each jewel type. And rather than thinking of each jewel as a discrete indivisible entity on the segment, remove the jewel itself. And, instead, just paint that segment the color of the jewel. So in this case, painting the whole necklace appropriately, eight eighteenths of the line are gonna be painted sapphire, while ten eighteenths of the line are gonna be painted emerald. The continuous version of this puzzle is to now ask whether we can find two cuts anywhere on this line, not necessarily on these one eighteenth interval marks, that let us divide up the pieces so that each thief has an equal length of each color.

In this case, that means each thief should come up with a total length of four eighteenths of sapphire-colored segments and five eighteenths of emerald-colored segments. An important but somewhat subtle point is that if you can solve this continuous variant of the puzzle, you can also solve the original discrete version. To see why, let’s say that you do find a fair division but whose cuts don’t necessarily fall cleanly between jewels. Maybe it cuts part of the way through an emerald segment. Well, because this is a fair division, the length of emerald in both the top and the bottom group has to add up to exactly five emerald segments, a whole number multiple of the segment length. So even if the division does cut partially into an emerald segment on the left, it would have to also cut partially into an emerald segment on the right here. So that the total length can add up to a whole number multiple of the segment length.

What that means is that we can adjust each cut without affecting the division so that they ultimately do line up on these one eighteenth marks. Now, in this continuous case, where you can cut the line wherever the heck you want, think about all of the choices that go into cutting the necklace and allocating its pieces. First, you choose two different places to cut the interval. But another way to think of that is to choose three positive numbers that add up to one. For example, maybe you choose one-sixth, one-third, and one-half. That would correspond with these two cuts here. Anytime that you find three positive numbers that add to one, it gives you a way to cut the necklace, and vice versa. Then after you cut it, you have to make a binary choice for each one of those three pieces for whether it goes to the thief one or if it goes to thief two.

Now compare that to if I asked you to choose some arbitrary point on the 3D sphere. Some point with coordinates 𝑥, 𝑦, 𝑧 so that 𝑥 squared plus 𝑦 squared plus 𝑧 squared equals one. Well, you might start off by choosing three positive numbers that add up to one. Maybe, you want 𝑥 squared to be one-sixth, 𝑦 squared to be one-third, and 𝑧 squared to be one-half. Then, you have to make a binary 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 three positive numbers that add up to one and then making a binary choice for what to do with each one of them. That right there is a key observation for the whole video. It gives a correspondence between points on the sphere and necklace divisions.

For any point 𝑥, 𝑦, 𝑧 that sits on the sphere, because 𝑥 squared plus 𝑦 squared plus 𝑧 squared equals one, you can cut the necklace so that the first piece has a length of 𝑥 squared. The second has a length of 𝑦 squared, and the third has a length of 𝑧 squared. Then to choose how to allocate these pieces, if 𝑥 is positive, give it to thief one. Otherwise, give it to thief two. If 𝑦 is positive, give that second piece to thief one. Otherwise, give it to thief two. And then, similarly, to allocate the third piece, if 𝑧 is positive, give it to thief one. Otherwise, give it to thief two. And you can go the other way around; this is a one-to-one correspondence. Any way to divide up the necklace and divvy up the pieces would give you 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 using a geometric object. And with that association, we are tantalizingly close. Take a moment and think about the meaning of antipodal points under this association. If the point 𝑥, 𝑦, 𝑧 on the sphere corresponds to some necklace allocation, what does the point negative 𝑥, negative 𝑦, negative 𝑧 correspond to? Well, the squares of all of these coordinates are the same. So it would correspond to making the same cuts on the necklace. The difference is that each 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 between the two thieves.

Now, remember what it is that we’re actually looking for. We want the total length of each jewel type belonging to thief one to equal that for thief two. 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, the way you might move forward is to construct a certain function, a function that takes in a given necklace allocation and spits out two numbers. The total length of sapphire belonging to thief one and the total length of emerald belonging to thief one.

What we wanna show is that there must exist a way to divide the necklace with only two cuts and divvy up the pieces so that those two numbers are the same as what they would have been for thief two. Or, said a little differently, where swapping all of the pieces won’t change those two numbers for thief one. Because of this back and forth between necklace allocations and points on the sphere and because pairs of numbers correspond to points on the 𝑥𝑦-plane, this is in effect a mapping from the sphere onto the plane. So what the Borsuk–Ulam theorem guarantees is that some antipodal pair of points on the sphere land on each other in the plane. And what that means is there is some necklace division and allocation so that swapping the pieces between the two thieves won’t change the amount of each jewel that each one has.

That’s a fair division. That, my friends, is what beautiful math feels like. 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 we actually wanna solve the more general stolen necklace problem, one that has more than just two jewel types. Well, for that, we can use a more general version of the Borsuk–Ulam theorem, one that applies to higher-dimensional spheres. As an example one dimension up, Borsuk–Ulam also applies to mapping hyperspheres in 4D space into 3D space. What I mean by a hypersphere, the way to think about it, is all possible lists of four coordinates where the sum of their squares equals one. Those are all of the points in 4D space a distance one from the origin.

The Borsuk–Ulam theorem says that if you try to map that set, all of those special quadruplets, into three-dimensional space, continuously associating each one with some triplet of numbers. There must be some antipodal collision, an input 𝑥 one, 𝑥 two, 𝑥 three, 𝑥 four, where flipping all of the signs wouldn’t change the output. I’m gonna leave it to you to pause and ponder and think about how that would apply to the three-jewel case. And about what the general statement of the Borsuk–Ulam theorem might be and how it can apply to the general necklace problem. Needless to say, actually trying to visualize a 4D sphere mapping into 3D space is rather difficult. Nevertheless, for the final animation, I’m gonna try to show you what that might look like.

Alright, so here’s that final animation. It’s a little confusing. So for analogy on the upper left here, I’m rotating a sphere in three dimensions and projecting it into 2D. But I’m only showing the lines of latitude on that sphere and not shading it or anything like that. So, similarly in the center, I’m rotating a four-dimensional hypersphere in 4D space but projecting it into 3D space. But all I’m showing is the spheres of latitude, so to speak. Keep in mind, you don’t actually need to be able to visualize a 4D sphere mapping into three dimensions to be able to understand the Borsuk–Ulam theorem. Much less, how it applies to the stolen necklace problem. This is just for fun. But it is pretty to try, don’t you think?