Six people in a room. Every pair either knows each other or doesn't. Try to arrange
it so that no three of them all know each other, and no three are complete strangers. You will
not manage it — and not because you are bad at it.
Every pair joined by a line● acquainted● strangers▲ a trio of one kind
trios right now—possible arrangements—escapes foundnot searchedfewest trios possible—
—
—
Keyboard: focus the ring, then ←→
to walk the highlight from one pair to the next and Enter to flip that pair between
acquainted and strangers — the same thing clicking a line does.
35 — escape possible6 — no escape
↳ press Search every arrangement
and watch six people run out of room — then drop to five and press it again
What you're seeing
Six dots, one per guest. Every pair is joined by a line: amber if they know each other, blue if
they are strangers. There is no third option, and no pair is left out.
A trio is three people whose three lines are all the same colour. Three mutual friends,
or three mutual strangers. The page marks each one in red as it appears.
Click any line to flip it and try to clear the board. The trio count will not go to zero. Drop
to five people and it will, easily — so this is not a rule about crowds in general.
When you have had enough of trying, press Search every arrangement. With six people
there are 32,768 ways to draw the lines, which is few enough to check all of them. None escape.
The best any arrangement manages is two trios, never one.
This is the smallest case of Ramsey's theorem. Its content is that total
disorder is impossible: make a structure big enough and some regularity has to appear in it,
whether or not anyone put it there. Six is the exact size at which three-of-a-kind becomes
unavoidable. For four-of-a-kind the number is eighteen, and for five-of-a-kind nobody knows
it — it is somewhere between 43 and 46, and has resisted since 1930.
The rule, exactly. Colour every edge of the complete graph
Kn with two colours. Ramsey's theorem says some
K3 ends up monochromatic once n is large enough, and the
smallest such n is
R(3,3) = 6
The classical proof is one line of pigeonhole. Pick any person. They have five relationships in
two kinds, so at least three are alike — say three friends. If any two of those three are
friends with each other, those two plus the first make a trio. If no two of them are, the three
of them are mutual strangers. Either way a trio exists.
Verified in node (improve/verify/111-ramsey-party.js, 12 checks)
by total enumeration, not sampling — the impossibility is the claim, so a spot check
would be the wrong instrument:
All 32,768 two-colourings of K6 were generated and every one
contains a monochromatic triangle. Escapes: zero.
Goodman's bound is confirmed and attained: the minimum over all arrangements is exactly
two trios, not one.
The average arrangement holds exactly 5 trios, matching 20 · 2 · (½)³
— a check on the enumeration itself.
The pigeonhole step is checked rather than asserted: in every arrangement, at every
person, one colour covers at least three of their five relationships.
Exactly 12 of the 1,024 arrangements of five people escape, and every one of them is the
pentagon-and-pentagram, with two friends and two strangers each.
Negative control. Those 12 acquittals prove the trio-finder is not
simply crying "trio" at everything, and an all-amber K6 is correctly
reported with all 20 triangles monochromatic.
Negative control. Given three colours, six people escape easily. So this
is a fact about splitting in two, not about six being a crowd.
Negative control. Six people do not force four mutual friends
or four mutual strangers; an explicit arrangement avoids it. That needs eighteen.
Frank Ramsey proved the general theorem in 1928, aged 25, as a lemma inside
a paper on formal logic. He died two years later.