Who Else!

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 this stuff as much as i do. so here's the puzzle that we're going to solve, the stolen necklace problem. you and your friend steal the 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 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 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 4 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 4 sapphires, each of you has 5 emeralds, 2 diamonds and 3 rubies. the claim, the thing that i want

to prove in this video, is that if you have n different types of jewels, it's always possible to find a fair division using only n cuts or fewer. so with 4 jewel types like this example, you should always be able to find a way to make 4 cuts and divvy up the 5 resulting pieces so that each thief has the same number of each jewel type. if

there were 5 jewel types, you should be able to do it in five cuts, no matter what the arrangement is. it's kind of 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 going to 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 going to land on top of each other once they hit the plane, and that's not really a big deal. the special fact that 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 exact opposite sides of the sphere which

land on each other during the mapping. points on the exact opposite side of the 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 poles, 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 lets you tweak this function a bit, maybe shearing it during the projection. 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 non tearing way to squash 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 mapped to the same temperature pressure coordinates. now, i imagine if you're watching this video you're probably a mathematician at heart,

and you want to see why this is true not just that it's true. vsauce actually taled 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 co-opt 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 going to 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 x-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 going to 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 x-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 going to make up some new closed loop around the sphere. this 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 word you and your antipodal sister by definition end up with the same x 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 going to swap places, there must be some point along the way where you also have the same y-coordinate, aligning horizontally. that gives the 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 want to 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 1. 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 going to help for where we're going. for any function that takes in points on the

sphere, triplets of numbers who squares sum to 1, 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 2 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 on 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 is a line with length one, with the jewels sitting evenly spaced on it. now divided up that line into 18 evenly sized segments, one

for each jewel. and rather than thinking of each tool 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, 8/18 of the line are going to be painted sapphire while, 10/18 of the line are going to 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 1/18 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 end up with a total length of 4/18 of sapphire colored segments and 5/18

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 1/18 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 1/6 1/3 and 1/2. 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 1 or if it goes to thief 2. now compare that to if i asked you to choose some arbitrary point on the 3d sphere. some point with coordinates (x, y, z) so that x

squared plus y squared plus z squared equals 1. well you might start off by choosing three positive numbers that add up to one. maybe you want x squared to be 1/6, y squared to be 1/3, and z squared to be 1/2. 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

the correspondence between points on the sphere and necklace divisions. for any point (x, y, z) that sits on the sphere, because x squared plus y squared plus z squared equals one, you can cut the necklace so that the first piece has a length of x squared the second has a length of y squared and the third has a length of z squared. then to choose how

to allocate these pieces, if x is positive give it to thief 1, otherwise give it to thief 2. if y is positive give that second piece to thief 1 otherwise give it to thief 2. and then similarly to allocate the third piece if z is positive give it to thief 1 otherwise give it to thief 2. 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 (x, y, z) on the sphere corresponds to some necklace allocation, what does the point (-x, -y, -z) 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 1 to equal that for thief 2. 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 1, and the total length of emerald belonging to thief 1. what we want to 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 2. or set a little differently, where swapping all of the pieces won't change those 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 to points on the (x, y) 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 want to solve the more general stolen necklace problem, one that has more than

just 2 jewel types. 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 a hypersphere 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 the squares equals 1. those are all of the points in 4d space a distance 1 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 (x1, x2, x3, x4)

where flipping all of the signs wouldn't change the output. i'm going to 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 going to try to show you what that might look like. but before that i actually have multiple announcements for you guys today. well i guess the first one is not really an announcement, i just want to say thank

you to the people making these videos possible on patreon, as always. but number 2, i just partnered with dftba to open a 3blue1brown store. so if you go check it out you can get a pause and ponder t-shirt, as well as three different fractal curve posters. and if things go well maybe we're going to add some more shirts, more posters and

potentially some little pleasure pi creatures. number 3, don't forget that mathologer just put out a video on a very different approach to a very similar fair division problem, so after the 4d sphere thing definitely go give him a look. if you don't already know about his channel, check out the rest of it. and finally, this particular video is

sponsored by the great courses plus. i imagine that many of you watching this channel, especially those of you who found it through the linear algebra series, are into binge learning on the internet, and the great courses plus has hundreds of lecture series where you can do just that. one that actually think you guys would like a lot is "the

inexplicable universe: unsolved mysteries" by neil degrasse tyson. i don't think i need to tell you what a great speaker neil degrasse tyson is, and the series itself does not disappoint. by going to the url on the screen, or more easily by just following the link in the description, you can get a one month free trial to see what i'm talking about.

alright, so here's that final animation. it's a little confusing, so for analogy on the upper left here i'm rotating 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?

Share this :