Make sure to check out 3Blue1Browns fair division video kzread.info/dash/bejne/eJyHqM2FmKenfqQ.html And, as usual, please ask if there is something you don't understand :)

@15october91

7 жыл бұрын

I know this isn't related to the video but what is your intro song?

@Mathologer

7 жыл бұрын

Some random clip from the library of free tunes that KZread provides. Having said that a lot of people have commented that it reminds them of Kate Bush's Babooshka :)

@SleepingUnderable

7 жыл бұрын

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!

@15october91

7 жыл бұрын

Thank you.

@Mathologer

7 жыл бұрын

+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

@Mathologer

7 жыл бұрын

Yes, 3B1B is simply amazing :)

@pauljoyko5320

7 жыл бұрын

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 🇩🇪

@moritzkockritz5710

7 жыл бұрын

3B1B has gotten almost as big as mathologer after the vsauce video

@Vedvart1

7 жыл бұрын

That's what people said about Kursega... Kursgesgts... Oh, you know who I mean.

@TheLolle97

7 жыл бұрын

Vedvart and they changed it eventually.

"So what are you doing with that weird triangle?" "I'm calculating rent.

@scitwi9164

7 жыл бұрын

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 ;)

@mangeurdecowan

7 жыл бұрын

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."

@richardgates7479

7 жыл бұрын

The writers of that show wouldn't have a clue.

@DigitalDreamG1rl

6 жыл бұрын

Ahahaha

@MikehMike01

3 жыл бұрын

@@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.

@deadmeat1471

7 жыл бұрын

good observation

1:08 *Music to my ears!* So satisfying to hear "Sperner" pronounced "Schperner"!

@U014B

7 жыл бұрын

PlayTheMind He _is_ German himself, so I'm not surprised, but yeah.

@AntoshaPushkin

7 жыл бұрын

Schhhhhhhperner. Did you feel it?

@Mathologer

7 жыл бұрын

+PlayTheMind :)

@Metalhammer1993

7 жыл бұрын

mathologer where are you from? i kinda think like i´m hearing a german accent (or at least perfect pronounciation of german words)

@Mathologer

7 жыл бұрын

+Metalhammer1993 Yes, I grew up in Germany but have been living in Australia for more than 20 years :)

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.

@Mathologer

7 жыл бұрын

Yep, that works :)

@DrGerbils

7 жыл бұрын

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.

@mina86

7 жыл бұрын

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. ∎

@aadfg0

7 жыл бұрын

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.

@rmsgrey

7 жыл бұрын

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.

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 KZread 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.

I will keep all this in mind if I ever have to split rent with a bunch of robots.

@anthonymonterrosa4383

7 жыл бұрын

Give it a few decades ;)

That is one of the most beautiful proofs I've ever seen, and wonderfully illustrated. Thank you.

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.

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).

@Mathologer

7 жыл бұрын

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.

@rasowa2958

7 жыл бұрын

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?

@rasowa2958

7 жыл бұрын

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.

@BainesMkII

7 жыл бұрын

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.

@NatePrawdzik

5 жыл бұрын

My wife pays negative rent.

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.

@cheongziyong8871

7 жыл бұрын

Jim Baumbach The two trips can't be identical as each starts from a unique bottom door.

@cryme5

6 жыл бұрын

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).

@irrelevant_noob

5 жыл бұрын

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 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.

You have an awesome channel! keep up the good work!

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! :-)

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.

@mappingtheshit

9 ай бұрын

What if your roommate jizz in the room?

Wow! great topic!! :O Thanks!! I love mathologer Chanel

Wow, beautiful proof Burkard! Thx for sharing this.

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

@Mathologer

7 жыл бұрын

Did it work for you ? :)

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

@clairecelestin8437

7 жыл бұрын

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

Could you do something about Integrals some day, maybe? I would love to learn about it through you! Thanks, man! I love your videos.

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.

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

@Mathologer

7 жыл бұрын

:)

This video is why I love the internet.

This is a wonderful explanation of Sperner's lemma!

7:49 omg I thought my screen broke :)

@TacoDude314

7 жыл бұрын

DanJan09 why?

@NoriMori1992

7 жыл бұрын

I didn't even notice that…

@U014B

7 жыл бұрын

TacoDude314 Look at Burkard's chest on the right (our left). There's a ( on the screen.

@TacoDude314

7 жыл бұрын

Noel Goetowski oh haha thanks

@DouglasZwick

7 жыл бұрын

Oh weeeeird

I didn't know the name of the guy behind ThreeBlueOneBrown

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.

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

A very nice example of how mathematics can help people in real-life situations :>

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

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.

@SmileyMPV

7 жыл бұрын

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.

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.

Your videos are awesome as always!!! Would recommend a color blind version for the red and green colors!

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.)

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.

@AdmiralJota

3 жыл бұрын

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.)

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".

@qwertyfinger

7 жыл бұрын

> 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.

@DrGerbils

7 жыл бұрын

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.

@kasuha

7 жыл бұрын

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.

@Mo-uc7vg

7 жыл бұрын

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.

@masterineverything

7 жыл бұрын

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

@Mathologer

7 жыл бұрын

Yes, Grant and I coordinated to release these videos at the same time :)

@mina86

7 жыл бұрын

I’ll take a wild guess that you haven’t watched the videos yet.

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

Instructions unclear: Left a diagram of a coloured triangulation in my landlord's mailbox.

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.

Awesome video!

Mathologer: How do you make your graphics / animations? What software do you use to make these videos?

@AlexanderBukh

7 жыл бұрын

Krishan Bhattacharya try "Processing"

Perfect, as usual

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?

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!

@Mathologer

7 жыл бұрын

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, ... :)

@harrypanagiotidis7370

7 жыл бұрын

That's a pretty nice way to get an intuitive understanding of the theorem! As always great video!

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?

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!

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.

MIND = BLOWN!

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.

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'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.

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

@Mathologer

7 жыл бұрын

:)

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. :)

Where did you get that shirt? I'm having trouble finding that design online.

Excellent!

amazing video!

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

This is art!

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. :)

I can't find Sperner's Lemma in 3B1B's channel. Can you please guide me? Please don't post the link directly as KZread will mark your message as spam. Simply paste the code at the end of the page URL.

Great video!

@Mathologer

7 жыл бұрын

:)

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

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?

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.

@jetison333

6 жыл бұрын

ooooh dang. smart.

@luciotanzini7319

4 жыл бұрын

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)

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).

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.

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.

Wasn't really sure what video I should click first :D

Lovely proof. Does this generalize to "rectangulations" or other "n-gonations"?

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

Hallo Herbert geiles Video!!

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.

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.

If you have 3 special triangles, which one do you use for rent and room assignments?

@clairecelestin8437

7 жыл бұрын

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

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.

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?

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...?

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

We leave the "HOUSE" aaah you thought we wouldnt notice? :D

@Mathologer

7 жыл бұрын

:)

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

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?

@anonymoususer9837

4 жыл бұрын

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.

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].

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

@AndresFirte

5 жыл бұрын

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.

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.

Can we use this to efficiently search Pareto fronts?

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.

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?

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.

@mikebrau5354

4 жыл бұрын

That isn't *optimial* (envyless) fair division (equal value to everyone), that's merely *satisfactory* division (non-negative value to everyone -- each person gets a room worth less than their willingness to pay). After building a non-degenerate preference triangle in your solution, there is economic surplus that still needs to be divided fairly. A simple example: Suppose all three are each willing to pay $2 for a different favorite room, and $1 for the others, and total rent is $3. Then "A pays $2 and B,C pay $.50", all for their favorite room, is acceptable (satisfactory) per your preference triangle, but not fair, because A is still envious of B and C. A fair solution would be everyone pays $1 for their favorite room. The difference between satisfactory and optimal is easily seen if you ignore the rooms and ask how to divide $3 fairly (envy-free). The roomshare with its complicated value model makes the solution more complicated.

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).

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.

@calculagator

6 жыл бұрын

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.