The vocabulary the solutions actually lean on, with a worked example and the mistake each term invites.
Bijection
A one-to-one pairing between the elements of two sets, so that every element of each set is matched with exactly one element of the other. If a bijection exists, the two sets have the same size — which lets you count a hard set by counting an easy one instead. Most clever counting arguments are a bijection in disguise.
In useThe number of subsets of an -element set equals : pair each subset with its characteristic sequence of zeros and ones, and the pairing is clearly one-to-one.
Watch out forA bijection must be both injective and surjective. Mapping each triangle to its longest side, for instance, is not a bijection because two different triangles can share a longest side.
Catalan number
The -th Catalan number is , giving for . It counts the number of ways to arrange pairs of something so that no prefix of the arrangement has more of the second kind than the first — a condition that reappears in ballot problems, bracketings and lattice paths.
In use counts the sequences of five A's and five B's in which A is never behind during the count, and equally counts the ways to fully bracket a product of six factors.
Watch out forThe offset is a frequent source of errors: , not . Check against the list before using it.
Degree of a vertex
The number of edges meeting a given vertex of a graph. In a simple graph a loop contributes nothing, and a graph drawn from real relationships often has degrees determined by the problem itself rather than chosen. Summing all degrees counts every edge twice, once at each end, which gives the handshake lemma: the degrees always add up to an even number.
In useIn the seven-bridges graph the four land-masses have degrees ; all four are odd, so no walk crosses every bridge exactly once.
Watch out forA graph can have a degree sequence that looks perfectly reasonable but is not realisable as a simple graph — for example a single vertex of degree with no other vertex of positive degree.
Frobenius number
For a set of coin denominations, the Frobenius number is the largest amount that cannot be formed exactly with them. For two denominations and that are coprime, it equals , and exactly positive amounts are unformable. With three or more denominations no closed formula is known.
In useWith -cent and -cent stamps, the Frobenius number is : every amount from upwards can be formed, and cannot. Exactly amounts fail, namely and .
Watch out forThe formula is for coprime denominations only. With -cent and -cent stamps, amounts like , and can never be formed at all, so there is no largest unformable amount.
Invariant
A quantity that does not change when the allowed operations are performed. If a candidate final state has a different value of the invariant from the initial state, no sequence of operations can reach it. Invariants turn 'is this possible?' into a comparison of two numbers.
In useColour a chessboard in the usual alternating pattern. Every domino covers one light and one dark square, so the difference (light squares covered minus dark squares covered) is always . A board with two same-coloured corners removed has a difference of , so it cannot be tiled.
Watch out forInvariants prove impossibility, never possibility. Showing two states share an invariant is not a construction — you still need an explicit sequence of moves to prove the target state is reachable.
Lattice point
A point whose coordinates are both integers, in the plane with the usual integer grid. Shapes with lattice vertices behave unusually well: their area, their boundary points and their interior points are linked by Pick's theorem, , where counts interior lattice points and counts boundary ones.
In useFor the triangle with vertices , , we have boundary points and area , so interior points.
Watch out forPick's theorem needs a simple polygon with lattice vertices. Self-intersecting polygons, polygons with holes, and polygons with non-integer vertices all break the formula.
Mathematical induction
A proof technique for statements indexed by the natural numbers. Prove the statement for the smallest value (the base case), then prove that whenever it holds for some it also holds for (the inductive step). Together these cover every value. Strong induction allows the step to assume all values below , not only .
In useThe sum of the first odd numbers is : true for since , and adding the next odd number to gives , which is exactly the claim for .
Watch out forBoth halves are required. Omitting the base case is the classic error: the statement 'all horses are the same colour' has a plausible-looking inductive step and is false from onwards.
Modular arithmetic
Working with remainders instead of whole numbers. Two integers are congruent modulo , written , when divides . Everything you normally do with numbers — adding, subtracting, multiplying — still works, because if and then and . Division is the exception: you may cancel only a factor that is coprime to the modulus.
In useTo find the last digit of , reduce modulo . Powers of cycle as with period , and , so . The last digit is .
Watch out forCancelling without checking coprimality is the classic error. From you cannot cancel the to conclude — that is false.
Monovariant
A quantity that changes in one direction only — always increases, or always decreases — under the allowed operations. Because a non-negative integer cannot decrease forever, a monovariant proves that any process must terminate. It is the standard tool for showing that a greedy procedure or a game ends.
In useIn a finite game where each move strictly reduces the total number of counters on the board, the game must end after at most as many moves as there were counters initially, since the count is a non-negative integer that drops every turn.
Watch out forThe quantity must be bounded below (or above) to be useful. A strictly decreasing sequence of real numbers, such as , never terminates, so a monovariant argument needs integer values or an explicit bound.
Parity
Whether an integer is even or odd — the value of the number modulo . Parity is the cheapest invariant available: it survives addition and multiplication in a completely predictable way, since the parity of a sum is the parity of the number of odd summands, and the parity of a product is odd only when every factor is odd.
In useThe number of people at a party who shook hands an odd number of times is always even. Summing all handshake counts double-counts every handshake, so the total is even, and an even total requires an even number of odd terms.
Watch out forParity alone often fails to distinguish cases. If two states have the same parity, parity cannot separate them, and you need a finer invariant — modulo , modulo , or a full colouring.
Pigeonhole principle
If objects are placed into boxes, at least one box holds two or more objects. The general form: if objects go into boxes, some box holds at least objects. The principle proves existence without constructing anything, which is why it is so widely useful and so unsatisfying to anyone who wants to see the object.
In useAmong any people, two were born in the same month: people into months forces a repeat. The same argument proves that in any set of integers, two differ by a multiple of .
Watch out forIt gives no information about *which* box overflows or how to find it. Recognising where to draw the box boundaries is the whole difficulty — the counting itself is trivial.
Vieta jumping
A descent technique for Diophantine equations that are quadratic in one variable. Fix the quantity you want to study, treat the equation as a quadratic in one unknown, and use the fact that the sum and product of the two roots are integers to show the second root is also an integer. Then show the second root is smaller, contradicting a minimality assumption. What survives the contradiction is the statement you wanted.
In useIf divides , the quotient is a perfect square. Setting the quotient to and viewing the relation as a quadratic in produces a smaller positive integer solution, and the descent forces . This is the solution to IMO 1988 Problem 6.
Watch out forThe descent needs a well-ordering to bottom out in. You must show the new solution is positive and strictly smaller, otherwise the argument proves nothing — a common failure is forgetting to rule out the negative root.