Welcome to another Mathologer video. Today is about

a math story that made it into The New York Times

something that's really very rare.

It's about a familiar problem. A couple

of friends,

Ashwin, Bret and Chad want to rent an

apartment. Now the rooms are quite

different and the friends have different

preferences, different ideas about what's

worth what. Is there a way to split the

rent and assign the rooms to the

friends so that everybody is happy?

It's really quite a tricky problem. Quite

recently it was discovered that a very

famous and very pretty result in

abstract math can be brought to bear on

this and many other related fair

division problems. So my mission today is

to sort all this out for you as best as I

can. Let me know in the comments how

I did. My favorite math channel is

Grant Sanderson's 3blue1Brown. Now this

week Grant and I have conspired to bring

you videos about two very different

fair division problems. If you like my video

or even if you don't, check out 3Blue1Brown,

Grant really does some wonderful work there.

Alright let's start with this

mathematical results, it's called Sperner's

lemma and it's due to the mathematician

Emanuel Sperner who published it in

1928. It's been awhile. In maths this pretty result

comes up in all sorts of

different contexts. So if you are in the know you

might recognize some of these. Okay so

here we go, take a triangle, any triangle

and triangulate it, that means chop it

into a network of little triangles like

this, ... or like that

We'll actually use a super-nice

triangulation of an equilateral triangle

for illustration. You all know this one, right?

Important: everything I'll say will work

for all other other triangulations, all other

triangles.

Color the corners with three different

colors, red, green and blue.

On the bottom edge randomly color every

vertex green or blue like this. On the

left edge randomly color every vertex

red or blue, for example like this.

The vertices on the right side are colored

red and green. Color the vertices in the middle

randomly, no restrictions apart from them having to be

red, green and blue.

Maybe something like this. Now,

there are infinitely many ways to

triangulate and infinitely many valid

ways to color the vertices of

triangulations and yet we can be

absolutely, absolutely certain, and that's

really what Sperner's lemma is about, that the

corners of at least one of the little

triangles in there feature all three

colors. For example here's one. Now there

can be more than one. For example, here's

another one, and there's another one. But

we can always be sure that there is at least one

of them. So how do you prove something

like this.

Well, there's a really really nice proof.

Think of this big triangle here as

a house with the little triangles being

the rooms. Every room is bounded by

three edges.

Let's say an edge is a door if it's two

ends are colored blue and green like that

one here.

Now there's are lots of doors in here, so

let's just highlight all of them. Here

they are. Important: instead of making

the blue-green edges the doors we could

also have chosen the red-green edges or

the red-blue edges as door. That would have

given different sets of doors but the

following argument stays the same for all

these choices. Here are three

important insights about the doors in our

house.

Let's start with a question: What are the

possible numbers of doors in a room.

Zero doors is definitely possible like

this. Exactly one is also possible and if

this is the one door here

what can we say about the color on top?

Well it cannot be blue or green because

that would give a second door like this, or

like that and so this means there's got to

be a red on top right? And that means

that the rooms that have exactly one

door are exactly the special 3-colored ones.

OK so that's pretty good already. Now as

we've already seen two-door rooms are

possible.

They have either two blue vertices and

one green, like this, or two green and one

blue. But then once a room has two

doors it's going to be one of these two

types which means that three doors is

impossible.

So to summarize, a room has either

zero, one or two doors and the

ones with exactly one door are exactly the

special 3-colored ones. Next, because of the

restriction of what colors can go on the

sides of the house it's clear that all

doors on sides have to be along the

bottom. We can also say something about

the number of doors at the bottom

namely there will always be an odd

number of doors at the bottom, so 1, 3, 5, 7

etc. In this case we've got three.

Why always an odd number of doors at the bottom?

Well I leave this for you to figure out

in the comments, actually pretty easy.

Now we're ready for the proof that

there will always be at least one of

those special 3-colored rooms in our

house. Let's enter the house through one

of the doors at the bottom, here we go.

Either the room we're in has exactly one

door or exactly two doors. If it has

exactly one door

the room is special and we're done, we

found a special room. Otherwise let's step into

the next room via the second door. Again

either we are in a special room and

we're done or we can keep going and as

we continue like this will never enter

the same room twice. But then since the

only finitely many rooms our trip must

end either in a special room in which

case we're done or we leave the house

through a second door at the bottom. So

far we've walked through two doors at the bottom ,

right, but since there's an odd number of

doors at the bottom there's at least one

more left over,

at the bottom, that we have not passed yet.

So let's reenter the house through one door

like this, at the bottom. Again we'll never

enter a room that we've already visited

and so the second trip will also either

end in a special room or another door at

the bottom. So, going like this, going like

that. Every time we end up outside

we've used up an even number of doors at

the bottom and since there's an odd

number of doors at the bottom, we can

always find a door to re-enter at this

stage. Now obviously this cannot go on

forever and therefore we eventually must

end up in one of those special

3-colored rooms no matter how hard we try

to avoid this. Isn't this a wonderful

proof. Now there's a bit more: you can

actually show that there's not only just

one special room but an odd number of

them. So, for example, in this case we've

got three so maybe also see whether you

can extend our proof in the comments

to show this. Now, how can all this be used to

achieve rental harmony. Let's say the rent

is 500 dollars,

Well it's obviously not New York City :) So

then there are lots of different ways to

split up the rent, for example,

$100+ $200 + $200 or this one here or,

crazy but or well it's just one rich guy

paying for his friends. Now we turn the

big triangle into a mathematical space

of rent divisions.

What this means is that every one of the

points inside it will stand for exactly

one of these possible divisions. OK

let me explain.Take a point on the inside

of this equilateral triangle here and

add up the distances to the three sides.

Now and this is really quite wonderful

this distance sum is always the same in

equilateral triangles. Red plus blue plus

green is constant. This is called Viviani's

theorem. So this distance sum is the same

as that one here, it's the same as that

one and it is the same as, well let's

make red and green vanish by moving the

point to the corner.

So what this means is that our constant

is really the height of the triangle.

Now let's superimpose our

triangulation. Using this special

triangulation we can illustrate all its

nicely. So the big triangle is five

little triangles high: 1, 2, 3, 4, 5

So let's say the height is 5 units.

Let's move the points. As you can see red is one

unit long, blue is two units long and

green two. And 1+2+2=5.

Works. Try another one: red is

zero, blue is 2 and green is 3. Works!

In this way every point in the big triangle

corresponds to exactly one of the

possible ways to write 5 at the sum

of three non-negative integers or,

if we scale everything by 100, the

vertices of our triangulation correspond

to the different ways of writing $500

as sums of multiples of $100.

For example, here we've got $0 + $200 +$300.

Or, moving to a different vertex and

maybe one more, like that.

OK, now we somehow want to use Sperner's

lemma to choose how we should split up

the rent and who among the friends

should move into which room and the friends

should end up happy with all this.

To do this we first label the vertices

with the friends, like so. Now the letters

are distributed in a regular pattern

such that all three letters occur at the

vertices of every one of the little

triangles, like this little triangle

there has ABC around it. That little

triangle has ABC around it and really you can

check, every other little triangle has ABC

around it.

Now let's look at one of the possible sums.

$0 + $400 + $100.

The corresponding vertex is labeled B, so let's

ask Bret which room he'd go for if the

rent was split up like this.

Well the red room costs nothing

and so it's reasonable to assume that

Bret will go for the red room

In fact,

we'll assume that everybody who's offered

a free room will go for it.

OK, Bret goes for the red room, so we

color this vertex red. Next vertex. The

new vertex is labeled C so it's up to

Chad to choose. Since red still costs

nothing Chad also goes for this room.

So in this way all the vertices on the left

will all end up red. For the same reason

the bottom edge will end up blue and the

right edge will end up green. Now in a

corner we've got two free rooms and in

this case

Ashwin will choose either one of them.

You get the same sort of choices in the

other corners. Now we fill in the rest by

going to the middle, and in the middle

there's no 0 here, so Bret can choose

whichever of the rooms he likes best

given this rent division, say he goes

for red. Now we continue to fill in the rest

and it looks like we may be able to somehow

apply Sperner's lemma with all those

colors. And we do if the choices in the corners lead to

three different colors,

for example like this. If this happens then

we have a coloring to which

Sperner's lemma applies, that it, we have a

little 3-colored triangle, there we go :)

How does this help with our problem?

Well the way the corners are labeled

ABC tells us that Ashwin should take

the green room,

Bret the red and Chad the blue. What

about the division of the rent.

Well the divisions corresponding to the

vertices of the little triangle are very

close, especially if we use a fine

triangulation like this one here.

Just in case you cannot see properly, the arrows

point at the tiny special triangle that I've

magnified up here. The three corners of this

this triangle correspond to

$120 + $150 + $230 dollars, ... that one

here, and finally that one here. So

the differences are in the

ten dollar range and every friend was

happy with this assignment of rooms there

for one of these divisions, and so

picking any of these three divisions

randomly should work for all three friends.

Now if some unhappiness persists finer

triangulations will get the divisions to

differ in arbitrarily small amounts. Now it's

possible to use the same sort of ideas

to come up with all sorts of other types

of fair divisions. I've linked in the paper by

Francis Su on which all this is based, as

well as to link to the New York Times

article which contains a nice apt to

explore as well as a website that allows

you to actually make real-life decisions

based on this circle of ideas.

A couple afterthoughts: all this

also works if you're dealing with less

or more than three rooms you just have to

use lower or higher-dimensional versions of

Sperner's lemma. I''m not going to go into

details here.

You may also have gotten the impression

that all this is impractical because to

color in a triangulation like this you

have to ask the friends to make as many

decisions as they are vertices, in this

case it is more than a thousand. However,

remember, when we looked for the special

little triangles we only visited a very

small part of the large triangle, so the

idea is to color in the triangulation

"on demand" as we walk around it.

This will cut down on the number of

decisions, and using some other

refinements it's possible to reduce the

number of decisions to something

manageable as in the online app.

One more thing:

Remember, at this point of the story,

choices at the corners either lead to

three different colors, like this. Then

Sperner's lemma applies directly. However,

you can also end up with this sort of

coloring here which is slightly

different from a Sperner coloring because

the corners of the big triangle don't

feature all three colors. Can you explain

how things have to be adjusted to save

the day here? Again let's have some fun

discussing this in the comments.

And that's it for today. Now I'll go and

have some rest but you should now go and

explore a bit what other miracles

mathematicians work using Sperner's lemma.

For example, if you understood everything

in this video you are actually on the brink

of understanding the nifty proof of the

famous Brouwer's fixed-point theorem that I've

linked in in the comments. So have fun

with that, too :)