Larry, Curly, and Moe are moving into a new apartment.

Both Moe and Larry want the room with the balcony, but Curly isn't as picky.

He mostly just wants a cheap room.

Taking into account all their subjective preferences, how should they fairly decide who gets which room and how much each person should pay?

10 00:00:27,390 --> 00:00:30,260 To help these wise guys fairly divide rent, we use some surprisingly geometric mathematics.

The fair division method we'll explore is grounded in a fact about triangles subdivided into further triangles known as Sperner's Lemma.

So let's start there.

Start with a triangle, and break it up into a bunch of smaller triangles.

Label the three points or vertices of the big triangle 1, 2, and 3.

Label each vertex on the sides of the big triangle with either of the labels at the endpoints.

So these are labeled 1 or 2.

These are 2 or 3.

And these are 1 or 3.

Finally, label the inside vertices 1, 2, or 3.

It doesn't matter.

Here's the fact known as Sperner's Lemma.

There will always be some smaller triangle with each of the three labels on its corners.

It will be labeled 1, 2, 3.

Why will a fully labeled triangle always exist?

In other words, how do we prove Sperner's Lemma?

Well, here's a procedure for finding one.

First, pick any two numbers from the options 1, 2, 3-- either 1 and 2, or 2 and 3, or 1 and 3.

Let's pick 1 and 2.

Color green all the edges whose vertices are labeled 1 and 2, like this.

Now imagine that all of the small triangles are rooms, and the green edges are doors.

Each small triangle has zero, one, or two doors.

It can't have three doors.

Here's a key observation.

A room has one door, if and only if it is labeled with all three labels.

To prove Sperner's Lemma, we need to find a triangle with all three labels.

And now we know that those are exactly the rooms with one door.

So we're hunting for rooms with one door.

So how do we find a one-door room?

First, observe that there must be an odd number of doors on the outside of the triangle.

All the exterior doors will be on the right side since that's the only side that can be labeled with both 1 and 2.

Starting from the top vertex labeled 1 and going down to the vertex labeled 2 at the bottom, each time we encounter an edge where the label switches from 1 to 2 or from 2 to 1, it's a door.

It must switch an odd number of times so there is an odd number of exterior doors.

Now pick one of these exterior doors and walk through it.

Either you just walked through the only door in the room, or there is exactly one other door.

If there's another door, walk through that.

Keep walking through doors without backtracking until you're stuck.

Then you've found a room with only one door-- a fully labeled room.

And you're done.

But what if you keep walking through doors and eventually wander back out through an exterior door?

This is why it matters that there are an odd number of doors on the exterior.

If you wander in through one and out through another, you've used up two.

But there will still be an odd number of doors-- namely, at least one-- that you can wander back through to find a fully labeled room.

There's a few details I left out of Sperner's Lemma, like that there will always be an odd number of fully labeled rooms.

As a mini challenge, can you show why this is true?

You have to fill in some details of the proof we gave above.

If you have an idea, go ahead and leave it in the comments.

Actually, Sperner's Lemma holds for all simplices.

A simplex is like a triangle, but they're defined in any dimension.

To construct a 2-simplex-- AKA a standard triangle-- place three vertices.

Then connect them with edges, and fill in the edges with a face.

To boost this up a dimension and build a 3-simplex-- AKA a tetrahedron-- we start with four vertices, connect them by edges, then connect the edges by faces, and finally, fill in the three-dimensional space between the four triangles.

To build a 4-simplex in four dimensions, start with five vertices, fill in the edges, then the triangles between the edges, then the three-dimensional spaces between the triangles, and then-- here's the crazy imagination part-- fill in the four-dimensional spaces between those three-dimensional ones.

The same idea gets you a simplex in any dimension.

And if you break an N-simplex into smaller N-simplices and label the vertices using the numbers 1 through N plus 1-- just like we did with the 2-simplex-- Sperner's Lemma tells you that one of the smaller N-simplices will have all the labels on it.

OK. Now that we're way past the limits of my visual imagination, let's move back to Sperner's Lemma for a normal triangle.

How is this weird fact going to help a split rent?

Who should get what room?

And how much should they pay?

Here's how.

Take an equilateral triangle and break it into a bunch of smaller triangles.

In three-dimensional space, place the triangle so that one corner is on 1, 0, 0, one corner is on 0, 1, 0, and one corner is on 0, 0, 1.

Now for every point on our triangle, the coordinates are all non-negative and add up to 1.

This point is 0.2, 0.7, 0.1.

And this point is 0, 0.62, 0.38, and so on.

Each point in the triangle is labeled by three coordinates, because it's in three dimensions.

And those correspond to a distribution of the rent.

The x-coordinate is the cost of room 1.

The y-coordinate is the cost of room 2.

And the z-coordinate is the cost of room 3.

So the point-- 0.2, 0.7, 0.1-- means that bedroom 1 costs 20% of the total rent, bedroom 2 is 70%, and bedroom 3 is 10%.

At each of the three corners of the big triangle, one room costs 100% of the rent, and the other two are free.

Along the sides of the triangle, one room is free while the other two split the rent.

Now label each vertex of the triangle either Larry, Moe, or Curly so that every little triangle has one of each label, like this.

We will apply a second labeling on top of this one which shows what bedroom each of these people prefer.

Let's look at a single vertex, like this one.

It corresponds to the rent division 1/8, 1/8, 3/4.

We just labeled it Larry.

So we ask Larry, if the rent were divided this way, which room would you prefer?

Maybe Larry thinks the third room is worth the extra money.

So we mark a 3 next to it, indicating he has chosen room 3.

Do this for each vertex.

Ask the person labeled at the vertex which room they prefer at this price division.

Then mark the answer.

On the sides of the triangles, there is one free room, so everyone will always pick that one.

On the three main corners, there are two free rooms.

Since everyone likes a free room, they'll pick one of the free ones.

It'll make the next step easier if they pick these free rooms.

These numbers-- the 1's, 2's, and 3's-- meet the requirements of a labeled triangle from Sperner's Lemma.

So at least one of the smaller triangles must be fully labeled, like this one.

The fully labeled triangle gives a fair division of the rooms.

Curly gets room 1.

Moe gets room 2.

And Larry gets room 3 at roughly the prices with which they selected those rooms.

Because we only divided the triangle into eight layers, the price distributions at the three corners of the small triangle are pretty different.

But if we broke it into 1,000 layers and repeated a similar procedure, Sperner's Lemma tells us that there would still be a fully labeled triangle-- one where each person prefers a different room.

Now the three corners of this triangle correspond to pretty similar rent distributions.

So Curly gets room 1 for 160 thousandth of the rent.

Moe gets room 2 for 462 thousandth of the rent.

And Larry gets room 3 for 377 thousandth of the rent.

That leaves 1 one thousandth of the rent unpaid.

But the smaller we cut the triangles, the more precise it will be.

Being fair within $1.00 or so is probably good enough.

To be very precise, what it means to say that this is a fair division of the rent is that no one would rather have someone else's room for the price that the other person is paying.

At the given price distribution, everyone most prefers their room.

Curly got the cheap room.

And even though Moe got the balcony, Larry is happy, because he doesn't think the balcony is worth that much extra money.

What if Curly isn't there when they move in to express his room preferences?

No problem.

Last summer, a group of awesome undergraduate students proved that you can still fairly divide rent, even if one of the roommate's preferences are secret.

Just use their modified method, and Curly will still get a room he's happy with.

What if there are more than three roommates?

No problem.

Just use the higher dimensional triangles we talked about earlier.

For N roommates, you need an N minus 1 simplex.

The technique we just saw, using Sperner's Lemma to fairly divide something according to subjective preferences, has many other applications.

Francis Su outlined this use-- fairly dividing rent-- in a 1999 paper.

But his work was building on Forest Simmons who developed the method to fairly divide a cake and Martin Gardner who used it to divide up a list of chores.

We've included links to all those papers and to a website where you and your roommates can actually implement this method to fairly divide your rent.

What's something you wish you could fairly divide?

Maybe Sperner's Lemma could help.

See you next time on Infinite Series.

After we recorded this episode, another fantastic mathy YouTube channel-- Mathologer-- also released a video about fair division of rent.

In his video, Burkard emphasizes slightly different aspects of the problem and the proof techniques.

If you want to see two different perspectives on fair division, I highly recommend you check out his video as well.

Here at Infinite Series, we wanted to make sure that just in case you'd seen his video, you'll still get something completely new out of this one.

So here's a little appendix to the episode where I'll outline a proof for fairly dividing rent when one roommate's preferences are a secret.

Let's say Larry and Moe are moving into a new three-bedroom apartment.

Curly is going to move into the third bedroom.

But he hasn't said what room he wants or how much he's willing to pay.

Start with a triangle subdivided into further triangles, like we had before, so each vertex corresponds to a rent division.

Previously, we labeled every vertex with one of the three names and asked the person whose name was on the vertex which room they preferred at these prices.

Let's do something a little different now.

At each vertex, we'll ask both Larry and Moe which room they want.

And we record their preferences as a pair of numbers, like this.

On the sides where exactly one room is free, they'll both pick the same room.

On the main three vertices where exactly two rooms are free, we can assume they each pick a different free room.

Now this isn't a Sperner's labeling, but we can turn it into one.

For each of the vertices, relabel it 1 if the label is 1,1 1,2, or 2,1.

Relabel it 2 if it's 2,2, 2,3, or 3,2 and 3 if it's 3,3, 3,1, or 1,3.

Now that's a Sperner labeling, which means we can find an interior triangle labeled 1, 2, 3 by Sperner's Lemma.

Similar to before, if we divide the triangle into tiny enough pieces, the rent distribution given by the vertices of this triangle are approximately-- say within $1.00 or so-- of a fair division.

We just have to decide who gets what room.

The presence of all the numbers on the small triangle indicates that Larry and Moe are both happy with at least two rooms.

And importantly, these can't be the same two rooms since all three rooms must be preferred by at least one of them.

This means that no matter what room Curly picks, Larry and Moe can happily split the remaining two.

Every week, I'm impressed by the conversations you guys have in the comments.

You work through problems together, share stories, and answer each other's questions.

Community is such a vital part of mathematics.

So this week, instead of me responding to some comments, I wanted to highlight some of the responses you all gave to each other's comments.

First, Diwonkulous and several others remarked, "I think D-Wave would argue against your opening point of quantum computers not existing."

Well, D-wave might, but most other scientists would probably agree with me.

Here's Ayyy's response.

"D-Wave's computers are only, by definition, quantum computers and are very different from what is typically called a quantum computer.

D-wave's computers use quantum annealing as an optimization tool to find approximate answers to some NP-complete problems.

They aren't general purpose quantum computers, though.

KohuCaly gave several great responses.

When TheJared asked, "IF we have the math, is it possible to simulate a quantum computer?"

They replied, "Yes, it is.

It's relatively easy, but keep in mind, simulating a quantum computer takes exponentially more computations.

That's the whole point of it all.

When you have problems that take exponential time to solve and you manage to convert the problem into quantum computable form, you can use hardware quantum computers to solve it in polynomial time."

Finally, chintamani asked, I want to learn this math.

Please recommend something.

Well, most of the math behind quantum computers is just linear algebra.

Matrices are just a tool in linear algebra.

Google will show about an endless number of linear algebra resources.

But we wanted to second Raphael's recommendation to check out 3blue1brown's introduction to linear algebra series.

They're great.

There's a link in the description.

See you next time.

[MUSIC PLAYING]