Three Colors

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:

1. The three corners of the big triangle get one of each. They're locked.
2. A dot on a side of the big triangle may only use the colors of that side's two endpoints.
3. 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.

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.

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?

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

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.

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

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.

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

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.