Graph Theory and Double Counting
The degree sum is (so the number of odd-degree vertices is even). A tree on vertices has edges and at least two leaves. A graph is bipartite iff it has no odd cycle. Mantel/Turán: a triangle-free graph on vertices has at most edges; Ramsey .
The olympiad step is recognizing the graph: people and acquaintances, cities and roads, numbers and a relation. Once it is a graph, the problem is usually a degree count, an induction removing a leaf or a minimum-degree vertex, or an extremal bound. Write "consider the graph whose vertices are… and whose edges are…" as the first sentence.
Count the same set of pairs (or triples) two ways. Incidences between points and lines, between students and clubs, between subsets and elements: gives an equation or, with an inequality on one side, a bound.
Double counting proves the handshake lemma, Fisher's inequality, and most "show that some element is in at least sets" claims: count (element, set) pairs by sets to get the total, divide by the number of elements to get the average, and some element meets or beats the average. Combined with convexity ( is minimized when degrees are equal), it yields the sharp bounds.
In a graph with vertices and more than edges, show there is a triangle (Mantel). Suppose not; for each edge , (no common neighbor). Summing over edges: . By Cauchy–Schwarz, . So , i.e. .
Games, Monovariants and Combinatorial Geometry
To show the first player wins without finding the strategy: strategy stealing (an extra move never hurts). To show the second player wins: a pairing/mirroring strategy. For take-away games, classify positions as P (previous player wins) or N by backwards induction, then find the pattern (usually a residue condition).
A winning strategy must handle EVERY opponent move; a proof that describes only one line of play proves nothing. Pairing strategies are complete by construction (every move has a paired response); P/N analysis is complete by induction. Say which one you are using and why it covers all cases.
A quantity that strictly decreases (or increases) and is bounded proves the process ends. Choose it so every legal move changes it: number of inversions, sum of squares, a potential function with well-chosen weights.
The USAMO "show the process terminates / show at most steps" is always a monovariant. For a bound on the number of steps, the monovariant must be an integer with a known range; the number of steps is at most the range. If no single quantity works, use a lexicographic pair.
Finite point sets in the plane: convex hull arguments (the extreme points), the extremal principle (closest pair, smallest triangle), pigeonhole on regions (divide the square into pieces), and colorings/parity of lattice points. Sylvester–Gallai: non-collinear points always determine a line through exactly two.
Combinatorial geometry problems are pigeonhole or extremal problems wearing coordinates. Divide the region into pieces small enough that two points in one piece are close; pick the point farthest from a line and argue with areas; or take the convex hull and remove a vertex for induction. Diagrams help find the argument and are worth zero in the write-up — every claim about the picture needs a sentence.
A "strategy" that assumes the opponent plays a certain way; a monovariant that is bounded only if the process ends (circular); and a geometry argument that depends on a generic picture (three points collinear breaks it).
Two players alternately place dominoes on a board ( even); the player who cannot move loses. Who wins?
Show the answerHide the answer
The second player, by symmetry: reflect every move through the center point of the board. For even the center is a grid point (a corner shared by four cells), so no domino covers it, and a domino and its reflection never overlap — a domino overlapping its own reflection would have to contain the center. Hence the reflected move is always available, and the second player never runs out of moves first.
Points in the Plane: Regions, Hulls, Extremes
For a finite point set in the plane: (1) cut the region into pieces so small that two points in one piece do what you want, and count pieces against points; (2) take the convex hull and split into cases by how many points it has; (3) choose an extremal pair — a closest pair, a point and line at minimal positive distance — and show a violation would produce a more extreme one.
Each opening turns geometry into a counting or ordering statement. Pigeonhole on regions works because diameter is monotone: two points in a set of diameter are within . The hull works because a point set is in “convex position” exactly when every point is on its hull, so hull size measures how far the set is from the conclusion. The extremal pair works because a finite set of positive numbers has a minimum, and geometry lets you manufacture a smaller one from any counterexample.
Prove that among any points in a unit square, some three lie in a closed disc of radius .
Step 1 — cut the square into squares of side . Since , some small square contains at least points.
Step 2 — a square of side fits in the disc around its center with radius half its diagonal, , and because .
How to find it. “Three points” means pigeons for holes: , so the square is cut into . Then check that the hole fits in the required disc — here with little room to spare.
Five points in the plane, no three collinear. Prove that four of them are the vertices of a convex quadrilateral. (Esther Klein.)
Step 1 — if the convex hull has or vertices, any four hull vertices (in the first case) or the four hull vertices (in the second) form a convex quadrilateral.
Step 2 — otherwise the hull is a triangle with the other two points inside. The line does not pass through , or (no three collinear), so it splits the three vertices : two of them, say and , lie on the same side.
Step 3 — the four points are in convex position, i.e. none lies inside the triangle of the other three. If one did, the line through it and one of the other three points would separate the remaining two. But line does not separate from (Step 2), and line does not separate from (both are inside the triangle). Checking the cases: inside would make line separate and ; inside likewise; inside would make line separate and ; inside likewise. So is a convex quadrilateral.
How to find it. Case on the hull. The only bad case has points inside a triangle, and a line through the two inner points is the one object that sorts the three vertices.
A finite set of points in the plane is not contained in one line. Prove that some line passes through exactly two of the points. (Sylvester’s problem, 1893; this proof is L. M. Kelly’s.)
Step 1 — consider all pairs with a line through at least two of the points and a point not on . There are such pairs (the set is not collinear) and finitely many; choose one with the distance from to as small as possible. Let be the foot of the perpendicular from to .
Step 2 — suppose contains three of the points. Two of them, and , are on the same side of (or one is itself); label them so that is between and (possibly ).
Step 3 — now look at the line and the point . The distance from to line is at most the distance from to line (A lies on segment ), and that is less than : in the right triangle the altitude from is shorter than the leg . So is a pair with smaller distance — a contradiction.
Step 4 — hence contains exactly two points.
How to find it. The conclusion is about a line with few points; an extremal line is the natural candidate, and “closest point to a line” is the measure that a third point on the line lets you beat.
In Example 2 the tempting shortcut is “take the convex hull; it has at least four vertices”. Five points , , , , have hull the triangle on the first three — no three collinear, yet only three hull vertices. The hull case split is the proof precisely because this case exists; skipping it proves the easy half. Here the line through and is , with and on the far side, and those four points form the convex quadrilateral.
Ten points lie in an equilateral triangle of side . Prove that two of them are at distance at most .
Show the answerHide the answer
Cut the triangle into equilateral triangles of side by lines parallel to the sides at distances one third of the height. Ten points in nine closed pieces: two share a piece, and two points of an equilateral triangle of side are at distance at most (its diameter is its side).