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.
![อยู่ได้แล้ว - LIPTA feat. Mirrr [OFFICIAL MV]](http://i.ytimg.com/vi/-9-hpntNym4/mqdefault.jpg)
Make sure to check out 3Blue1Browns fair division video th-cam.com/video/FhSFkLhDANA/w-d-xo.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 TH-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
Both of you do an absolutely fantastic job of communicating the beauty of math, love your videos, never stop.
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 TH-cam at the moment.
Thanks for the video!
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.
That is one of the most beautiful proofs I've ever seen, and wonderfully illustrated. Thank you.
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 :)
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.
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
I will keep all this in mind if I ever have to split rent with a bunch of robots.
Give it a few decades ;)
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!
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.
What a fascinating proof! Nicely explained, too! :-)
12:39 If this is New York, that big triangle probably wouldn't even fit into one of the apartments.
You have an awesome channel! keep up the good work!
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?
Wow, beautiful proof Burkard! Thx for sharing this.
This video is why I love the internet.
Wow! great topic!! :O Thanks!! I love mathologer Chanel
I didn't know the name of the guy behind ThreeBlueOneBrown
Could you do something about Integrals some day, maybe? I would love to learn about it through you! Thanks, man! I love your videos.
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
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
:)
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.
I actually used an online tool for this several years ago when I was sharing an apartment in Boston :)
Did it work for you ? :)
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?
A very nice example of how mathematics can help people in real-life situations :>
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
Your videos are awesome as always!!! Would recommend a color blind version for the red and green colors!
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
This is really beautiful!
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
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.
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?
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.)
Where did you get that shirt? I'm having trouble finding that design online.
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!
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.
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.
Perfect, as usual
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.
MIND = BLOWN!
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.
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.
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?
@Mathloger How does this relate to a nash equilibrium?
Can we use this to efficiently search Pareto fronts?
This is art!
I can't find Sperner's Lemma in 3B1B's channel. Can you please guide me?
Please don't post the link directly as TH-cam will mark your message as spam. Simply paste the code at the end of the page URL.
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.)
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).
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
Instructions unclear: Left a diagram of a coloured triangulation in my landlord's mailbox.
What if a triangle had 3 blue and 1 brown corners?
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.
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.
Awesome video!
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.
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.
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.
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
I couldn't believe it should be so diabolically obvious! Thanks!
:)
Can someone explain how we know the path through will never go to the same room twice?
debblez short answer: because that would only happen if the rooms had 3 doors, and we know that is impossible
Long answer (maybe I just overexplained it): we know that we can only have rooms with 1 door, 2 doors or 0 doors. Each time we enter a different room (lets call it Room alpha), we know that alpha can’t have 0 doors, because we entered alpha through a door. So alpha must have either 1 or 2 doors. If alpha has 1 door, then we found the special room. But if alpha has 2 doors, then we can enter through the door that we haven’t used yet to get to another room. So, let’s see that you will never go through the same room twice.
(Remember that we can’t backtrack, so once we enter a room, we can’t simply turn around and go back). If we got to alpha twice, that would mean that at some point out path must have had a “loop”. So let’s go to the room where the loop was made: the first room that was visited twice. This room can be alpha, or can be a different room. Let’s call it Beta. You can only enter to Beta through 2 doors. Remember that it is impossible for any room to have 3 doors. Let’s call those doors A and B. If we had entered (for the second time) to Beta through A, that means that Beta was not the first room that we visited twice, because we must have gone first through the room that A leads to. So we visited that room twice. If we had entered to Beta through B, then we must have visited twice the room that B leads to. So as you can see, we can’t have any room called Beta (remember that Beta was defined as the FIRST room that was visited twice), because everytime we claim we have found Beta we can conclude that one of the adyacent rooms to Beta was visited twice before Beta. We can never find any Beta, so we can never visit a room twice. Because Beta can’t exist.
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. :)
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
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...?
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?
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?
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?
If a room has 0 doors, we can't enter it. If a room has 1 door, we stop when we enter it. Rooms can't have 3 doors, so this only leaves the 2-doored rooms under possibility of being entered twice. To enter one of them twice, we'd either have to enter an earlier room twice to use its door twice, or backtrack through a door we already went through. Since we never backtrack (including not entering from an outside door we already exited from) and the earliest room for each path (a room with a door on the edge) is only entered once when we choose our path, we can't enter any of the rooms twice.
amazing video!
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.
Lovely proof.
Does this generalize to "rectangulations" or other "n-gonations"?
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!
Excellent!
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
Wasn't really sure what video I should click first :D
mate, where were u looking throughout the video
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. :)
Where do you buy your shirts? I'm interested in buying a couple I've seen you wear.
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 divide the triangle infinite times do you get the true fair division at the cost of having to label infinite points
Hallo Herbert geiles Video!!
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)
Where can I buy that shirt? I've found similar online, but none quite as cool.
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].
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.
what does coloring a vertex represent?
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.
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.
Great video!
:)
As a programmer, I'm drawn to the parallels with pathfinding
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.
Very interesting. But the problem is as the number of parties increase to d, the (hyper-)triangle becomes (d-2) dimensional. Assuming that the Sperner's Lemma extend to higher dimensions, curse of dimensionality happens, as the number of triangles to check, exponentially increase (by d).
From the Sperner's proof, I am thinking if one can apply a "smart" walk to quickly get to a valid solution. Interesting....
if somebody is answering with nefarious means, is it possible for him to still get a better answer than if he had always answered the lowest/best suited for him
Could you demonstrate this? I think you may be correct and this is an interesting comment about game theory, though mathloger dude did say multiple times that each one attempts to get the lowest rent on each choice, not sneakily game the system long term by making 'short term bad decisions' so I dont think its a criticism of this video.
Shit, you are right, I totally missed that somehow :/