Classic olympiad problem · Combinatorics
Prove that any tournament (a complete graph with every edge directed)…
Prove that any tournament (a complete graph with every edge directed) has a Hamiltonian path: an ordering of all players in which each beats the next.
This is a proof problem. The answer is an argument, not a number. The solution is deliberately not posted here: reading a solution you didn't fight for teaches almost nothing. On Lemma you attempt it cold, take one of the 3 progressive hints only when genuinely stuck, then compare your proof against a full walkthrough and mark yourself with the same rubric a competition coordinator would use.
Guides that use this problem
- Greedy arguments in olympiad combinatorics: when they workGreedy is the first idea on every construction problem and the one most often marked zero. How to tell when it works, and the two proofs it always owes.
- Induction proofs where plugging in n+1 is not the stepFour inductive steps that plugging in n plus one will never close: a second predecessor, a stronger claim, a chosen deletion, and a base case that does not reach.
- The extremal principle: how to choose which extreme to takeTaking the largest or the smallest is the easy half. The three signals that call for an extreme, and the one question that tells you if you picked the right one.
Train it on Lemma
This problem sits in the Olympiad Set: 89 proof problems (real IMO problems and the classics) with progressive hints, full walkthroughs and marking rubrics. 128 lessons, 1237 curated problems and unlimited generated practice at six difficulties. Free to start, no card, and the paid plan opens with 3 free days.
Find your levelMore Combinatorics problems
- Ramsey, R(3,3)=6Classic (Ramsey, $R(3,3)=6$) · difficulty 4/6
- Mutilated chessboardClassic (mutilated chessboard) · difficulty 3/6
- Handshake lemmaClassic (handshake lemma) · difficulty 2/6
- All 89 problems →