Every Tournament Contains a Winning Chain (Rédei's Theorem)

Six players, round-robin: everyone plays everyone once, every game has a winner, and each result is an arrow from winner to loser. The outcome is usually a mess. A beats B, B beats C, C beats A — cycles everywhere, no undefeated champion, no honest ranking. And still, you can always seat all the players in one row so that each player beat the next. One unbroken chain of wins through everybody, no matter how chaotic the arrows fell. That guarantee has a name, and a two-line proof idea.

A tournament here means exactly this: between every pair of players there is one arrow — one direction, never both, never neither. Count the games and you are choosing pairs: $\binom{n}{2} = \tfrac{n(n-1)}{2}$. That single “exactly one arrow” fact carries the whole proof.

The obvious plan fails

The tempting move is to crown the strongest player and build the line outward. But a tournament can have no strongest player: in the rock-paper-scissors triangle, whoever you crown, somebody beat them. Greedy chains stall with players stranded outside. The lesson is not that the theorem is hard. It is that building the line from scratch is the wrong plan.

Grow it by one

Suppose you already have a line for everyone except one newcomer. Compare the newcomer with the front of the line: if the newcomer won, put them first. Compare with the back: if the back player won, hang the newcomer off the end. The only remaining case is that the newcomer lost to the front and beat the back — so, walking left to right, the results flip somewhere from “beats the newcomer” to “loses to the newcomer”.

Take the last player who still beats the newcomer. The very next player does not, and “does not beat” in a tournament means “loses to”. So the pivot beats the newcomer and the newcomer beats the pivot’s successor: drop them in that gap and every arrow still points forward. One of the three cases always fires, so a line for $k$ players always extends to $k+1$. A single player is already a line, and induction climbs the rest of the ladder.

Poke it before trusting it

Rock-paper-scissors is the smallest interesting test. No best player exists, and the theorem never promised one: a Hamiltonian path is not a ranking and crowns nobody. Three valid lines exist here (start anywhere and follow the loop). There is also a quiet structural bonus, due to Rédei in the same 1934 paper: the number of Hamiltonian paths in any tournament is odd. And an odd number cannot be zero, which re-proves existence in one sentence.

The completeness hypothesis is doing real work. Erase a single game, so one pair never met, and a player can end up unreachable — the guarantee dies with the missing arrow. This is not magic for arbitrary piles of arrows; it needs every pair decided.

From line to loop

The line has two loose ends. If the tournament is strongly connected — you can reach anyone from anyone by following arrows — the line can be closed into a full cycle through all players. That stronger statement is Camion’s theorem, and the video leaves it as the cliffhanger: when exactly can a winning line be bent into a winning loop?

The move to keep is the induction pattern itself: never build the object, grow it by one and prove the newcomer always fits. The same discipline of filters-then-survivor runs the classification in which polynomials map ℚ onto ℚ — a very different battlefield, same way of winning.