PENNEY'S GAMEnontransitive from k=3first triangle at k=4OEIS · 3 new sequences
Coin-flip sequences are nontransitive: for any sequence you name, another beats it, in a ring that never ends. At length three the ring is a square — and search as you like, there is no triangle inside it. The smallest rock-paper-scissors triangle does not exist until length four.
In Penney's game two players each name a string of coin-flips. A fair coin is tossed until one string shows up as a run; that player wins. The startling part, known since 1969, is that the game is nontransitive: no sequence is best. Whatever you pick, I have one that beats it — and whatever I pick, a third beats that.
At three flips the nontransitivity is a clean loop of four. HHT beats HTT beats TTH beats THH beats HHT — four sequences in a ring, each devouring the next:
I · the ring you knowk=3 · the famous 4-cycle
Each arrow A → B means A beats B; the fraction is the exact probability that A appears first. Computed live in your browser by Conway's leading-number formula. The four odds — read them around the loop — are the same two values twice: 2/3 and 3/4.
A rock-paper-scissors made of nothing but a fair coin. So Penney's game is nontransitive at length three. Now ask the obvious question: where is the triangle? Rock-paper-scissors is three things, not four. Surely three of these eight sequences cycle directly — A beats B beats C beats A.
Hunt for it. Pick any three of the eight length-three sequences and the machine settles their three matchups and tells you whether they cycle or fall into rank.
II · hunt the trianglepick any 3 of the 8
Pick three sequences above.
A triple is decided when none of its three pairs is a tie. A decided triple is cyclic (a directed triangle) when each sequence beats exactly one of the other two; otherwise it is transitive — one sequence beats both, a clean 1st/2nd/3rd.
You will not find one. The scan confirms it: of the 56 triples of three-flip sequences, every decided one is transitive. Zero triangles. The nontransitivity is real, but at length three it lives only in the longer loop — the 4-cycle is the smallest cycle there is.
The cycle is a square. The triangle you expect from rock-paper-scissors simply isn't there yet.
Push to four flips and the triangle finally arrives — 14 of them. Here is one, proven the same way:
III · the first trianglesk=4 · 14 of them
Each line is one directed edge with its exact odds; the three close into a loop. There are 14 such triangles among the 16 four-flip sequences — the onset of a count that grows fast.
What grows from the onset
Track three honest quantities of the whole tournament as the strings get longer. None of the three was in the On-Line Encyclopedia of Integer Sequences when this page was made; all three are now staged for submission, each computed exactly and cross-checked two independent ways.
IV · three new sequencescomputed live · k=1…9
sequence (function of string length k)
k = 1, 2, 3, …
recomputing…
Filled by recomputing the tournament in your browser. The "nontransitive triples" row is the one that starts 0, 0, 0, 14 — the missing triangle, made into a sequence: it is exactly the length at which rock-paper-scissors becomes possible.
The whole shape: one whirlpool, two drains
Counting triangles is counting the local cycles. Step back and ask the global question: draw the whole tournament — every pattern, every "beats" arrow — and what does the picture look like? A ladder with a champion at the top? A few rival cliques? Neither. From length four on, the answer is startlingly simple, and it has a name in graph theory: the tournament is almost entirely one strongly-connected whirlpool.
"Strongly connected" means: pick any two patterns in it, and you can walk from the first to the second along a chain of strict upsets — A beats X beats Y beats … beats B — and walk all the way back the same way. Dominance eats its own tail so thoroughly that no pattern is above any other. There is no best. There is no worst — with exactly two exceptions.
V · one whirlpool, two drainsstrongly connected · k=5, live
length k
patterns 2^k
whirlpool (strongly connected)
drains (sinks)
strays
recomputing…
Pick two of the 32 five-flip patterns. The machine finds a chain of strict upsets from one to the other — both ways — proving they sit in the same whirlpool.
and
A sink (drain) is a pattern that beats no one — its column of odds is all ≤ ½. For every length k ≥ 3 there are exactly two, and they are always the constant runs HH…H and TT…T: name all-heads or all-tails and any thoughtful opponent has your number. Everything else (from k = 4 on) is one whirlpool of size 2k−2. There are no sources: no pattern is unbeaten.
No pattern is best; only two are worst. Between the all-heads drain and the all-tails drain, every other coin-word spins in a single current where beats leads, eventually, back to itself.
A cycle of every length
How rich is that whirlpool? As rich as a directed graph can be. It is pancyclic: it contains a directed cycle of every length from the shortest (a triangle — the girth is 3 once k ≥ 4) all the way up to a grand tour that visits all 2k−2 patterns and returns (a Hamiltonian cycle). Ask for any length and the current has a loop exactly that long. At k = 3 the lone whirlpool is only the famous 4-cycle, so it has a cycle of length 4 and nothing else; one flip later, every length from 3 up appears.
VI · ask for a cycle of any lengthpancyclic · k=5
length7
A directed cycle of the requested length in the k = 5 whirlpool, each arrow a strict upset with its exact odds. The witness for each length was found by search offline and is re-checked edge-by-edge in your browser — a wrong one would read EDGE CHECK FAILED, not slip through. Every length 3…30 works, up to the length-30 grand tour of the whole whirlpool; that is what pancyclic means. Offline the same is proven exactly for k ≤ 4 (Held–Karp) and by exhibited, edge-checked witnesses for k = 5, 6, 7.
Why the square comes before the triangle
Conway's rule explains it. Who-beats-whom is governed by how a sequence's tail overlaps another's head (and its own — see Always Bet Second for the mechanism). At three flips the overlap structure is too coarse to seat three mutually-cycling sequences: any three you settle always leave one that beats the other two. The cyclic tension has to route the long way around, through four. Add a flip and the overlaps gain enough resolution for a true three-way standoff — and fourteen of them appear at once. The same coarseness is why, at k = 3, only four of the eight patterns manage to join a cycle at all: the two constant runs drain out, and the two perfect alternations HTH, THT are left stranded between the tiers until the next flip pulls them into the whirlpool.
It is a small, exact fact about a famous game, and it has the shape this place likes: the surprise (no triangle where rock-paper-scissors should put one) is not a vibe but a thing you can scan for and fail to find, then watch arrive one length later, then count forever. The counting is the contribution: three sequences the world's catalogue of sequences did not have.