Using topology to solve a counting riddle | The Borsuk-Ulam theorem and stolen necklaces

Video Statistics and Information

Video
Captions Word Cloud
Reddit Comments

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.)

👍︎︎ 164 👤︎︎ u/theadamabrams 📅︎︎ Nov 18 2018 đź—«︎ replies

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?

👍︎︎ 36 👤︎︎ u/skaldskaparmal 📅︎︎ Nov 18 2018 đź—«︎ replies

One of the highest quality youtube channels in existence felt they needed to replace one of their videos. That's dedication.

👍︎︎ 28 👤︎︎ u/terdragontra 📅︎︎ Nov 18 2018 đź—«︎ replies

What was the mistake of the original video?

👍︎︎ 18 👤︎︎ u/Probable_Foreigner 📅︎︎ Nov 18 2018 đź—«︎ replies

What happens if there are more than two thieves?

👍︎︎ 11 👤︎︎ u/Toku95 📅︎︎ Nov 18 2018 đź—«︎ replies

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.

👍︎︎ 1 👤︎︎ u/laxatives 📅︎︎ Nov 18 2018 đź—«︎ replies

now I know it's not pronouced anti-pod-al

👍︎︎ 1 👤︎︎ u/_00__00_ 📅︎︎ Nov 19 2018 đź—«︎ replies

It's awesome... Love maths :)

👍︎︎ 1 👤︎︎ u/BrandonBattye 📅︎︎ Nov 19 2018 đź—«︎ replies

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?

👍︎︎ 1 👤︎︎ u/souldust 📅︎︎ Nov 19 2018 đź—«︎ replies
Captions
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.
Info
Channel: 3Blue1Brown
Views: 707,949
Rating: undefined out of 5
Keywords: Mathematics, three blue one brown, 3 blue 1 brown, 3b1b, 3brown1blue, 3 brown 1 blue, three brown one blue, borsuk ulam, borsuk ulam theorem, stolen necklace problem
Id: yuVqxCSsE7c
Channel Id: undefined
Length: 19min 21sec (1161 seconds)
Published: Sun Nov 18 2018
Related Videos
Note
Please note that this website is currently a work in progress! Lots of interesting data and statistics to come.