Classic (handshake lemma) · Combinatorics
Handshake lemma
Prove that in any finite gathering, the number of people who have shaken hands an odd number of times is even.
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 2 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
- EGMO 2026 Problem 1: solution, and four rectangles that isolate a cellA full solution to EGMO 2026 Problem 1: the four-cell construction, the parity proof that every board beats it, and the signal in the statement.
- How to build a problem-solving notebook that actually worksMost problem notebooks are copied solutions nobody reopens. Index yours by the clue in the statement, not by topic, and test it from the clue side.
- Extremal graph problems for beginners: the bound and the exampleAn extremal graph problem is two problems: a bound nobody can beat and an example that reaches it. How to spot one, and which vertex to pick first.
- How a double counting proof is actually builtDouble counting proofs are always the same three steps, and only one of them is hard. The skeleton, five worked examples, and where they go wrong.
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
- Erdős–SzekeresClassic (Erdős–Szekeres) · difficulty 5/6
- All 89 problems →