Three Colors - NFHN Reader

June 11, 2026 · 795

Sperner's lemma, the intermediate value theorem, Brouwer's fixed point, and Nash equilibrium: one coloring puzzle, scrolled.

Three colors, three rules, and a triangle there is no avoiding.

There is a game. You will lose it, and the way you lose it is one of my favorite ideas in math.

We'll start by taking a big triangle, we'll cut it into small ones, and we'll put a dot at every corner. Now color the dots with three colors (rust, cobalt, jade) under three rules:

The three corners of the big triangle get one of each. They're locked.
A dot on a side of the big triangle may only use the colors of that side's two endpoints.
Every interior dot is yours: any color, go wild.

The goal is to avoid creating a single rainbow triangle, a small triangle wearing all three colors. Go ahead.

Recolor any unlocked dot by clicking it. Corner dots are fixed; dots on a side may only use that side’s two colors. Try to reach zero rainbow triangles.

I did warn you that you'd lose. You can get the count down to one. In fact, you may have noticed something stranger: the count is always odd. Three, five, one; never two and, in particular, never zero.

This is Sperner's lemma, proved in 1928 by Emanuel Sperner, then a 22-year-old graduate student: every coloring that follows the three rules contains an odd number of rainbow triangles, and in particular at least one.¹

If you're like me, you probably found this pretty underwhelming. I don't blame you! Strangely enough what feels like a contrived parlor game ends up underwriting some really important results of the 20th century. By the end of this page it will have proven the intermediate value theorem, then Brouwer's fixed point theorem, and the existence of Nash equilibria.

Part I

One dimension, one idea

Before the triangle, flatten the game onto a line. A row of beads: the left end is locked rust, the right end locked cobalt, and the beads between are yours. How many gaps sit between two beads of different colors?

A path from rust to cobalt. Click the middle beads to recolor them; the number of two-colored gaps stays odd, no matter what.

It turns out it's an odd number, always. To see why, let's walk from left to right: you start on rust and end on cobalt, so you switch colors an odd number of times, and each two-colored gap is one switch. The rest of this post is this same idea in a nutshell: the boundary conditions guarantee the parity, and an odd count is at least one.

The two-dimensional proof is, I think, one of the most elegant arguments in mathematics, and it is also a walking tour.²

The setup

Take the puzzle from the top of this post, but bigger, and change how you look at it: this is a floor plan. Every small triangle is a room. The colored dots are the corners of their walls.

Doors

Now, a rule for doors. A wall is a door when its two ends are rust and

cobalt. Every other wall is solid. And notice: doors to the outside can only exist along the bottom of the big triangle, the one side where rust and cobalt are both allowed to live.

Rooms

Count the doors of any single room. A room with all three colors at its corners, a rainbow room, has a single door. A room with only rust and cobalt corners has

two (shaded gray). Any other room has none. No room can have three.

Take a walk

Step inside through a door on the bottom edge and keep walking: whenever the room you’re in has another door, go through it. You never face a choice; at most one other door exists. For the same reason, you can never circle back: re-entering a room would take a third door, and three doors in a room is impossible.

Every walk ends

There are finitely many rooms, so each walk must end, and only two endings exist: you pop back outside through another bottom-edge door (a round trip), or you hit a room with no second door. A dead end. And the only rooms with a single door are

rainbow rooms, so a dead end is the thing we were looking for.

The parity trap

The finish is pure counting. The bottom edge is the one-dimensional game from Part I: it starts

rust, ends

cobalt, so it has an odd number of doors. Round trips swallow boundary doors two at a time. Odd minus even pairs leaves at least one walk with nowhere to exit: it must dead-end in a rainbow room. (Rainbow rooms the outside never reaches come in pairs, joined by private corridors, drawn dashed, so the total count stays odd. That’s Sperner’s lemma, with jade watching from the sidelines the whole time.)

So the puzzle was never winnable. Every legal coloring hides an odd number of rainbow rooms, because the bottom edge, a one-dimensional game with its odd number of doors, leaves at least one walker stranded inside, and walkers can only strand in rainbow rooms.³

Sperner's lemma is a theorem of discrete mathematics, nary an epsilon in sight, which makes it a suspicious tool for proving theorems about continuous functions. What saves us is that the lemma does not care how fine you cut: divide the triangle into a million cells or a trillion, and the rainbow room is still there. The fact this guarantee survives every resolution means that we can take a limit.

Part III

The intermediate value theorem

The intermediate value theorem says a continuous function that starts below zero and ends above zero must cross it. "To get out of the basement you must pass the ground floor." Let's prove it as a consequence of Sperner's Lemma.

Color the interval by the sign of the function. Below zero, rust; at or above, cobalt. The hypothesis (starts below, ends above) locks the endpoints rust and cobalt, and we are playing the bead game again. Nothing about the game needed to be adapted; the hypotheses of the theorem are exactly its rules.⁴

Sample the function at n points and color each sample by sign: rust below zero, cobalt above. The two-colored cells are the doors of Part I. There’s always an odd number, and the first one brackets a root ever more tightly as n grows.

Now sample the interval at n points. The one-dimensional lemma fires: there is an odd number of two-colored cells, at least one, and the first one brackets a sign change inside a window of width 1/n. Double n and the lemma fires again. You get a sequence of shrinking brackets, each pinning the function to both signs within a vanishing distance, and they converge to a point c.⁵ If f(c) were positive, continuity would make f positive in a whole neighborhood of c, yet every bracket near c contains a rust point. Negative fails the same way. The only value left is f(c) = 0.

In one dimension this argument is admittedly close to bisection.⁶ The reason to prefer the coloring language is that bisection does not generalize: in two dimensions there is no interval to halve and no single bracket to follow, while the coloring argument passes to the triangle unchanged.

Take two identical sheets of paper, one lying flat on a table. Crumple the other (fold it, twist it, anything short of tearing) and drop it on top, landing anywhere within the flat sheet's outline. Brouwer's fixed point theorem says some point of the crumpled sheet sits right on top of its twin on the flat one. Stir a cup of coffee gently, no splashing: when the surface settles, some point sits where it began. Continuous rearrangements of a disk, or a triangle, or a square (topology sees a single shape⁷) always leave something untouched.

The claim

Take any continuous map f that sends the triangle into itself: stir it, swirl it, crumple it without tearing. Brouwer’s fixed point theorem says some point ends up right back where it started. The arrows show one such map: each point is flung along its arrow. Could a map outrun every single point?

Three shares

First, a coordinate system born for this problem. Every point in the triangle is a blend of the three corners (say 50%

rust, 30% cobalt, 20%

jade): three shares that always total 100%. Watch the shares shift as the point wanders.

Who loses?

Now bring back f, and watch the scoreboard. As the point moves to its image, its three shares change, yet they still must total 100%. So if the point moved at all, something had to give:

at least one share fell. That’s the coloring rule: paint each point with the color that lost the most

ground. Watch the readouts; the share falling hardest (↓) is the color the point turns. And the biggest drop always comes out of a share the point holds, since a 0% has nothing to lose.

It’s the game

Check what this rule does at the boundary. The

rust corner is 100% rust, the only share that

can drop, so it keeps its color. A point on the bottom edge has zero jade, so it must be rust or cobalt. These are

the rules of the coloring game, clause for clause. The map f imposed them all by itself.

Refine

So Sperner’s lemma fires: at every resolution there must be a rainbow cell, three neighboring points, one shedding rust, one shedding cobalt, one shedding jade. Keep refining. The cells shrink, and the lemma keeps delivering, forever.

f(x) = x

Shrink the cells toward nothing and the rainbow cells crowd around a limit point x. Near x, all three shares are trying to drop. But the shares of x must still sum to 100%, and the only way out is that none of them moves. The map failed to outrun x: f(x) = x. The swirl has a still point; every continuous map does.

Notice there weren't really any new ideas introduced. The map f, just by being continuous and trapped in the triangle, forces a legal coloring: paint each point by the share that shrinks the most.⁸ Sperner's lemma, which knows nothing about continuity, hands us a rainbow cell at every resolution: three points huddled arbitrarily close, each shedding a different share. Compactness squeezes those cells onto a single point x.⁹ At x, all three shares are trying to drop at once, but the three shares always total 100%, and you cannot lower all three parts of a whole. So nothing moves, and f(x) = x.

Game theory in 1949 was von Neumann's subject. His minimax theorem had settled two-player zero-sum games, where my loss is exactly your gain, and his book with Morgenstern treated everything beyond as a theory of coalitions. Nash, then a 21-year-old graduate student at Princeton, asked about the games this left out: interests that neither align nor oppose exactly, no coalitions, every player deciding alone. The question, in its smallest version: two players each pick one of two actions, simultaneously; payoffs land according to a little table. Some games have an obvious resting point. Others have none. Try matching pennies, where I want our coins to agree and you want them to disagree: whatever we're doing, someone wants to switch, forever.

Nash's reframe: let players mix. Instead of picking heads, pick "heads with probability p." Then everything a player might do is a dial from 0 to 1, and everything two players might do together is a point in a square. An equilibrium is a point where neither player can improve their lot by unilaterally moving their own dial: a profile that survives everyone's second-guessing simultaneously. Does such a point always exist?

It sure does, if you recast it as a fixed point problem and smack it with Brouwer. A square is a triangle as far as topology cares, so what's missing is a continuous map whose still points are the equilibria, and that map is what Nash built. Give each player a nudge toward temptation: compute how much each pure action would gain against the opponent's current mix, shift probability toward the gainers, renormalize. Tempted players move; untempted players stay. The result is a continuous map from the square to itself.¹⁰

Ann wins on a match, Bea on a mismatch. No pure strategy survives; the flow circles a single mixed equilibrium where both flip 50/50. Notice the orbit: the equilibrium exists, but the dynamics never settle on it.

A point the nudge map leaves in place is a point free of temptation, which is the definition of equilibrium. And the map must have an unmoved point: it is continuous, from a square to itself, so Brouwer applies. Every finite game, any number of players,¹¹ any payoffs: at least one equilibrium exists. Auction design and the modeling of markets rest on this theorem (it is the work that later won Nash the Nobel Prize), and from this altitude it is a corollary.¹² When Nash described the result to von Neumann, the story goes, von Neumann cut him off mid-sentence: "That's trivial, you know. That's just a fixed point theorem."¹³ He was right about the mathematics. The contribution was the reframing itself: equilibrium, stated correctly, is a fixed point, and the fixed point theorem already existed.

One caveat, visible in the matching pennies figure: the wandering profile orbits the equilibrium and never settles in. The proof is non-constructive. It guarantees that an equilibrium exists, but it offers no procedure for finding one, and the figure shows the most natural procedure failing. Computing Nash equilibria turns out to be hard in a precise sense, and PPAD, the complexity class that pins down how hard, is defined by the parity-of-paths argument from Part II.¹⁴

So the game was rigged from the start. All three theorems came from the same construction: discretize the continuous problem, color the sample so that the hypotheses fix the boundary, apply the lemma at every resolution, and let compactness pass to the limit. Notice that nothing was ever exhibited. We never produced a root, a fixed point, or an equilibrium. We counted, the count was odd, and an odd number is at least one.

Play the game once more on your way out; you will lose again. But you will lose for the same reason a continuous function cannot skip zero, a crumpled sheet cannot avoid its twin, and a finite game cannot escape equilibrium.

Sperner proved it as a lemma toward a cleaner proof of the invariance of dimension; fixed points were the last thing on his mind. The best tools rarely stay in the drawer they were built for. ↩
The doors-and-rooms framing follows Francis Su's write-up of Sperner's proof, the same source I leaned on when I first blogged this lemma in 2012. That version had figures that held still; this post is the one I wanted to write then, with figures you can poke. ↩
The same argument runs in any dimension: in 3D, tetrahedra with four colors, where the "doors" are rainbow faces and the induction hands you the parity of the boundary from one dimension down. Nothing new is needed, which is what makes it a great proof. ↩
My 2012 write-up called Sperner's lemma "The Discrete Mathematician's Intermediate Value Theorem." This section is the nickname, cashed out. ↩
Take the left endpoints of the brackets at n = 2, 4, 8, …; they live in a closed interval, so (Bolzano–Weierstrass) some subsequence converges to a point c, and every neighborhood of c inherits points of both colors. ↩
With one wrinkle: bisection follows a sign change, while the lemma counts all of them, and the odd count is the stronger fact. A function that wiggles across zero five times still shows an odd number of two-colored cells at every resolution. Parity is conserved; that's the law the figure is demonstrating. ↩
Any convex compact shape (disk, square, pentagon) can be continuously deformed onto the triangle and back, and fixed point theorems ride along under such deformations: conjugate the map, fix the point, deform back. So proving Brouwer for the triangle proves it for all of them. ↩
Two crumbs swept here. If several shares tie for the biggest drop, pick any, say the first; the boundary rules still come out legal because a color is never assigned where its share is zero. And at a point where no share drops, no color is needed, because that point is already fixed and the theorem is proved. ↩
Same compactness move as the interval: pick one rainbow cell per resolution, take a convergent subsequence of (say) their rust-shedding corners. The other two corners tag along since cell diameters vanish, and continuity of f promotes "shrinks at points arbitrarily near x" to "cannot grow at x" for all three shares at once. ↩
For our 2×2 games, with gains g for each pure action against the current mix: p′ = (p + g₀) / (1 + g₀ + g₁). Continuous, since maxima of linear things are continuous and the denominator is at least 1. One direction is immediate: at an equilibrium every gain is zero and nothing moves. The converse is the one lemma I'll wave at: if some action gains against the mix, some currently played action must pay below the mix's average, and the formula strictly drains probability away from it, so the profile moves. ↩
More players and more actions just upgrade the square to a product of simplices, a higher-dimensional convex compact, which Brouwer handles without blinking (see the previous footnote on shapes). ↩
Historical fine print: Nash's 1950 announcement leaned on Kakutani's fixed point theorem, a set-valued generalization of Brouwer that shrinks the argument to a paragraph and powers the Arrow–Debreu theorem on market equilibrium. The nudge map above is Nash's 1951 refinement, built to need plain Brouwer and nothing stronger. I proved Kakutani from Brouwer in 2012, by the recipe this essay keeps reusing: approximate, apply the finite tool, squeeze with compactness. ↩
The scene comes from Sylvia Nasar's A Beautiful Mind, reconstructed from interviews decades after the fact, so the quote is folklore with a good source rather than a transcript. Nasar also records Nash's own reading of the dismissal: he was aware that his non-cooperative framework implicitly challenged von Neumann's cooperative one, and he later understood the reaction partly in that light. ↩
PPAD (Papadimitriou, 1994) is the class of search problems reducible to "this graph of in/out-degree ≤ 1 has an odd number of dangling ends; find another one," which is the door-walk, verbatim. Computing a Nash equilibrium is PPAD-complete (Daskalakis–Goldberg–Papadimitriou 2006, Chen–Deng 2006); so is finding the rainbow room itself. The proof that an answer exists and the reason it's hard to find are the same walk through the same doors. ↩