| by Kenneth Chase | 100 comments

NYT: Sperner’s lemma defeats the rental harmony problem


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 🙂

100 Comments

Mathologer

Feb 2, 2017, 8:10 pm Reply

Make sure to check out 3Blue1Browns fair division video https://youtu.be/FhSFkLhDANA
And, as usual, please ask if there is something you don't understand 🙂

Sean Stanley

Feb 2, 2017, 3:37 am Reply

Both of you do an absolutely fantastic job of communicating the beauty of math, love your videos, never stop.

Y Qisq

Feb 2, 2017, 3:56 pm Reply

Random thought: if v(x) is a psychometric "value" function a person attach to the set of "physical features" x of the rooms (e.g. x =(size, lighting, …), and let w be the money the person pays, then a fair division could be defined as the case when the ratio v(x)/w for everyone being equal. The algorithm described in the video seems to be a pretty objective way to measure this "psychometric function" (maybe not very practical). Also I wonder if there is a continuous analog to this, like some sort of variational method for finding the optimal mapping M: [rooms]->[people, money].

Y Qisq

Feb 2, 2017, 4:00 pm Reply

Discrete maths can be pretty mind blowing

EmpowerDB

Feb 2, 2017, 5:41 pm Reply

Oh man, another color blindness fail. I know RGB is the classic three-color color mixing metric. But maybe next time you can use Red, Yellow, Blue?

Frank Underwood

Feb 2, 2017, 10:12 pm Reply

Is it possible to trick the method into getting a better deal by lying?

GAPDaTsar

Feb 2, 2017, 10:36 pm Reply

2:54  There should be Illuminatis instead of smilies.  XD

kennkong61

Feb 2, 2017, 11:47 pm Reply

I'm pretty good with mathematics, but am by no means a mathematician, so I'm sticking my neck out here.

Sperner's lemma appears to be one of those proofs that implicitly depends upon the axiom of choice. If the axiom of choice is not true, the proof fails.

In the rental example, the axiom of choice is true only if all three tenants are will to pay the full price themselves. Suppose that each of the three tenants has an unstated limit of $100 (if it were stated, they would know they couldn't afford a $500 apartment). Each one is hoping to be able to select the least desirable room within their budget. So while one or two of them might be able to choose a room, there is no way all three of them can. In this case, the axiom of choice is false (you cannot choose a single item from a set of three items).

Mads Nielsen

Feb 2, 2017, 6:49 pm Reply

"NYT" got me really confused, since that means "NEW" in my language …

Jonathon Chambers

Feb 2, 2017, 4:23 pm Reply

Ah, but suppose that one friend is a mathematician, economist, venture capitalist, eurogame player, and the other two are honest yet uneducated. What system could protect the weaker tenants from being exploited through false preferences?

deadmeat1471

Feb 2, 2017, 5:30 pm Reply

@Mathloger How does this relate to a nash equilibrium?

mumhustler

Feb 2, 2017, 10:46 am Reply

I like the math istself but this is a dumb way to split rent. Much more difficult than needed and I wouldnt even go to say it makes sense in real life! Just do YourRoomArea/AllRoomsArea x Rent – thats intuitive to "humans" vs autists ( and yes I like math but no this isnt sensible)

ザ・ワールド!

Feb 2, 2017, 4:27 am Reply

There is always an odd number of the "perfect" (RGB) triangles. I won't explain how there are always an uneven number of doors at the bottom.

As we know, there are always an uneven number of rooms. Using this knowledge, You know when you enter a door, it goes to a perfect triangle or exits another door. We won't be able to use that door anymore. If all lead to a perfect triangle, it's an odd amount. If one door leads to another door that exits, it will leave an even or odd amount. If it leaves an odd amount, we're fine. But what about an even amount?

So let's say there were 5 doors on the bottom. The first leads to a perfect triangle. The second exits out. So there are now 2 doors. There is 1 perfect triangle so far. If one exits out, there is 1 perfect triangle. If one leads to a perfect triangle, there is one door left and 2 perfect triangles. Since there is one door left, it's guarenteed to lead to a perfect triangle, as there is no other door. So you now have 3 perfect triangles.

Doug Rosengard

Feb 2, 2017, 4:38 am Reply

He says at 6:10 that if the path doesn't end at a special triangle it must leave leave at the bottom and not a different edge. He's right but I think this was a bit of a gap in the explanation because it's not necessarily obvious at face value why you can't leave on the right or left edges.

One way to prove this is to notice that once you start travelling through the doors the two doors will always be the same colors at each step. So if you start going through a blue-green door then all the doors you travel through will be blue-green. (If you suddenly went through a blue-red or green-red door then you were in a room that had all three colors and were done.) So your exit must be the same colors as the rest of the path, blue-green in this example. But since the outer edges all have distinct pairs of colors then the pair of colors of your exit uniquely determines the edge it is on (eg all the blue-green exits are on the bottom so if your exit is blue-green you left via the bottom edge.)

Other than that small quibble great video as always. 🙂

ElGringoCastellano

Feb 2, 2017, 6:12 pm Reply

My solution for the final question, about what to do if the vertices don't include all three colors, is to find the largest internal triangle that has three different colors for its vertices. Then lop off everything outside that triangle and use this smaller one instead.

Fernando Bastos

Feb 2, 2017, 1:29 am Reply

yes! fun! discussing… nope… didn't got it this time.

Diego Castillo

Feb 2, 2017, 3:52 am Reply

Even if mathematics had no application at all, I'd still be watching it as a beautiful construction… But not only that, but they're also really really usefull and even important in some areas… absolutely perfect

Username

Feb 2, 2017, 12:59 pm Reply

I actually used an online tool for this several years ago when I was sharing an apartment in Boston 🙂

Zum Spaß

Feb 2, 2017, 11:37 pm Reply

Hallo Herbert geiles Video!!

Leandro Lima

Feb 2, 2017, 1:53 am Reply

Great video!

John Adam Robert Hughes

Feb 2, 2017, 4:09 pm Reply

am i right?:

so it has to change from blue to green along the bottom from one primary node to the other and if there was even bridges the bottom and left and bottom right would have to be the same colour and we want them to be different colours, so they must be odd?

Steen Harsted

Feb 2, 2017, 4:11 pm Reply

Can the triangle also be used for negative numbers? If one of the rooms where so terrible to be in that its occupant would only stay there if he got money for staying in the room. Would there be anything from preventing you from placing the point "outside" of the triangle?
Also – Where is Guiceppe your camera-man?

Anon Ymous

Feb 2, 2017, 8:22 pm Reply

Is there a generalization of Sperner's lemma to n-simplices?

Romy Williamson

Feb 2, 2017, 9:29 pm Reply

I proved Viviani's Theorem in a cute way 🙂

Ahmad Bazzari

Feb 2, 2017, 12:22 am Reply

Great video as usual, very relevant to my situation, I'm renting with 2 other roommates (with 3 different types of rooms available in the house; size and features wise) what we do though instead of dividing the rent, we're rotating the rooms every couple of months. Keeping the rent divided equally.

gwho

Feb 2, 2017, 12:45 am Reply

what does coloring a vertex represent?

Bon Bon

Feb 2, 2017, 5:19 am Reply

Looks like PBS Infinite Series also made a video about the same thing:
watch?v=48oBEvpdYSE

Grant Trebbin

Feb 2, 2017, 9:09 am Reply

Hi, I was just wondering how you make your animations? I occasionally need to do one to explain something on my blog and haven't come up with a good solution. Love your work.

Adam Mangler

Feb 2, 2017, 3:09 am Reply

I couldn't believe it should be so diabolically obvious! Thanks!

Onward to Innisfree

Feb 2, 2017, 5:13 pm Reply

10:52 This is a significant assumption to make, as people may want to live in certain rooms, but disagree about how much they're worth. Just to illustrate that it's not rare or irrational to refuse a free room, suppose one of them has a baby, and only one of the rooms is suitable for that. In that case, they need a fair division but we can't expect the parent to take room that doesn't fit the crib (or whatever) even for free.

Ace shinigami

Feb 2, 2017, 10:12 pm Reply

It's cool to find out that you also like 3blue1brown, I also love his videos

VintageBreakfast

Mar 3, 2017, 6:52 am Reply

Unfair division. I know theres a fun brain game much like the triangle door game you created. It involves getting a line in each room and through each doorway one time exactly. In RESPONSE: If the roomates had different ideas in mind might they realize lack of fair division? Picking Red on top, green right and blue left would be a bias because of room size after all.

Dannyu NDos

Mar 3, 2017, 9:11 am Reply

If there are 4 people, I should use a tetrahedron, or if there are 5 people, I should use a pentachoron, and so on?

Siretch

Mar 3, 2017, 12:08 am Reply

You can take a math professor out of the classroom, but you cannot take the classroom out of a math professor…

Falk Heinze

Mar 3, 2017, 11:00 pm Reply

there has to be a room with 3 different colors because otherwise ( relating to the part at 4:43 ) there is no red in the whole triangle, wich cant be true because there are 3 colors

Bulhakas

Mar 3, 2017, 11:24 pm Reply

In the part where you explain the triangulated house with the doors and coloured vertices, I don't understand why we must always end up with at least one special room and an odd number of doors on the bottom. If the distribution of colours for each vertex is truly random, wouldn't it be possible to have cases where one colour shows up a lot more than the other two, for instance, or one colour is missing entirely even?

TheMasonX

Mar 3, 2017, 3:30 am Reply

I thought I saw a similar video pop up in my recommendations. Long time subscriber to both, but my viewing time wasn't high enough quality for engaged mathematical thought when I saw it haha

TheMasonX

Mar 3, 2017, 3:31 am Reply

If anybody has Chad's number, I'm looking for a roommate…

TheMasonX

Mar 3, 2017, 3:48 am Reply

As a programmer, I'm drawn to the parallels with pathfinding

TheMasonX

Mar 3, 2017, 3:48 am Reply

As a programmer, I'm drawn to the parallels with pathfinding

Debasish Ray Chawdhuri

Mar 3, 2017, 11:46 am Reply

The sum of the distances from any point to the sides is constant for all triangles, not just equilateral triangles. The proof is simple, just connect the point to the vertices and compute the area of the three triangles obtained (this half X the distance between the point and the side X the length of the side). The sum of the areas is the area of the big triangle and hence is constant.

frooshante

Mar 3, 2017, 9:28 pm Reply

love your videos. especially when you ad lib 🙂 #extemporaneous

Casa Xtreme

Mar 3, 2017, 9:01 pm Reply

ACAB

Steve Frandsen

Mar 3, 2017, 6:34 pm Reply

I really enjoy your explanations of real world issues. Thank you!

Chris Battey

Mar 3, 2017, 12:09 am Reply

Coming to this a bit late, but for the question at 15:00, assuming that the sides (other than the corners) are each completely one color: just consider the triangle without its corners. I.e. a hexagon with three short sides of one unit each and three long sides of n-2 units each; the nodes along the long sides are each a single uniform color, while the two nodes on each short side are different colors. There is exactly one door, on the side that is one unit wide and blue/green. (The lower right side, using the video's layout of the colors.) Entering that door and following the path to the end will get you to a tri-color room – no matter whether the corner you chopped off was blue or green. (If it was red for some bizarre reason, you have another tri-color room right there.)

Subhankar Ghosal

Mar 3, 2017, 6:13 am Reply

I could not understand the original problem statement. I understood the lemma mathematically, but unable to find out what was the application. Please elaborate little bit.

Stefan Reich

Mar 3, 2017, 4:55 pm Reply

10:03 "The friends should end up happy with all this."

Well: Nobody is happy when paying "rent".

Caffine Molecule

Apr 4, 2017, 9:08 pm Reply

But what if the random colouring made no red dots?

Anshee

Apr 4, 2017, 3:31 am Reply

Correct me if I'm wrong (I hope you'll read this), but for the last problem where two ends of the triangle have the same colour, would encompassing the triangle in a bigger one, where the sides are coloured the same way as the original one (bottom side all blue, left all red, right all green), and one of the two conflicting ends is randomly assigned the missing colour, actually work?
ugly Paint picture for better visuals (grey triangles are the ones added) http://puu.sh/vbY34/107c945f0e.png

Hope I can get a reply! Loved this video.

David Davison

Apr 4, 2017, 6:44 am Reply

Or you could do what you do with the dividing a cake problem.

Chorkaloopa

Apr 4, 2017, 12:17 am Reply

For "fairness" of splitting the rent, why not just 1/3 each? If they are doing it by room size, then why not by square footage? I'm just looking at it from the perspective of equality based on real world factors.

toenine

Jun 6, 2017, 3:59 pm Reply

"There are infinitely many ways to colour the vertices of each triangulation"…:thinking:

Unknown Entity

Jun 6, 2017, 8:29 am Reply

so THAT'S why my sims die when I remove all the doors to the house!

Sanket Thakare

Jun 6, 2017, 3:00 pm Reply

mate, where were u looking throughout the video

Dangn Abbit

Jul 7, 2017, 3:43 am Reply

I love this, but I also hate it. Without fail under these channels, I find some advanced and interesting mathematical problem that I've solved without knowing I had, or used as a method to some weird approximation. This has been going on for years now, with Wikipedia being the most powerful taste. Until they show up and I understand them, I could only assume that I'd thought of something batshit crazy to satisfy something less and moreso

Val

Aug 8, 2017, 4:55 pm Reply

If you have two corners of the same color, there can be an even number of doors in a side, which is bad.

Christopher Reid

Aug 8, 2017, 5:23 am Reply

This assumes that all tenants would prefer a crappy room for free than a great room for $10 (per week/month/whatever) which I don't think is true in general. For the corners, you can simply set the colour since your solution is likely to appear somewhere in the middle of the triangle. Jerry Nilsson's solution in the comments is much more effective, practical and logical!

coff81

Sep 9, 2017, 4:31 am Reply

This method assumes that people will always tolerate one room for any given distribution. Where it would run into trouble is if for instance if you could not pay more then $200 for any room and for some reason you hated the red room and would only pay $50 for it then posed with a distribution of $210, $210, $80 you wouldn't want to choose any of the rooms. If you were forced to just choose one you might have a preference but then if the algorithm landed in this triangle you wouldn't be happy. But there might be a different distribution where everyone was happy.

Joel Amunrud

Sep 9, 2017, 2:32 am Reply

I'm a little late to the conversation, but I think my solution to the problem at 15:00 where the corners are not three different colors is more elegant than what I've seen so far in the comments:
Even though we can't guarantee that the three corners will be different colors, we can know that they won't all be the same color. Two of the sides will have corners with different colors. One of these sides will have only two colors.
You can use the same door method to find the special triangle with the same reasoning-just make the side with two colors your new bottom and let those two colors indicate a door. You will have have an odd number of doors (only one in this case), and because the sides are all solid colors, it will still be impossible to exit on either of the other sides.

cOmAtOrAn

Oct 10, 2017, 12:14 pm Reply

Why there has to be an odd number of special (one-door) rooms:
Every door has to go somewhere. This means that special rooms either connect to the outside, or connect to a friend. There can be any number of two-door hallways over the course of the connection, but they don't really change anything.
So, doors that don't connect to the outside come in pairs.
Because the total number of outside doors is odd (as proven elsewhere in the comments), we can deduce that there is an odd number of special rooms which connect to the outside. This is because every outside door either connects to a special room, or connects to another outside door. That is to say, because outside doors that don't lead to special rooms come in pairs, and the total number of outside doors is odd, there must be an odd number of outside doors that connect to special rooms.
So, an odd number of outside-connected special rooms + an even number of inaccessible special rooms = an odd number of total special rooms.

Peepo

Oct 10, 2017, 12:29 am Reply

Yo, pass me the Sperner’s lemma triangle.
You better not calculate rent.

Gifford Metz

Nov 11, 2017, 4:43 am Reply

Interesting note: if at 13:06 each person found $10 to be a non-negligible difference, none of the three rent divisions will be a condorcet winner (http://en.wikipedia.org/wiki/Condorcet_criterion) ; I.E. if all three people voted between each pair of two of the three alternatives, no rent division would ultimately win. Explained another way, each division would win against another division but lose to the other division, like rock-paper-scissors.

manoj Cheera

Nov 11, 2017, 6:45 am Reply

what about zero doors at bottom?

Connor Mcnally

Dec 12, 2017, 4:49 pm Reply

Wouldn’t this work for all polygons? After all, they can be split into triangles as well.

Sponzibobu

Dec 12, 2017, 6:01 am Reply

I'm moving out if any of my housemates starts drawing triangles with crayons.

poiewhfopiewhf

Dec 12, 2017, 4:49 am Reply

THIS IS SO COOL!!!!!!!

教主蓝教

Jan 1, 2018, 8:26 am Reply

i have been thinking about how to integrate 1/[4-6(cosX)^6] , x/[4-6(cosX)^6] or x^2/[4-6(cosX)^6] ,or in general term x^n / a-bsin^6X as a whole. Please help… Thanks.

Zoolooman

Jan 1, 2018, 3:10 pm Reply

I know this is an old video, but I sat down this morning and played around with drawing patterns until I was forced to create a special room, and it was fascinating to see what patterns could form around a vertex which made it impossible to mark the triangulation without creating at least one special room.

When you're drawing patterns, it's "obvious" that the conditions of Sperner's lemma would have to be violated to create a triangulation with no special rooms, but I wasn't able to come up with a way to express why. What kind of mathematical language am I missing that would let me express thoughts generally for any triangulation?

For example, if the boundaries are set up like this, then somewhere in the pattern, I'll end up with a hexagon that has 6 vertexes containing at least one of each color, and thus no matter what I color the final vertex, I'll create a special room.

If I could change the corner or the edge rules, I could push my pattern to avoid special rooms, and the vertex I'd create that violated Sperner's lemma would be like… an extra one of that color? More of that color than I could otherwise have in Sperner's lemma? I feel like in some sense, the count of the number of the colors is what the lemma restricts.

I may be wrong, but I don't see a way to rearrange a "count" of colors that matches a valid lemma pattern that avoids special rooms. Alas, my imagination fails here because I have to get to work.

Great video, Mathologer!

Tobias Wilfert

Feb 2, 2018, 2:35 pm Reply

What about dividing by 3?

Tobias Wilfert

Feb 2, 2018, 2:39 pm Reply

Just saying: Using this as back backpropagation could lead to interesting stuff.

Alice

Mar 3, 2018, 10:20 am Reply

Actually, some part through the video I thought the problem was going to use other kind of data/decisions, so I figured I might as well post it here.

The decisions – each friend estimates how much rent they're willing to pay for each room, to the total sum of 500$.
The ouput – happiness of each friend, defined as friend's perceived worth divided by the rent they end up paying; if the paid rent is 0, the happiness is assumed 1 for 0 perceived worth and +infinity for positive perceived worth.
The problem:
– easy version – assign friends and rents to rooms to have each friend with at least 1 happiness
– harder version – maximise the minimum happiness (the happiness of the least happy friend)

My hunch tells me that applying coloured triangles and Sperner's lemma (with per-vertex decision being based on maximum happiness) would yield results close to the harder version solution (the closer the finer the triangle is). The tricky part would be with perceived worths of $0 (making a free room not immediately desirable).

enkii82

Mar 3, 2018, 10:52 pm Reply

i love you!!

Austin Bryan

Mar 3, 2018, 12:37 am Reply

But what if the top dot is red, the right dot is green, and all the other dots are blue? They'd be only one door to enter so we wouldn't leave, but we would never find a room with the three colors so we''re gonna be wondering around forever. The intial argument only works if you pretend like the latter isn't an option which it is.

Andy Hanson

Mar 3, 2018, 6:38 pm Reply

I notice that the result is base on a sequence on which anyone of them will decide the point. How do we decide who will decide first? So, if the triangle is big enough, the rent will be close to 1/3. I feel that it will become and endless debate? How sure are we that, the out come will be the same each time they repeat the selection all over again…?

Ilia Kalistru

Apr 4, 2018, 8:24 pm Reply

They also can find a happy triangle with $100 division and then make another triangle inside the first one to divide the rent finer. Recursive Sperner's triangles.

bejoscha

Apr 4, 2018, 10:40 am Reply

Depending on the ´door´ one starts with, one would end up at a different final split, right? So there is not necessarily a unique solution. How can this be solved in a real world decision situation? (Say there are N different solutions, but the people can not agree on which one to favour?)

Adevid Linares

Jun 6, 2018, 8:30 am Reply

Ain't the green and the blue inverted in the solution?–> C should be A and viceversa????

Matthew Grimshaw

Jun 6, 2018, 6:53 pm Reply

A simpler solution utilizing Viviani's theorem, but sidestepping Sperner's lemma:

Ask each room mate to divide the total cost among the rooms according to her preferences. These three points constitute a (possibly degenerate) "preference" triangle within the larger "total" triangle. Label each corner of the preference triangle with the name of the person whose preferences it represents. Since each corner of the total triangle would represent perfect preference for one room, i.e. two of the coordinates a,b,c would be zero, proximity to the corners of the total triangle can be used to assign rooms to room mates. For example, if Alice's corner of the preference triangle is closest to the Red room, then she values the Red Room more highly than Bob or Charlie, so we assign that room to her. Any point within the preference triangle would satisfy her, as each point within the triangle represents a cost for her room not greater than the value she assigned herself. If the preference triangle is degenerate, meaning that at least two room mates agreed on the values of all three rooms, then any choice of room assignment at the agreed values would satisfy both, and a choice can be made at random. Note that the larger the preference triangle, the more disagreement between room mates on the relatives values, and better deal each room mate will get relative to his own evaluations. The worst case would be when all three room mates agree on the values of all three rooms, in which case each pays exactly the amount for the (randomly assigned) room that she assigned, and not less.

This approach is probably less interesting mathematically, but is, in my opinion, more practical.

Jeremy Siegel

Jul 7, 2018, 2:58 am Reply

The number of doors on the bottom of the triangle must be odd for any number of points along that side of the triangle because an even number of doors could only occur if the bottom two corners have the same color. So long as the two corners are not the same color (as is postulated here), the progression of points from one corner to the other must include at least one pair where two adjacent points are not the same color. And if it includes more pairs of adjacent points that are not the same color, the number of such additional pairs must be even in order for the progression to end on the proper color. This means the number of doors must be the one required door plus some number of pairs of doors, meaning the number must be odd.

Wai Shing Tseung

Jul 7, 2018, 12:17 pm Reply

5007dtdtdpa=5÷djdpatgat×67xmw

darcipeeps

Aug 8, 2018, 2:57 am Reply

I’m super confused

Dark Inferno

Aug 8, 2018, 6:34 pm Reply

MIND = BLOWN!

Samira Peri

Sep 9, 2018, 2:25 pm Reply

RED RUM

M. A. Malcolm

Oct 10, 2018, 4:34 pm Reply

Superpi!!!!!!!!!

0x0

Oct 10, 2018, 11:51 pm Reply

If you divide the triangle infinite times do you get the true fair division at the cost of having to label infinite points

Emanuele Cerri

Nov 11, 2018, 10:15 pm Reply

Perfect, as usual

pratherat

Nov 11, 2018, 1:23 am Reply

Where can I buy that shirt? I've found similar online, but none quite as cool.

David Eikeland

Nov 11, 2018, 5:14 pm Reply

What if a triangle had 3 blue and 1 brown corners?

Bob Bobson

Mar 3, 2019, 8:00 pm Reply

But if there’s more than one triangle with all three colors, how do you determine which one is best?

Bradley Kenney

Mar 3, 2019, 4:30 am Reply

Just swap the colour with one of the other coloured dots to make three different colours.

debblez

Mar 3, 2019, 10:17 pm Reply

Can someone explain how we know the path through will never go to the same room twice?

CeeCeeLemons

Apr 4, 2019, 12:36 pm Reply

What if you tried making “walls” connecting same-colors? Red-red, blue-blue, green-green

Any triangle would then have either 3 walls (completely blocked) one wall (straight through) or no walls (fork)

You could then start at any opening and travel through until you reach a fork, or until you reach an exit in which case you find a new opening and start again

You’ll never get caught in a dead end because it’s impossible to have a two sided triangle if you connect all same colors, since you would have to connect the third side. You would either continue to pass straight through until no openings remain, or find a fork

Not certain if this will work, it’s just my immediate thought

Tom Fields

Apr 4, 2019, 2:30 pm Reply

Question
@ 6:02 –

Need to clarify "[we] will never enter the same room twice".

Is this because we can't? If so, why can't we?

Or is this because we choose not to? If so, can we avoid this?

spawn142001

Apr 4, 2019, 6:10 pm Reply

I dont understand how this takes into account the roommates preferences at all. What about the size of the rooms etc the income of each roommate? I dont get where any of the preferences came into account and if they never do then shouldn't a fair division amongst 3 always just be 166 or 1/3 of 500? It seemed that at certain points we just assumed the only thing each roommate cared about was if there was a cheaper room, then a person would always pick that room. But This seems arbitrary, wouldn't the other two roommates be unhappy that they got more expensive rooms? Again i dont see where any other preferences were taken into account. So if any roommate would always pick the cheapest room and thats the only thing we would care about in determining this, then all 3 roommates would end up settling for 166$

Further more, i get that every triangle is always made up of all 3 roommates but for example if you take the top triangle which is ABC you could switch the bottom two vertexes and get ACB which would end up moving around the rest of the vertexes in the overall triangle but wouldn't this lead to a different triangle with all 3 choices leading to a different agreement on how to split the rent?

The math here is beautiful but i am 100% failing to understand how this connects to a fair division of rent based on preferences when we never ever considered any preferences? Im about to watch this video again, see if i missed something obvious.

Matt GSM

May 5, 2019, 9:02 pm Reply

Well Chad is a Chad so he's going to Chad up on the Betamales

Baruch ben Avraham

May 5, 2019, 8:09 am Reply

There is an easier soution where each person pays a proportional amount based on the proportional room size.

Baruch ben Avraham

May 5, 2019, 8:10 am Reply

Where do you buy your shirts? I'm interested in buying a couple I've seen you wear.

Senso Crítico

Jul 7, 2019, 8:43 pm Reply

Mathologer, what if instead of 3 rooms and 3 people, the division was something like: 2 people and 10 different house tasks? Can this system be tweaked in any way to find a fair number?

Michael Lubin

Jul 7, 2019, 10:10 am Reply

12:39 If this is New York, that big triangle probably wouldn't even fit into one of the apartments.

Michael Lubin

Jul 7, 2019, 10:33 am Reply

I got it, I got it, I got it! If the three corners are not three different colors… you move to a different apartment building.

Is that mathematically elegant or what?

Leave a Reply