Olympiad | Combinatorics Problems Solutions

But here’s the secret:

At a party, some people shake hands. Prove that the number of people who shake an odd number of hands is even.

Whenever you see sums of numbers counting relationships, try counting the total number of pairs or triples in two ways. 4. Extremal Principle: Look at the Extreme Pick an object that maximizes or minimizes some quantity. Then show that if the desired condition isn’t met, you can find a contradiction by modifying that extreme object.

When stuck, ask: “What’s the smallest/biggest/largest/minimal possible …?” 5. Graph Theory Modeling: Turn the Problem into Vertices & Edges Many combinatorial problems—about friendships, tournaments, networks, or matchings—are secretly graph problems. Olympiad Combinatorics Problems Solutions

This is equivalent to showing every tournament has a Hamiltonian path. Use induction: Remove a vertex, find a path in the remaining tournament, then insert the vertex somewhere.

Let’s break down the most common types of Olympiad combinatorics problems and the strategies to solve them. The principle is deceptively simple: If you put (n) items into (m) boxes and (n > m), at least one box contains two items.

A finite set of points in the plane, not all collinear. Prove there exists a line passing through exactly two of the points. But here’s the secret: At a party, some

Count the total number of handshakes (sum of all handshake counts divided by 2). The sum of degrees is even. The sum of even degrees is even, so the sum of odd degrees must also be even. Hence, an even number of people have odd degree.

In a tournament (every pair of players plays one game, no ties), prove there is a ranking such that each player beats the next player in the ranking.

A knight starts on a standard chessboard. Is it possible to visit every square exactly once and return to the start (a closed tour)? Use induction: Remove a vertex

Take a classic problem like “Prove that in any set of 10 integers, there exist two whose difference is divisible by 9.” Apply the pigeonhole principle. You’ve just taken the first step into a larger world.

Color the board black and white in the usual pattern. A knight always moves from a black square to a white square and vice versa. For a closed tour, the knight must make an equal number of black and white moves, but there are 64 squares. Since 64 is even, a closed knight’s tour is possible in theory—but parity alone doesn’t guarantee it; it’s a starting point for deeper invariants.