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

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

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. Let's start with the puzzle we're going to solve.

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

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,

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.

no matter the arrangement, and so on. It's 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,

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 optimization issues that 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.

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?

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 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,

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

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.

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

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.

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,

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

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,

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.

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.

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.