Book 1. Foundations of Olympiad Combinatorics

Key Idea

Counting begins not with a formula, but with the question: what is chosen first, what is chosen next, and does the next choice depend on the previous one? The sum rule is used for disjoint cases, while the product rule is used for sequential choices when the number of options at each step is known.

The olympiad difficulty is often not arithmetic, but avoiding double counting and missing forbidden cases. Therefore this module emphasises a careful order of choice, casework, and complement counting.

Basic Facts

• If an object can be obtained in \(a\) ways of one type or \(b\) ways of another type, and the types are disjoint, there are \(a+b\) ways.
• If the first step has \(a\) choices and after each first step the second has \(b\) choices, there are \(a\cdot b\) ways.
• If the number of choices on a later step depends on an earlier step, write a product by cases or draw a choice tree.
• Complement counting: sometimes it is easier to count all objects and subtract the forbidden ones.
• Overcounting happens when the same object can be obtained in several ways; then choose a different order or divide by the number of repetitions.

When to Use This Method

• You need to count numbers, words, paths, selections, or colorings with simple restrictions.
• The condition naturally splits into disjoint cases.
• Forbidden objects are easier to count than allowed objects.
• There is a danger that different descriptions produce the same object.

How to Recognise the Method

The word “or” often suggests the sum rule, provided the cases are disjoint. Words like “first”, “then”, and “after that” suggest the product rule. If the statement says “at least one”, “not less than one”, or “without such a property”, check the complement method.

If several objects are chosen, ask: does order matter? If order does not matter, one cannot simply multiply sequence choices without later correction.

Typical Mistakes

• Adding choices when the choices must be made simultaneously.
• Multiplying cases that overlap.
• Forgetting that the first digit of a number cannot be \(0\).
• Counting “at least one” directly when complement counting is shorter.
• Counting the same object twice because it was chosen in different orders.

Mini-Checklist

• What exactly counts as one object?
• Does the order of choices matter?
• Are the cases truly disjoint?
• Are forbidden objects easier to subtract?
• Does a later choice depend on an earlier one?
• Can the same object be obtained in several ways?

Key Idea

A permutation is an arrangement of objects in order. The key difference from simple selection is that order is part of the object. If all objects are distinct, \(n\) objects can be arranged in \(n!\) ways. If some objects are identical, overcounting from permuting identical copies must be removed.

Olympiad permutation problems rarely reduce to one formula. More often, one needs the right device: glue a block, subtract forbidden adjacencies, fix a rotation in circular seating, or split by positions.

Basic Facts

• \(n\) distinct objects can be arranged in a line in \(n!\) ways.
• If \(k\) objects are chosen and ordered from \(n\) distinct objects, the number of ways is \(n(n-1)\cdots(n-k+1)\).
• If among \(n\) objects there are identical groups of sizes \(a,b,c,\ldots\), the number of distinct permutations is \(n!/(a!b!c!\cdots)\).
• In circular seating, rotations are considered the same, so \(n\) distinct people can be seated at a round table in \((n-1)!\) ways.
• If several objects must be together, glue them into one block and then count the internal order of the block.

When to Use This Method

• You need to arrange people, books, letters, digits, or objects in a row or around a circle.
• The statement contains “next to”, “not next to”, “in a certain order”, or “in fixed positions”.
• There are repeated letters or repeated objects.
• It is easier to count all arrangements and subtract forbidden ones.

How to Recognise the Method

If objects must be together, try a block. If objects must not be together, it is often easier to subtract cases where they are together. If the arrangement is circular, first fix one object or use \((n-1)!\). If there are identical letters, first count as if they were distinct and then divide by permutations of identical copies.

For forbidden positions, ask whether the restrictions are independent or overlap. If they overlap, inclusion-exclusion may be needed.

Typical Mistakes

• Counting circular seating as linear seating.
• Forgetting the internal order of a glued block.
• Subtracting forbidden cases but forgetting that several restrictions can hold at once.
• Dividing by factorials of repeated objects when the objects were already treated as indistinguishable.
• Confusing “\(A\) before \(B\)” with “\(A\) next to \(B\)”.

Mini-Checklist

• Are the objects distinct or are some identical?
• Is the arrangement linear or circular?
• Are there blocks that must stay together?
• Is “not adjacent” easier directly or by complement?
• Does order inside the chosen group matter?
• Can forbidden conditions overlap?

Key Idea

A combination is a selection of objects without regard to order. If the order of selection is not part of the answer, sequential counting usually overcounts. The number of ways to choose \(k\) objects from \(n\) is denoted by \(\binom{n}{k}\).

In olympiad combinatorics, combinations are more than a formula. They encode objects: positions of ones, vertices of a polygon, boundaries of a rectangle, elements of a subset, or places for dividers.

Basic Facts

• \(\binom{n}{k}\) is the number of ways to choose \(k\) objects from \(n\), ignoring order.
• \(\binom{n}{k}=\binom{n}{n-k}\): choosing \(k\) objects is the same as choosing the \(n-k\) objects not taken.
• Pascal's identity: \(\binom{n}{k}=\binom{n-1}{k}+\binom{n-1}{k-1}\).
• Complement counting: “at least one” is often counted as all cases minus cases without the property.
• Choosing nonconsecutive elements often reduces by shifting: replace \(a_1<\cdots

When to Use This Method

• You need to choose a team, subset, positions, vertices, or a collection of objects.
• The order of choice does not matter.
• The problem says “exactly \(k\)”, “at least \(k\)”, or “at least one”.
• You need to prove a combinatorial identity by counting the same collection in two ways.

How to Recognise the Method

If an object is completely determined by a set of chosen elements, use combinations. If it is determined by positions of special symbols, choose positions. If the condition says “not consecutive”, write the chosen numbers as \(a_1<\cdots

If a formula looks algebraic, ask: what does the left-hand side count, and what does the right-hand side count?

Typical Mistakes

• Counting ordered choices when order does not matter.
• Forgetting to subtract forbidden cases in “at least” problems.
• Using the combination formula without saying what is being chosen.
• Confusing choosing \(k\) objects with partitioning objects into groups.
• In nonconsecutive selection problems, forgetting the required gaps.

Mini-Checklist

• Is one answer a set or an ordered list?
• Which elements are being chosen?
• Can the complement be counted?
• If there is a “not adjacent” condition, where are the required gaps?
• If proving an identity, what common object do both sides count?
• Do we need to split by the number of objects of different types?

Key Idea

Double counting means counting the same set of objects in two different ways. The result may be an equality, an identity, an average, or a proof that an object with a desired property must exist.

Most often, we count pairs: \((student,club)\), \((vertex,edge)\), \((subset,element)\), \((point,line)\). If the right pairs are chosen, the problem often becomes short.

Basic Facts

• If the same finite set is counted in two ways, the answers are equal.
• The sum of degrees of a graph equals \(2E\), because every edge has two ends.
• If \(T\) objects are distributed among \(m\) boxes, some box contains at least the average \(T/m\).
• The number of pairs \((S,x)\), where \(x\) belongs to subset \(S\), can be counted by \(S\) or by \(x\).
• Double counting often turns “prove existence” into a statement about an average.

When to Use This Method

• The problem contains relations between objects: a student attends a club, a point lies on a line, a vertex is incident to an edge.
• You need to prove a combinatorial identity.
• There is a table, rows and columns, and entries can be counted in two ways.
• You need to prove existence of an object with high or low load.

How to Recognise the Method

Look for phrases such as “each object is connected to”, “in every group”, “each pair”, “total number of memberships”, or “average number”. They almost always suggest a set of pairs or incidences.

If you see a sum like \(0C(n,0)+1C(n,1)+\cdots+nC(n,n)\), try counting pairs “chosen subset and marked element inside it”.

Typical Mistakes

• Counting two different sets of objects instead of one set in two ways.
• Forgetting that each graph edge has two ends.
• Using an average but not stating the conclusion “there exists at least the average”.
• Confusing ordered pairs and unordered pairs.
• In identity problems, not explaining what is being counted.

Mini-Checklist

• What set of objects are we counting?
• Can each object be described as a pair \((a,b)\)?
• What happens if we count by the first component?
• What happens if we count by the second component?
• Do we need equality or only an estimate?
• How does the average imply existence?

Key Idea

The pigeonhole principle says: if there are more objects than boxes, then some box contains at least two objects. The strengthened form says: if \(N\) objects are distributed among \(k\) boxes, some box contains at least \(\lceil N/k ceil\) objects.

The olympiad part is choosing the right “boxes”. They may be months, residues, sums, intervals, colors, odd parts of numbers, small regions in a geometric partition, or pairs of parameters.

Basic Facts

• If \(k+1\) objects lie in \(k\) boxes, two objects lie in the same box.
• If \(N\) objects lie in \(k\) boxes, some box contains at least \(\lceil N/k ceil\) objects.
• Residues modulo \(n\) give \(n\) boxes.
• For problems where a sum must be divisible by \(n\), partial sums are often useful.
• In geometry, the boxes are often small regions into which a large figure is partitioned.

When to Use This Method

• You need to prove that among many objects, two share a property.
• There are residues, months, colors, intervals, parity classes, or other finite categories.
• You need to prove existence of a pair with small distance or a special sum.
• The statement says “for every choice of sufficiently many objects”.

How to Recognise the Method

Ask: which property can take only a small number of values? If there are more objects than possible values, two objects share that value. For divisibility, boxes are often residues. For closeness, boxes are intervals or small cells.

If subset sums appear, consider partial sums or all subset sums and compare the number of sums with the number of possible values.

Typical Mistakes

• Choosing boxes without proving there are fewer boxes than objects.
• Finding two objects in the same box but not explaining why this gives the required property.
• Forgetting residue \(0\) in modular problems.
• In geometric problems, using regions with diameter too large.
• In subset-sum problems, forgetting to remove common elements from two equal-sum subsets.

Mini-Checklist

• What are the objects?
• What are the boxes?
• How many objects and how many boxes are there?
• What does it mean for two objects to be in the same box?
• Do we need the simple or strengthened form?
• If sums are used, can equal sums be turned into nonempty disjoint sets?

Key Idea

An invariant is a quantity or property that does not change under the allowed operations. If the initial and final states have different invariant values, then the transition is impossible.

In olympiad problems, the invariant is often hidden. Look among parity, sum, residue modulo a number, coloring, product of signs, number of objects of a certain color, or permutation parity.

Basic Facts

• If an operation changes a quantity by an even number, its parity is preserved.
• If an operation adds to one part and subtracts from another, the sum is often preserved.
• If an operation changes a quantity by a multiple of \(m\), the residue modulo \(m\) is preserved.
• For board colorings, track how many cells of each color a tile covers or a move changes.
• For sign changes, the product of all signs or the parity of the number of minus signs is often useful.

When to Use This Method

• You need to prove that one state cannot be obtained from another.
• There is a repeated operation changing a configuration.
• The problem contains tokens, coins, lamps, signs, board cells, or permutations.
• Direct search over moves is impossible or quickly becomes chaotic.

How to Recognise the Method

Ask: what does the operation definitely not change? If a number of objects changes, check parity. If objects are moved, check the sum. If the operation is local on a board, color the board. If signs change, check the product or number of minus signs.

Sometimes the invariant is not the quantity itself, but its residue. For example, a sum may change, but always by a multiple of \(3\), so the sum modulo \(3\) is preserved.

Typical Mistakes

• Showing a quantity does not change in some moves, but not checking all possible moves.
• Choosing a quantity that is almost preserved but breaks under one type of move.
• Proving impossibility without comparing initial and final invariant values.
• Using a board coloring without checking the colors covered by the tile.
• Forgetting that an invariant may be composite, such as “inversion parity plus number of moves”.

Mini-Checklist

• What is the initial state?
• What final state is required?
• What does one move change?
• Which quantity is preserved by every move?
• Do the initial and final invariant values differ?
• If one invariant fails, should we try a modulus, coloring, or product?

Key Idea

A coloring turns a board picture into a counting problem. If every tile covers colors in a fixed ratio, then the whole tiled region must have the same ratio.

The main skill is to choose a useful coloring, not a pretty one. Dominoes often need the usual chessboard coloring. Straight trominoes and tetrominoes are handled by diagonal colorings modulo \(3\) and \(4\). For knight moves, remember that a knight changes square color at every move.

Basic Facts

• A \(1\times2\) domino on a chessboard covers one black and one white cell.
• A straight \(1\times3\) tromino, under the coloring of cell \((i,j)\) by \(i+j\pmod3\), covers one cell of each of the three colors.
• A straight \(1\times4\) tetromino, under the coloring of cell \((i,j)\) by \(i+j\pmod4\), covers one cell of each of the four colors.
• With vertical stripe coloring, a horizontal domino covers two colors, while a vertical domino covers two cells of one color.
• A knight move changes the color of the square in the usual chessboard coloring.

When to Use This Method

• You need to prove that a board cannot be tiled by given pieces.
• The area divisibility check passes, but the tiling still looks impossible.
• Special cells are removed: corners, a diagonal, the center, or cells of one color.
• There is a condition on the number of vertical or horizontal pieces.
• A piece moves on a board, and its possible position after a given number of moves matters.

How to Recognise the Method

First check area. If area gives no contradiction, try chessboard coloring. If the pieces are long, use coloring modulo their length. If directions matter, color rows or columns in stripes.

A good test is to count how many cells of each color one tile covers. If this number is fixed for every tile, the whole region must have the same color ratio.

Typical Mistakes

• Stopping after the area check and not checking a coloring.
• Using chessboard coloring when a modulo \(3\) or modulo \(4\) coloring is needed.
• Forgetting that a piece may be rotated.
• Counting colors on the full board but forgetting to subtract removed cells.
• Proving a necessary condition and accidentally treating it as sufficient.

Mini-Checklist

• What is the area of the region and of one tile?
• What does one tile cover in chessboard coloring?
• If the tile has length \(3\) or \(4\), what does \(i+j\pmod3\) or \(i+j\pmod4\) give?
• What colors are the removed cells?
• Do the required color counts match?
• If the problem is about a moving piece, how does color change after one move?

Key Idea

In complete-information games, we usually look not for one lucky move, but for classes of positions: winning positions, from which there is a move to a losing position, and losing positions, from which every legal move goes to a winning position.

At the first level, four tools are enough: residues in stone games, symmetry strategy, pairing strategy, and backward analysis from the end of the game.

Basic Facts

• If a position has a move to a losing position, then it is winning.
• If every legal move goes to a winning position, then it is losing.
• In the game “take from \(1\) to \(k\) stones, last move wins”, the losing positions are multiples of \(k+1\).
• In the game “add from \(1\) to \(k\), whoever reaches the target wins”, one often keeps totals separated by \(k+1\).
• Symmetry works when after the opponent’s move, the reflected move is always legal.

When to Use This Method

• You need to determine who wins with perfect play.
• The game repeats similar moves with piles, numbers, or board cells.
• There are natural pairs of objects: numbers with a fixed sum, symmetric cells, or equal piles.
• The end of the game is clear, but the beginning looks complicated. Then analyze backward from losing terminal positions.

How to Recognise the Method

If the game has one pile, check residues. If two players choose objects from a symmetric set, look for a pairing strategy. If a board has a center or an axis of symmetry, try a mirror response. If the rules are unusual, list the last few positions and label them winning or losing.

Typical Mistakes

• Showing a good first move without explaining how to respond later.
• Calling a position losing without checking all legal moves from it.
• Using symmetry without proving that the reflected move is unoccupied and legal.
• Confusing the normal game with the variant where taking the last stone loses.
• In target-number games, forgetting to check the first move and the final target.

Mini-Checklist

• What are the terminal positions?
• Who wins or loses in a terminal position?
• Can positions be classified by residues?
• Is there a symmetry or pairing that can be maintained?
• After any opponent move, is there a predetermined response?
• Is the strategy proven until the end, not only for the first move?

Key Idea

A graph replaces relations between objects by vertices and edges. People and acquaintances, cities and roads, teams and games, cells and legal moves often become the same kind of structure.

The first main graph tool is the degree-sum formula: every edge has two ends, so \(\sum \deg(v)=2E\). From this simple formula come the parity of odd degrees, average arguments, and many impossibility proofs.

Basic Facts

• The degree of a vertex is the number of edges incident to it.
• In every finite undirected graph, \(\sum \deg(v)=2E\).
• The number of vertices of odd degree is always even.
• The complete graph on \(n\) vertices has \(\binom{n}{2}\) edges.
• A connected graph on \(n\) vertices has at least \(n-1\) edges; a tree has exactly \(n-1\) edges.
• A bipartite graph has no odd cycle.

When to Use This Method

• The problem contains pairs of objects: acquaintances, roads, games played, or possible transitions.
• You need to prove that a system of relations is impossible.
• Degrees or numbers of connections are given, and you need to find edges or a contradiction.
• You need to prove the existence of a vertex with large or small degree.
• There is a restriction on triangles, cycles, or connections inside two groups.

How to Recognise the Method

Ask: what are the vertices, and what are the edges? If the relation is mutual, use an undirected graph. If the relation is directed, it may be a tournament or directed graph, but often it is enough to count in-degrees and out-degrees.

If the statement contains words like “each”, “exactly”, “at least”, “is acquainted with”, or “is connected to”, it is almost always useful to write down degrees and use the degree-sum formula.

Typical Mistakes

• Counting each edge once in the degree sum, although it contributes \(2\).
• Confusing the number of edges of a complete graph with \(n^2\) instead of \(\binom{n}{2}\).
• Proving connectedness without excluding several components.
• Using tree properties for graphs that may contain cycles.
• In acquaintance problems, forgetting that acquaintance is usually mutual.

Mini-Checklist

• What are the vertices?
• What are the edges?
• Which degrees are known or bounded?
• What does \(\sum \deg(v)=2E\) give?
• Do we need connectedness, a tree, a cycle, or bipartiteness?
• Can we use an average argument: some vertex has degree at least or at most the average?

Key Idea

Recursion appears when an object can be built from a smaller object by its last step. Instead of counting the large case at once, define \(a_n\) as the number of ways for size \(n\), then express \(a_n\) through previous values.

In olympiad problems, the point is not to guess a sequence, but to justify the split: by the last step, last tile, last symbol, last column, or last point of a path.

Basic Facts

• If the last step has length \(1\) or \(2\), the recurrence \(a_n=a_{n-1}+a_{n-2}\) often appears.
• Tilings of a \(2\times n\) strip by dominoes give the same Fibonacci recurrence.
• Binary strings with no adjacent ones are naturally split by the last symbol.
• Grid paths satisfy \(P(i,j)=P(i-1,j)+P(i,j-1)\), or can be counted by \(\binom{m+n}{m}\).
• If one state is not enough, introduce extra states, such as “a board with one missing corner on the right”.

When to Use This Method

• You need to count ways for a long string, strip, staircase, or path.
• An object of size \(n\) naturally ends in one of several types of last steps.
• Small cases are easy to list, and the general case resembles previous ones.
• Direct enumeration grows quickly, but the structure repeats.

How to Recognise the Method

Ask: what can the last step look like? If that last step is removed, what remains? If it is the same kind of problem, one recurrence may be enough. If several “almost the same” problems remain, use several states.

For strings, look at the last symbol or last two symbols. For tilings, look at the last column. For paths, look at where the path came from before the final point.

Typical Mistakes

• Writing a recurrence without initial conditions.
• Counting objects twice because the last-step cases overlap.
• Not checking small values \(n=0\), \(n=1\), although the recurrence needs them.
• Using a Fibonacci recurrence when there is a third type of last step.
• In path problems, confusing the number of steps with the number of grid points.

Mini-Checklist

• What does \(a_n\) mean?
• Which initial values are needed?
• By which final element do we split cases?
• Are the cases disjoint?
• Are all possibilities included?
• Do we need a second state?

Key Idea

In mixed problems, the method is not written in the statement. The student must recognize the structure: what should be counted, where cases are needed, where the boxes are, what is invariant, which coloring to choose, and whether the problem is a game, graph, or recurrence.

The main habit is to ask before computing: “what kind of object repeats here?” Repeated choices suggest counting. More objects than types suggests pigeonhole. Operations suggest invariants. Boards suggest coloring. Relations suggest graphs. Growing size suggests recursion.

Basic Facts

• The method is chosen by structure, not by keywords.
• First look for a simple invariant or simple count; a difficult method is not always needed.
• For existence, check averages, pigeonhole, or graph degrees.
• For impossibility, check parity, residues, coloring, or a sum.
• For counting a family of size \(n\), look for the last step and a recurrence.

When to Use This Method

• After several topics have been studied, when the statement no longer names the technique.
• Before a mock olympiad, where problems appear in arbitrary order.
• When the obvious first approach creates many chaotic cases.

How to Recognise the Method

Run a quick diagnosis: are we counting, proving existence, proving impossibility, or building a strategy? Is there a repeated operation? Is there a board? Is there a relation between pairs of objects? Can the last element be removed to get a smaller problem of the same kind?

If two methods seem possible, start with the coarser one: parity, residues, sum, or average. Often it immediately explains why the problem has its shape.

Typical Mistakes

• Recognizing a familiar topic and applying it mechanically without checking the conditions.
• Trying to count directly when a coloring or invariant is needed.
• In existence problems, forgetting to define the boxes or the average.
• In games, giving a first move but not the continuing strategy.
• In recurrences, not proving that the last-step cases are disjoint.

Mini-Checklist

• What is required: find a number, prove existence, prove impossibility, or build a strategy?
• Which objects repeat?
• Are there natural boxes, colors, degrees, or residues?
• Can the problem be reduced to a smaller size?
• Have edge cases been checked?
• Does the solution explain the choice of method?

Key Idea

A mock olympiad tests not one method, but method choice under time pressure. One set may contain counting, pigeonhole, invariants, games, graphs, and recurrences side by side.

The goal of this module is to train students to read a statement quickly, choose the first reasonable tool, and finish with a rigorous proof.

Basic Facts

• Problem 1 in a mini-set usually checks careful counting or a simple construction.
• Problem 2 often needs pigeonhole, coloring, or complement counting.
• Problem 3 trains invariants, games, or recurrences.
• Problem 4 requires combining ideas: graph, average, cycle, partial sums, or a strong coloring.

When to Use This Method

• When students have studied the basic methods and must solve without topic labels.
• Before a school, municipal, or internal selection round.
• When diagnosing gaps in counting, proof, strategy, or careful condition checking.

How to Recognise the Method

Start by classifying the goal: count, prove existence, prove impossibility, or find a strategy. Then identify the object: numbers, board, graph, sequence, or game. Finally choose the simplest tool that can plausibly work.

Typical Mistakes

• Spending too much time on brute force when an invariant is present.
• Giving an answer to a counting problem without explaining the cases.
• In existence problems, not naming pigeonhole, average, or a concrete construction.
• In graphs, forgetting that the degree sum is twice the number of edges.
• In games, not describing responses to all opponent moves.

Mini-Checklist

• What exactly must be proved or found?
• Which method looks cheapest?
• Is there a quick test: parity, residue, color, average?
• Can the solution be written in 5-8 lines?
• Are edge cases and the final conclusion checked?