Rent Division

You and two friends rent an apartment. The rooms are not equal: one is big and sunny, one is tiny, one gets the morning noise from the street. The rent is one number — say $3000 — and somehow you have to split it three ways. Charge equally and whoever got the closet feels robbed. Charge "by the square meter" and tastes still differ: maybe someone would gladly pay more for the quiet room.

The real question is sharper than "what's fair in dollars." It is: can we assign rooms and prices so that no roommate would rather have someone else's room-and-price deal? When that holds, the split is called envy-free — nobody envies anybody.

It sounds like the kind of thing that might be impossible to arrange. Astonishingly, under very mild assumptions it is always possible — and the proof comes not from economics but from a piece of combinatorial topology about coloring triangles.

Three roommates, three rooms, total rent $3000. Each roommate secretly values the rooms differently (sliders below set how much each person would pay for each room). The solver searches for a price on each room so that, at those prices, every roommate's favorite room is a different one — that is an envy-free assignment.

<p class="hint">{{hint}}</p>
<div id="grid" class="grid"></div>
<div class="status" id="status">{{status_initial}}</div>
<div id="result" class="result"></div>
<div class="btns">
  <button id="find" type="button">{{btn_find}}</button>
  <button id="rand" type="button" class="ghost">{{btn_rand}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.grid { display: grid; grid-template-columns: auto repeat(3, 1fr); gap: .4rem .7rem; align-items: center; }
.h { font-weight: 700; color: #1d3557; font-size: .85rem; text-align: center; }
.name { font-weight: 700; color: #1d3557; font-size: .9rem; }
.vcell { display: flex; flex-direction: column; gap: 2px; }
.vcell input { width: 100%; }
.vcell span { font: 600 12px ui-monospace, monospace; color: #555; text-align: center; }
.status { font-size: 1rem; font-weight: 600; margin: .8rem 0 .3rem; min-height: 1.4em; }
.status.ok { color: #0a7d33; }
.status.bad { color: #c92f3c; }
.result { display: grid; grid-template-columns: repeat(3, 1fr); gap: .5rem; margin: .3rem 0 .6rem; }
.card { border: 1px solid #cdd9e3; background: #e8eef3; border-radius: 8px; padding: .5rem; text-align: center; }
.card .who { font-weight: 700; color: #1d3557; }
.card .room { font-size: .85rem; color: #333; }
.card .price { font: 700 16px ui-monospace, monospace; color: #0a7d33; margin-top: 2px; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Notice the asymmetry. Checking a proposed split is instant: at the given prices, ask each person which room they'd pick, and see whether the three choices are all different. Finding the split is the work — but unlike many puzzles on this site, a solution is guaranteed to exist. Move the sliders however you like and press Find a fair split: it never comes back empty-handed.

What makes rent division remarkable is not that it is hard — it is that it is provably solvable, every single time.

• The status is settled. In 1999 the mathematician Francis Su published "Rental Harmony: Sperner's Lemma in Fair Division," proving that under mild conditions an envy-free rent split always exists. This is a solved problem with a constructive guarantee, not an open question.
• The engine is Sperner's lemma (Emanuel Sperner, 1928). Picture all the ways to split $3000 among three rooms as points of a triangle. Triangulate it finely, and label each corner by which room that roommate would choose at those prices. Sperner's lemma guarantees at least one tiny sub-triangle whose three corners carry all three different labels.
• A fully-labeled triangle is an (almost) envy-free split. Its three corners are three nearly-identical price vectors at which the three roommates each prefer a different room — so you can hand each person their favorite. Shrink the triangulation and the approximation becomes exact in the limit.
• Mild assumptions only. Each person must always be willing to take some room if it is free (no infinitely-fussy tenants), and preferences must vary continuously with price. That's it.

So rent division sits in the friendly company of problems with existence theorems — like the stable matching that always pairs up couples, or the Nash equilibrium every finite game must have. The math doesn't just hope a fair split exists; it hands you the recipe to find it.

"Divide this fairly among people who want different things" is everywhere, and the rent problem is its clearest case:

• Real apartments. The New York Times built a public rent-division calculator on exactly this theorem; the academic site Spliddit offers it to anyone with squabbling roommates.
• Inheritances and divorce. Splitting a house, a car, and a record collection between heirs is the same shape: indivisible items plus a money side-payment, made envy-free.
• Chores and shared duties. Replace "rent" with "hours of unpleasant work" and the math flips into dividing burdens so nobody feels overloaded.
• Computing resources. Cloud schedulers and shared clusters borrow fair-division ideas to split CPU, memory and bandwidth so no tenant envies another's allocation.

Understand the rent split and you've met fair division — the field that turns "that's not fair!" from a complaint into something you can actually compute and prove.

Rent division hides a quietly beautiful fact: the loudest household argument — who pays what for which room — has a mathematically guaranteed peaceful answer. Color the corners of a triangle by everyone's preferences, invoke a lemma from 1928, and out falls a price split that leaves no one envious.

So the next time roommates square off over the big bedroom, you can promise more than a compromise. You can promise a split that is provably envy-free — and, unlike P vs NP and the genuinely hard problems on this site, this one comes with both the existence guarantee and the algorithm to find it.