NYT: Sperner's lemma defeats the rental harmony problem
Вставка
- Опубліковано 9 лют 2017
- TRICKY PROBLEM: A couple of friends want to rent an apartment. The rooms are quite different and the friends have different preferences and different ideas about what's worth what. Is there a way to split the rent and assign rooms to the friends so that everybody ends up being happy? In this video the Mathologer sets out to explain a very elegant new solution to this and related hard fair division problems that even made it into the New York Times.
Featuring Sperner's lemma and Viviviani's theorem.
Check out 3Blue1Brown's video on another fair division problem here: / @3blue1brown
Francis Su's article in the American Mathematical Monthly on which this video is based lives here www.math.hmc.edu/~su/papers.d...
You can find his fair division page here
www.math.hmc.edu/~su/fairdivi...
To find the New York Times article "To Divide the Rent, Start With a Triangle" just google this title (the url is ages long and I don't want to reproduce it here).
The NY Times fair division calculator.
www.nytimes.com/interactive/2...
A proof of Brouwer's fixed-point theorem using Sperner's lemma www.math.harvard.edu/~amathew/HMMT.pdf
Enjoy :)
P.S.: One more thing you can think about is the following: how can what I show in the video be used to prove Viviani’s theorem.
Make sure to check out 3Blue1Browns fair division video ua-cam.com/video/FhSFkLhDANA/v-deo.html
And, as usual, please ask if there is something you don't understand :)
I know this isn't related to the video but what is your intro song?
Some random clip from the library of free tunes that UA-cam provides. Having said that a lot of people have commented that it reminds them of Kate Bush's Babooshka :)
I was just checking the proof of Monsky's theorem, and now I have a beautiful video to explain Sperner's lemma for me. Very nice!
Thank you.
+SleepingUnderable I am actually pondering whether I should also turn Monsky's theorem into a video. It's really a wonderful proof. Some of the generalizations are also fun :)
First VSauce and now Mathologer - 3B1B really is getting some well deserved attention
Yes, 3B1B is simply amazing :)
Parzival Before watching this video, I just watched some 3B1B stuff and thought about that also VSauce recommended them. And now this 🤔😄 BTW I really appreciate your videos Mathologer. Every time I finished a video of yours, I can't wait to watch a new one. Keep up that great work. ✌️️greetings from Germany 🇩🇪
3B1B has gotten almost as big as mathologer after the vsauce video
That's what people said about Kursega... Kursgesgts... Oh, you know who I mean.
Vedvart and they changed it eventually.
"So what are you doing with that weird triangle?"
"I'm calculating rent.
Don't lie to me, young man! It's one of those stupid board games you play all days again! What do they call it? Matticks? Yeah, something like that... So STOP IT, and go to your room! You're grounded!
Ehh.. all those problems geniuses have with stupids... :q
;)
or better yet...
Leonard: "What are you doing with that Sperner's lemma triangle?"
Sheldon: "As per Section 1 of the roommate agreement, I'm calculating rent."
The writers of that show wouldn't have a clue.
Ahahaha
@@mangeurdecowan titties
I just realized that if all 3 rooms are exactly the same and the roommates want to minimize rent, this would lead to the triangle being split into 3 equal triangles of red, green and blue color. The only multi colored room would be in the center, leading to all 3 people paying 1/3rd of the rent.
good observation
1:08 *Music to my ears!*
So satisfying to hear "Sperner" pronounced "Schperner"!
PlayTheMind He _is_ German himself, so I'm not surprised, but yeah.
Schhhhhhhperner. Did you feel it?
+PlayTheMind :)
mathologer where are you from? i kinda think like i´m hearing a german accent (or at least perfect pronounciation of german words)
+Metalhammer1993 Yes, I grew up in Germany but have been living in Australia for more than 20 years :)
I will keep all this in mind if I ever have to split rent with a bunch of robots.
Give it a few decades ;)
A couple years ago, I had the pleasure to see Francis Su give a talk about combinatorial fixed point theorems and fair divisions, and this was one of the things he went through. Good to see it on your channel (and a mention of Francis Su too!).
Also, glad to see you collaborating with 3Blue1Brown. I consider you two to be the best mathematics channels on UA-cam at the moment.
Thanks for the video!
Both of you do an absolutely fantastic job of communicating the beauty of math, love your videos, never stop.
why always an odd number of doors on the bottom:
you start with 1 door
every time you split it:
-if it is a door it turns into a door and a non-door (BBG or BGG) (this doesn't change the number of doors)
-if it is a non-door it turns into 2 doors or 2 non-doors (BBB, BGB, GGG, GBG) (this doesn't change the odd or evenness of the number of doors)
so the odd/ evenness of doors never changes so it stays odd.
Yep, that works :)
Nice. I did it by induction on the number of points. I'll post that as a separate comment to avoid clogging up your thread.
I did it by walking from left to right and recursive application of two lemmas:
Lemma 1: There’s odd number of doors between blue and green points.
Lemma 2: There’s even number of doors between green and green points.
Proof of Lemma 1: We start at a blue point. The next point is either
1) blue in which case the problem is reduced back to L1; or
2) green in which case there’s a door and based on L2 additional even number of doors for a total of odd number of doors.
Proof of Lemma 2: We start at a green point. If that’s the end, there’s zero (even) number of doors. Otherwise, the next point is either
1) green in which case the problem is reduced back to L2; or
2) blue in which case there’s a door and based on L1 additional odd
number of doors for a total of even number of doors.
Now, from Lemma 1, there’s odd number of doors between blue point on
far left and green point on far right. ∎
I simplified this a bit. Assume that A is blue and B is green. You start with an even number of doors (0). Start walking from A to B. You will eventually reach a green point (B is green, you're guaranteed at least 1) Now there is an odd # of doors. If there's no more blue points, you ends with an odd # of doors, otherwise walk to the next blue point and you're back to an even # of doors. The fact that n,n+1,n+2... alternates even, odd, even etc. is used.
Rename this A! and repeat the process to find A!!, A!!!, A!!!! etc. There is an even number of points between any 2 consecutive A's. Eventually you will run out of blue points (Suppose A? is the last blue point) Then the remaining points are green and you have 1 door in A?B. Totaling the # of doors, you get 2+2+2+...+1=2n+1=odd number of doors.
Parity: each door toggles the colour, so each pair of doors restores the colour, so any stretch with an even number of doors is the same colour at both ends. The edge is different colours at each end, so it can't have an even number of doors.
This would work very efficiently if done recursively. Start with the big triangle, split into four sub-triangles. Evaluate the opinions at the new vertices introduced. One of the triangles must be “special” by your proof. Rinse and repeat on the special triangle until everyone feels it is “good enough” and you can stop.
Love your videos, thanks to all involved.
That is one of the most beautiful proofs I've ever seen, and wonderfully illustrated. Thank you.
I'm having a problem with "you never enter the same room twice." On a particular trip, this is true because you use up a 2-room with entry and exit, but on another trip, why can't you suddenly find yourself in a room from a previous trip? Well, it's because if that ever happens, the 2 paths must be identical (though possibly in opposite directions). So that's why, but it needed to be said.
Jim Baumbach The two trips can't be identical as each starts from a unique bottom door.
You can just create equivalence classes with the equivalence relation aRb if a and b share a door, then do the finite closure (i.e. aRb if there's a sequence of rooms relating to each other). From the two-door max property you conclude that an equivalence class is just a list, the ends must be either one-door rooms either two-door room (hence on the border).
Cheong Ziyong that's not enough justification. The two "end" doors of a trip through the triangle are obviously different, therefore starting trips from them still respect your condition of "unique" doors. You need a more restrictive condition, i.e. start from a door not yet used. :-B
Hmm, for each edge that only features one color (causing the three outer vertices to contain a duplicate), you can embed the triangle within a larger triangle (eg. "triforce") that establishes *negative* rent for each room at the extremes. If the larger triangle fails to resolve the problem, then process is repeated to make each room increasingly enticing. That presumes that at some point someone's paid enough to accept an unfortunate room (eg. paid $100 per month to sleep on the couch), even if it's deadly (eg. $10,000,000 per month to sleep in radioactive waste).
Negative rent, I like it :) Actually this negative rent idea has been considered in the literature (some people subsidising their friend). However in this setup you don't need to go to such extremes to guarantee the existence of one of the special rooms.
Why would anybody even want to share apartment with someone who pays negative share of rent? You would rather leave one room unoccupied than subsidize person living in it, wouldn't you?
Ok, you made some valid points, although I doubt in real life anybody would pay someone to share an apartment. Even in your examples I would argue that you're just letting that person stay for free and you actually pay him/her for cleaning common area or partying with you etc.
There are two assumptions that can cause the system to fail in the real world even though it works on paper.
The haunted rooms scenario is "solved" on paper because of the (false in the real world) assumption that, regardless of other conditions, people will prefer free board over paying any sum of rent. This assumption means that even if all the interior triangles are the same color, there will still be a special triangle adjacent to one corner.
Another assumption that can fail in the real world is that each person is willing to pay up to the full rent. In reality, you can end up with a special triangle that sets an individual's share above what they are willing or able to pay. (That doesn't even get into getting upset over the divisions.) This is even a reasonable real world case, considering money concerns can easily be the driving force in people seeking shared rent.
My wife pays negative rent.
I really enjoy your explanations of real world issues. Thank you!
12:39 If this is New York, that big triangle probably wouldn't even fit into one of the apartments.
What a fascinating proof! Nicely explained, too! :-)
You have an awesome channel! keep up the good work!
Wow, beautiful proof Burkard! Thx for sharing this.
Graph theory explanation of odd bottom doors:
Think about blue and green dots as nodes and the doors as links. Since you must end on the opposite color (opposite side of the triangle) there has to be an odd number of links because you don't finish at the starting node.
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.
What if your roommate jizz in the room?
Could you do something about Integrals some day, maybe? I would love to learn about it through you! Thanks, man! I love your videos.
Wow! great topic!! :O Thanks!! I love mathologer Chanel
This is a wonderful explanation of Sperner's lemma!
It's cool to find out that you also like 3blue1brown, I also love his videos
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
I think the lemma works for two corners of the same color, to prove it you have to begin your journey into the house through one side that has two different colors, and then you're guaranteed to have an odd number of doors and thus can always find your special room
Odd number of doors on that side... But also an odd number of doors on another side, leading to an even number of doors on the entire perimeter. If the path leads straight through the triangle and exits on that other side, there might not be a solution
I actually used an online tool for this several years ago when I was sharing an apartment in Boston :)
Did it work for you ? :)
There are an odd number of special rooms reachable through the doors at the bottom. This is because there are an odd number of doors at the bottom and the doors which do not lead to a special room exit through a different door. So the doors at the bottom that do not lead to a special room occur in pairs and the remaining odd number of doors at the bottom each lead to a special room. There remain (possibly) some special rooms that are not reachable from a bottom door. Leaving through the door of such a room will enter a corridor of two-door rooms. The only exterior doors are at the bottom and by assumption our corridor does not lead there. It must therefore end at another special room so the special rooms not reachable from a bottom door are also paired and therefore even in number. The total number of special rooms (odd plus even) is odd.
7:49 omg I thought my screen broke :)
DanJan09 why?
I didn't even notice that…
TacoDude314 Look at Burkard's chest on the right (our left). There's a ( on the screen.
Noel Goetowski oh haha thanks
Oh weeeeird
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
:)
Your videos are awesome as always!!! Would recommend a color blind version for the red and green colors!
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.
Instructions unclear: Left a diagram of a coloured triangulation in my landlord's mailbox.
A very nice example of how mathematics can help people in real-life situations :>
This video is why I love the internet.
I didn't know the name of the guy behind ThreeBlueOneBrown
Regarding the task at 15:00, neither of the corner triangles can have three different colors. That means swapping corner colors does not make the solution disappear and that in turn means there must be a solution, the same one as for triangle with corner colors swapped to have three different corners.
And since for each color combination there is exactly one "door" on the perimeter of the triangle, we don't need to change anything on it to go searching for the solution, we only need to choose which color combination we consider the "door".
> And since for each color combination there is exactly one "door" on the perimeter
i think if two corners are the same, there can be an even number of doors on that side, but there must be a side with an odd number of doors for the same reason there can't be three doors on a triangle segment if not all three corners are the same colour. if for some crazy reason one of the people would prefer a room even if there was a free one on the table, then this wouldn't necessarily work.
Kasuha said everything that needed to be said in the first paragraph. If the three corners are three different colors, there is at least one special triangle in the array. Changing one or all of the corner colors doesn't change that because none of the corner vertices are a vertex of a special triangle.
From a practical perspective that's all we need to know. From a theoretical perspective, it tells us that as long each of the sides is monochromatic in a different color, the corner colors are irrelevant.
lifeinsepia, there is exactly one "door" for each color combination on the perimeter of the whole triangle. By choosing different color of the corner vertex, you don't change number of doors, you just change on which side of that triangle the door is.
Not exactly, since you change the position of the doors. Its all about the number of doors on the perimeter. That must stay odd otherwise it won't work. In this case the number of doors on the perimeter remain odd so the principle still holds.
I think this is false, consider all the colors are red except where they need to be green (right edge) and blue (bottom edge) and the bottom right corner is blue, there is no tricolor triangle. this indicates a problem with the resolution of your triangulation. For example if the red room were valued above T-r where T is total cost and r is the cost different across an edge.
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.)
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.
Well, if you colour the corners well, i.e. all different, then we already concluded a special triangle exists. But it can't ever be one of the triangles in the corners, since, for each one of them, there is a color none of it's corners can have. So the colours in the corners don't matter and independently of them, there exists a special triangle.
I forgot that this is under the assumption that the triangle isn't split up in the trivial manner, with which I mean that you split it up in 1 piece. Can't really call this splitting up anymore though. But this is useless to consider anyways, since you want to split it up as much as possible to get the best approximation.
This is really beautiful!
Mathologer: How do you make your graphics / animations? What software do you use to make these videos?
Krishan Bhattacharya try "Processing"
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.
When me a two friends had to split up three rooms. We simply bid on them one at a time. The highest bid would "win" the biggest room and then the remaining two people would bid on the next biggest room. This seemed to work pretty well.
That seems like it would work well when everyone agrees on which rooms are best. But it might not help decide on a fair rent if you had different preferences. (E.g., biggest room vs. most windows vs. private bathroom.)
I couldn't believe it should be so diabolically obvious! Thanks!
:)
It's interesting that the triangles (and i mean all the sizes) either have the same letter on the corners either they have ABC, which is pretty cool
My high school geometry book has viviani's theorem as a difficult problem and I am proud to say I proved it :). Though it first asked to prove that the sum of the distances of a point at the base of an isosceles triangle from the sides is equal to one of its heights. Fun problem indeed!
Great :) Actually, if you have a close look at what I do you can discover another proof based on these sort of special triangulations that I am working with (basically it's obvious that the distance sum does not change when you move from on vertex to an adjacent vertex, ... :)
That's a pretty nice way to get an intuitive understanding of the theorem! As always great video!
MIND = BLOWN!
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?
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!
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.
So if I understood that right, it's like a computable system to do an auction like process for dividing the worth of multiple things depending on how much they are willing to pay and distribute it evenly? Neat
Where did you get that shirt? I'm having trouble finding that design online.
Did you and 3B1B coordinate to release videos at the same time?
I was so happy to see two of my favorite channels post at once :D
Yes, Grant and I coordinated to release these videos at the same time :)
I’ll take a wild guess that you haven’t watched the videos yet.
My guess, why the corners aren't important to make sperner's result work, is, that you only need the chosen colouring of the outer edges. It's a much more special situation than the one in sperner's lemma, because there will be exactly one side, which has exactly one door in it. It depends on wether the bottom right corner is green or blue. This enables us, to continue with the proof as in sperner's lemma, so that we get a triangle with all three colours. :)
I'm extremely late (this is at least my second time here) but I think you can bypass the problem with the colouration difficulties with the vertices quite readily: I don't think the third vertex needs to be unique, you just start from one of the edges that has two distinct coloured vertices (this must exist), and then follow the doors around. If we label, say, red/green edges as doors in the example triangle, there's only ever one door on the edge (noting that 1 is odd), and the graph still has the property that every triangle has either 0, 1 or 2 edges, which is all we needed for the proof.
An important point mentioned in the NY Times article is that each room in the apartment is valued differently by each of the roommates. This is how uneven rental shares come about. If each of the roommates were merely minimizing cost, Game Theory predicts the a strict Nash equilibrium of Rent / N, where N is the number of roommates. Another observation from the fair division calculator is that if two or more people are adamant about a particular room, the price spikes dramatically with such demand and takes a long time to recover afterward.
Do strategies exist for picking rooms based on selections of other players and prices that spoil the fair division?
Regarding the problem of same colors in two corners.
What you do is you take the color of the two corners and the color of the remaining corner a your set for defining door. Since are limited in color choice, there's only going to be combinations that feature corners of all 3 colors or of 2 colors - there's always going to be a side of the triangle that has a solution.
5:25 the reason for always having an odd number of doors at the bottom is because of the Sperner's Lemma in 1-D, which states that there are an odd number of color switches on a line segment.
I am in the AIRBNB like house management indust. for about 20 years till now, I don't think this will ever work out. The attributes a room can have is too many, we usually use public area and private area share and advantage attribute(private toilet, window, facing and so on) to calculate the rent.
The corners represent the choices between a pair of free rooms. In the setup, each person gets a different pair from which to choose. If the red room is popular with Alice and Bob, then Alice prefers red to green while Bob prefers red to blue. Change the assignment of people to corners (there are 3!=6 ways) until you find a suitable graph, or else you've learned that one room is completely worthless and you should find a better place to live.
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. :)
Excellent!
Perfect, as usual
Lovely proof.
Does this generalize to "rectangulations" or other "n-gonations"?
My solution is not to use complex math, but economics (and a tiny bit of algebra). First, ask everyone what’s their 1st pick for the room they want. If multiple people choose the same room, then ask them if they’re willing to spend more than the total rent divided by 3 ($1000) for that room, and have them bid until there’s a winner, and have the winner commit to that price and they’re free to go start moving their stuff in. Then, continue for the remaining rooms with the remaining portion of rent (so if room #1 went for $1100, then the remaining rent is $1900 so if the next room also has multiple 1st-pick people, then bidding would start at $950).
Easy & fair. The rooms have different subjective values, so the price of each is determined by the interested parties, in particular the party willing to pay the most. And the party who gets the room nobody else wanted gets the benefit of paying the lowest price.
A door corresponds to a colour change from blue to green or vice versa. Since the right-hand corner is the opposite colour to the left, there must be an odd number of colour changes (as two brings us back to the original colour) and therefore an odd number of doors.
Given that this is true, each time you go through a door on the bottom, there are two possibilities: 1) You come out of another, eliminating two doors from the bottom which leaves the number of possible special rooms which you can reach from the bottom odd, and 2) You reach a special room. Therefore you can reach an odd number of special rooms from the bottom. Similarly if you start at any of the special rooms not reachable from the bottom, then you can exit through its single door - this will either take you into a room with two doors or another special room, so you will finish at some point in another special room. This adds two to the total, leaving the parity unchanged. Since there are an odd number of special rooms you can reach from the bottom, and all other special rooms are joined in pairs, there are an odd number of special rooms
If you don't have 3 differently colored corners you'll have to redefine the triangle. The triangle doesn't need to be equilateral, so as long as you can find a smaller triangle inside the big one that has A B C corners with different colors, you can then re-triangulate it and find the solution somewhere inside it.
Mathematically there's no guarantee this triangle exists, but with people paying rent they'd have to be pretty nuts to make it impossible to find.
Edit: On further thought I guess the redefined triangle could be outside the original one I guess. Then you'd be getting paid for living there. Eventually you'd find a triangle ABC with different colors. Must be some really dank apartment if you need to be paid to want it. Or you're rich and can't agree with your roommate who gets the cool one so you pay him to accept the dank one, something like that.
And the proof of Viviani's theorem is because the sum of the areas of the 3 triangles is a constant (the whole area) so dividing by the base gives the sum of the altitudes.
I'm moving out if any of my housemates starts drawing triangles with crayons.
Wasn't really sure what video I should click first :D
We leave the "HOUSE"
aaah you thought we wouldnt notice? :D
:)
Where do you buy your shirts? I'm interested in buying a couple I've seen you wear.
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...?
Awesome video!
amazing video!
Since you only have to worry about the "doors" at the bottom of the triangle, most of the points in the puzzle can be ignored. For example, if we choose "red-blue" as our door, then there is only 1 door leading into the puzzle....on the far left. When you asked what would happen if we turned "B" into green, it still doesn't make a door. If we choose "blue-green" then it can only apply to that scenario and the "red-blue" door goes away. If the entire bottom becomes blue (both vertices), then we can safely "delete" the bottom edge and begin fresh in the next row up as our new edge.
This means....we can pick any 2 points at the bottom edge to begin our "walk" on the puzzle as long as those 2 points are not identical in color. We then request a new choice on the third point as soon as we walk through the door to figure out if either:
1. another door appears, at which point we walk through it and repeat the request
2. no door appears, and we've found a position in the puzzle that all people agree to the price and room, ignoring nearly 66% of the map.
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?
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].
As a programmer, I'm drawn to the parallels with pathfinding
This is art!
Would the existence of multiple triangles with three color vertices mean there are multiple solutions that everyone could agree on? How can the optimal solution be chosen from those options?
The only way you can get an even number of doors at the bottom is if both pole vertices are the same color. They must be different colors.
An EVEN number of vertices on the bottom, would create an odd number of lines that would all be doors if they were alternating, but if you changed any color, you would change an even number of doors (0 or 2, never 1).
Odd +/- Even = Odd
An ODD number of vertices on the bottom would create an even amount of lines but because the two poles need to be different colors, you will always need at least one line to not have a door.
This means you start with an Odd number and swapping colors would make an even change. Again, Odd +/- Even = Odd.
@Mathloger How does this relate to a nash equilibrium?
Great video!
:)
I can't find Sperner's Lemma in 3B1B's channel. Can you please guide me?
Please don't post the link directly as UA-cam will mark your message as spam. Simply paste the code at the end of the page URL.
ha! another cool math thing I won't understand :D
cool tshirt btw!
For proving the odd number of doors at the bottom. If there is only 2 points, there must be one door. Adding extra points can not add a new door. Flipping any of the colors of the midpoints can only remove or add 2 doors, never remove or add one door.
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.
Perhaps should mention a special case where an internal path has zero end points so is a loop with no special rooms - but zero is even so your argument is still valid.
how to 'fix it' for schperners lemma to always apply:
in sperners lemma, the corners are set and the lengths are random. In the room renting the corners are random and the lengths are set.
We have to switch the sides with the corners somehow. I'm not up to steam yet, been drinking yesterday and I just woke up, but it's a familiar problem as a student (both dividing the rent and drinking too much).
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?
What if a triangle had 3 blue and 1 brown corners?
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.
If two vertices of a big triangle have the same color, that means, all the edge is one-colored and we can't have our solution triangle adjacent to this edge. So we remove this edge completely and end up with a little bit smaller triangle.
If this smaller triangle has all vertices colored differently, we can apply the lemma. If not, rinse, repeat.
ooooh dang. smart.
Well, you don't have to rinse and repeat. After removing one of the duplicate vertices you always end up with a sperner triangle (which is slightly less ordered but is still a sperner triangle)
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
Can you assume Sperner applies if the corners match?
In a situation like the Times' article described, it seems like as long as you had two free rooms to choose from, there's one room that wouldn't ever get picked. But that's fine, because we are assuming that, if one and only one of the three room is free, people will always pick that one. And sperner's lemma is supposed to apply to all triangulations of the triangle. So you can just cut off one of the offending corners, and stretch one of the correctly-colored edges to fill it in. Voila! a three-color-corner triangulated triangle. This amounts to picking a smaller triangle, out of the space of all possible rent divisions, and showing that sperner's lemma applies to the smaller triangle, so it must also apply to the larger triangle that contains it.
Now, this won't work if the offending color doesn't appear ANYWHERE on an edge. But that would amount to saying that one of the rooms, no one would stay in it for free. And yes, that genuinely is a situation with no solutions :P
*"Can you assume Sperner applies if the corners don't match?"*
That's the only time Sperner applies. Sperner's lemma requires that the three corners each be a different color. For Su's variant on Sperner's lemma to work, that isn't necessary. Requiring that all vertices on a side, other than the corners, be a single color guarantees a tricolor triangle and a solution.
Sorry, typo. Obviously I meant to answer his question at the end, how can you show Sperner's lemma to apply if the corners aren't all different colors. I fixed it now.
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.
This method doesn't make everyone happy, but it does divide things in a way they must agree is "fair." Chad might only want to spend $50, but he is constrained by the total cost: If he assigns a value of $50 to one of the rooms, he must assign more value to the other rooms to add to $500. If Chad says that one of the rooms is worth $300, then it would be "fair" for the roommates to ask him to live there and pay that. The roommates don't get the room they want at the cost they want, but they will get a room at a value they assigned to it.
In your example, you are only valuing the apartment at $450 ($50+$200+$200). What you want is actually unfair: you are hoping that your roommates will make up the extra $50.
This problem is really just an extension of the simpler way to fairly divide something between two people. One person makes a "fair" division into halves and the other person gets to choose which half he wants. They might not like what they got, but they can't say that the other person got a better deal.
If you have 3 special triangles, which one do you use for rent and room assignments?
Triangles are only special in the condition that all 3 roommates agree on the price distributions in that region; if there are multiple possible configurations that each roommate would agree to, all are considered "fair" and this method makes no attempt to pick the "best" balance among all possible deals
Can we use this to efficiently search Pareto fronts?
love your videos. especially when you ad lib :) #extemporaneous