Welcome to another Mathologer video. Today is about a math story that made it into The New York Times something that's really very rare. It's about a familiar problem. A couple of friends, Ashwin, Bret and Chad want to rent an apartment. Now the rooms are quite different and the friends have different preferences, different ideas about what's worth what. Is there a way to split the rent and assign the rooms to the friends so that everybody is happy? It's really quite a tricky problem. Quite recently it was discovered that a very famous and very pretty result in abstract math can be brought to bear on this and many other related fair division problems. So my mission today is to sort all this out for you as best as I can. Let me know in the comments how I did. My favorite math channel is Grant Sanderson's 3blue1Brown. Now this week Grant and I have conspired to bring you videos about two very different fair division problems. If you like my video or even if you don't, check out 3Blue1Brown, Grant really does some wonderful work there. Alright let's start with this mathematical results, it's called Sperner's lemma and it's due to the mathematician Emanuel Sperner who published it in 1928. It's been awhile. In maths this pretty result comes up in all sorts of different contexts. So if you are in the know you might recognize some of these. Okay so here we go, take a triangle, any triangle and triangulate it, that means chop it into a network of little triangles like this, ... or like that We'll actually use a super-nice triangulation of an equilateral triangle for illustration. You all know this one, right? Important: everything I'll say will work for all other other triangulations, all other triangles. Color the corners with three different colors, red, green and blue. On the bottom edge randomly color every vertex green or blue like this. On the left edge randomly color every vertex red or blue, for example like this. The vertices on the right side are colored red and green. Color the vertices in the middle randomly, no restrictions apart from them having to be red, green and blue. Maybe something like this. Now, there are infinitely many ways to triangulate and infinitely many valid ways to color the vertices of triangulations and yet we can be absolutely, absolutely certain, and that's really what Sperner's lemma is about, that the corners of at least one of the little triangles in there feature all three colors. For example here's one. Now there can be more than one. For example, here's another one, and there's another one. But we can always be sure that there is at least one of them. So how do you prove something like this. Well, there's a really really nice proof. Think of this big triangle here as a house with the little triangles being the rooms. Every room is bounded by three edges. Let's say an edge is a door if it's two ends are colored blue and green like that one here. Now there's are lots of doors in here, so let's just highlight all of them. Here they are. Important: instead of making the blue-green edges the doors we could also have chosen the red-green edges or the red-blue edges as door. That would have given different sets of doors but the following argument stays the same for all these choices. Here are three important insights about the doors in our house. Let's start with a question: What are the possible numbers of doors in a room. Zero doors is definitely possible like this. Exactly one is also possible and if this is the one door here what can we say about the color on top? Well it cannot be blue or green because that would give a second door like this, or like that and so this means there's got to be a red on top right? And that means that the rooms that have exactly one door are exactly the special 3-colored ones. OK so that's pretty good already. Now as we've already seen two-door rooms are possible. They have either two blue vertices and one green, like this, or two green and one blue. But then once a room has two doors it's going to be one of these two types which means that three doors is impossible. So to summarize, a room has either zero, one or two doors and the ones with exactly one door are exactly the special 3-colored ones. Next, because of the restriction of what colors can go on the sides of the house it's clear that all doors on sides have to be along the bottom. We can also say something about the number of doors at the bottom namely there will always be an odd number of doors at the bottom, so 1, 3, 5, 7 etc. In this case we've got three. Why always an odd number of doors at the bottom? Well I leave this for you to figure out in the comments, actually pretty easy. Now we're ready for the proof that there will always be at least one of those special 3-colored rooms in our house. Let's enter the house through one of the doors at the bottom, here we go. Either the room we're in has exactly one door or exactly two doors. If it has exactly one door the room is special and we're done, we found a special room. Otherwise let's step into the next room via the second door. Again either we are in a special room and we're done or we can keep going and as we continue like this will never enter the same room twice. But then since the only finitely many rooms our trip must end either in a special room in which case we're done or we leave the house through a second door at the bottom. So far we've walked through two doors at the bottom , right, but since there's an odd number of doors at the bottom there's at least one more left over, at the bottom, that we have not passed yet. So let's reenter the house through one door like this, at the bottom. Again we'll never enter a room that we've already visited and so the second trip will also either end in a special room or another door at the bottom. So, going like this, going like that. Every time we end up outside we've used up an even number of doors at the bottom and since there's an odd number of doors at the bottom, we can always find a door to re-enter at this stage. Now obviously this cannot go on forever and therefore we eventually must end up in one of those special 3-colored rooms no matter how hard we try to avoid this. Isn't this a wonderful proof. Now there's a bit more: you can actually show that there's not only just one special room but an odd number of them. So, for example, in this case we've got three so maybe also see whether you can extend our proof in the comments to show this. Now, how can all this be used to achieve rental harmony. Let's say the rent is 500 dollars, Well it's obviously not New York City :) So then there are lots of different ways to split up the rent, for example, $100+ $200 + $200 or this one here or, crazy but or well it's just one rich guy paying for his friends. Now we turn the big triangle into a mathematical space of rent divisions. What this means is that every one of the points inside it will stand for exactly one of these possible divisions. OK let me explain.Take a point on the inside of this equilateral triangle here and add up the distances to the three sides. Now and this is really quite wonderful this distance sum is always the same in equilateral triangles. Red plus blue plus green is constant. This is called Viviani's theorem. So this distance sum is the same as that one here, it's the same as that one and it is the same as, well let's make red and green vanish by moving the point to the corner. So what this means is that our constant is really the height of the triangle. Now let's superimpose our triangulation. Using this special triangulation we can illustrate all its nicely. So the big triangle is five little triangles high: 1, 2, 3, 4, 5 So let's say the height is 5 units. Let's move the points. As you can see red is one unit long, blue is two units long and green two. And 1+2+2=5. Works. Try another one: red is zero, blue is 2 and green is 3. Works! In this way every point in the big triangle corresponds to exactly one of the possible ways to write 5 at the sum of three non-negative integers or, if we scale everything by 100, the vertices of our triangulation correspond to the different ways of writing $500 as sums of multiples of $100. For example, here we've got $0 + $200 +$300. Or, moving to a different vertex and maybe one more, like that. OK, now we somehow want to use Sperner's lemma to choose how we should split up the rent and who among the friends should move into which room and the friends should end up happy with all this. To do this we first label the vertices with the friends, like so. Now the letters are distributed in a regular pattern such that all three letters occur at the vertices of every one of the little triangles, like this little triangle there has ABC around it. That little triangle has ABC around it and really you can check, every other little triangle has ABC around it. Now let's look at one of the possible sums. $0 + $400 + $100. The corresponding vertex is labeled B, so let's ask Bret which room he'd go for if the rent was split up like this. Well the red room costs nothing and so it's reasonable to assume that Bret will go for the red room In fact, we'll assume that everybody who's offered a free room will go for it. OK, Bret goes for the red room, so we color this vertex red. Next vertex. The new vertex is labeled C so it's up to Chad to choose. Since red still costs nothing Chad also goes for this room. So in this way all the vertices on the left will all end up red. For the same reason the bottom edge will end up blue and the right edge will end up green. Now in a corner we've got two free rooms and in this case Ashwin will choose either one of them. You get the same sort of choices in the other corners. Now we fill in the rest by going to the middle, and in the middle there's no 0 here, so Bret can choose whichever of the rooms he likes best given this rent division, say he goes for red. Now we continue to fill in the rest and it looks like we may be able to somehow apply Sperner's lemma with all those colors. And we do if the choices in the corners lead to three different colors, for example like this. If this happens then we have a coloring to which Sperner's lemma applies, that it, we have a little 3-colored triangle, there we go :) How does this help with our problem? Well the way the corners are labeled ABC tells us that Ashwin should take the green room, Bret the red and Chad the blue. What about the division of the rent. Well the divisions corresponding to the vertices of the little triangle are very close, especially if we use a fine triangulation like this one here. Just in case you cannot see properly, the arrows point at the tiny special triangle that I've magnified up here. The three corners of this this triangle correspond to $120 + $150 + $230 dollars, ... that one here, and finally that one here. So the differences are in the ten dollar range and every friend was happy with this assignment of rooms there for one of these divisions, and so picking any of these three divisions randomly should work for all three friends. Now if some unhappiness persists finer triangulations will get the divisions to differ in arbitrarily small amounts. Now it's possible to use the same sort of ideas to come up with all sorts of other types of fair divisions. I've linked in the paper by Francis Su on which all this is based, as well as to link to the New York Times article which contains a nice apt to explore as well as a website that allows you to actually make real-life decisions based on this circle of ideas. A couple afterthoughts: all this also works if you're dealing with less or more than three rooms you just have to use lower or higher-dimensional versions of Sperner's lemma. I''m not going to go into details here. You may also have gotten the impression that all this is impractical because to color in a triangulation like this you have to ask the friends to make as many decisions as they are vertices, in this case it is more than a thousand. However, remember, when we looked for the special little triangles we only visited a very small part of the large triangle, so the idea is to color in the triangulation "on demand" as we walk around it. This will cut down on the number of decisions, and using some other refinements it's possible to reduce the number of decisions to something manageable as in the online app. One more thing: Remember, at this point of the story, choices at the corners either lead to three different colors, like this. Then Sperner's lemma applies directly. However, you can also end up with this sort of coloring here which is slightly different from a Sperner coloring because the corners of the big triangle don't feature all three colors. Can you explain how things have to be adjusted to save the day here? Again let's have some fun discussing this in the comments. And that's it for today. Now I'll go and have some rest but you should now go and explore a bit what other miracles mathematicians work using Sperner's lemma. For example, if you understood everything in this video you are actually on the brink of understanding the nifty proof of the famous Brouwer's fixed-point theorem that I've linked in in the comments. So have fun with that, too :)
https://www.youtube.com/watch?v=FhSFkLhDANA
The 3Blue1Brown video
Can Sperner's lemma be considered a part of Ramsey theory because no matter how you color the triangle with (R,G,B), you get at least one smaller triangles that has all 3 colors?