Three Colors — Aftermath<br>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<br>ideas in math.
We'll start by taking a big triangle, we'll cut it into small ones, and<br>we'll put a dot at every corner. Now<br>color the dots with three colors (rust ,<br>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<br>two endpoints.
Every interior dot is yours: any color, go wild.
The goal is to avoid creating a single rainbow triangle, a small triangle<br>wearing all three colors. Go ahead.
rainbow triangles3your best–<br>ShuffleReset
click to recolorclick to recolorclick to recolorclick to recolorclick to recolorclick to recolorclick to recolorclick to recolorclick to recolorclick to recolorclick to recolorclick to recolor3 rainbow triangles. An odd number, every time.
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.<br>I did warn you that you'd lose. You can get the count down to one.<br>In fact, you may have noticed something stranger: the count is always odd.<br>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<br>graduate student: every coloring that follows the three rules contains an odd<br>number of rainbow triangles, and in particular at least one.1
If you're like me, you probably found this pretty underwhelming. I don't blame you!<br>Strangely enough what feels like a contrived parlor game ends up underwriting some really<br>important results of the 20th century. By the end of this page it will have proven<br>the intermediate value theorem, then Brouwer's fixed point theorem, and the existence of<br>Nash equilibria.
Part I<br>One dimension, one idea
Before the triangle, flatten the game onto a line. A row of beads: the left<br>end is locked rust , the right end locked<br>cobalt , and the beads between are yours. How many gaps<br>sit between two beads of different colors?
two-colored gaps3 · odd<br>123STARTEND<br>A path from rust to cobalt. Click the middle beads to recolor them; the number of two-colored gaps stays odd, no matter what.<br>It turns out it's an odd number, always. To see why, let's walk from left to<br>right: you start on rust and end on cobalt, so you switch colors an odd number<br>of times, and each two-colored gap is one switch. The rest of this post is<br>this same idea in a nutshell: the boundary conditions guarantee the parity,<br>and an odd count is at least one.
Part II<br>Doors and rooms
The two-dimensional proof is, I think, one of the most elegant arguments in<br>mathematics, and it is also a walking tour.2
The proof, on foot1 / 6<br>OUTSIDE
The setup<br>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<br>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<br>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<br>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<br>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<br>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<br>rainbow rooms, because the bottom edge, a one-dimensional game with its odd<br>number of doors, leaves at least one walker stranded inside, and walkers can<br>only strand in rainbow...