This cheat sheet summarizes high-value strategies for Putnam and USAMO style problems, where choosing the right idea often matters more than long computation. It helps students recognize when to use invariants, extremal choices, modular arithmetic, induction, bounding, and contradiction. These tools appear across algebra, number theory, combinatorics, and geometry, so a compact reference can guide productive first moves.
Key Facts
- For modular arithmetic, means , and congruent numbers may be added, subtracted, or multiplied modulo .
- An invariant is a quantity that stays fixed after each operation, so if , the target state is impossible.
- In a monovariant argument, a quantity such as always increases or always decreases and is bounded, which can prove termination.
- Strong induction proves by assuming is true for all and then proving .
- The extremal principle chooses a largest, smallest, nearest, or farthest object, then uses its extremal property to force a contradiction or structure.
- The AM-GM inequality states that for nonnegative , .
- The Cauchy-Schwarz inequality states that .
- A proof by contradiction assumes the negation of the desired result, derives an impossibility such as or with , then concludes the original statement.
Vocabulary
- Invariant
- An invariant is a value or property that does not change under the allowed operations in a problem.
- Monovariant
- A monovariant is a value that always moves in one direction, such as always increasing or always decreasing, during a process.
- Extremal Principle
- The extremal principle is the strategy of selecting an object with a maximum or minimum property and using that choice to prove a result.
- Modular Arithmetic
- Modular arithmetic studies remainders, using to show that and have the same remainder when divided by .
- Strong Induction
- Strong induction proves a statement for by using the truth of all earlier cases, not just the immediately previous case.
- Bounding
- Bounding proves a result by trapping a quantity between useful lower and upper estimates, often using inequalities.
Common Mistakes to Avoid
- Using examples as proof is wrong because checking several cases, such as , does not prove the statement for all .
- Forgetting to prove the base case in induction is wrong because the implication step only moves truth forward after a starting value has been established.
- Dividing by a variable expression without checking it is nonzero is wrong because expressions such as may equal and make the step invalid.
- Assuming equality in an inequality too early is wrong because inequalities such as AM-GM require conditions, and equality often occurs only when .
- Choosing an extremal object without using its extremal property is wrong because the maximum or minimum choice must create a specific restriction or contradiction.
Practice Questions
- 1 Find the remainder when is divided by .
- 2 Prove or disprove: for every integer , the number is never divisible by .
- 3 Use AM-GM to find the minimum value of for .
- 4 A game repeatedly replaces two positive integers and with and . Explain what invariant or monovariant you would look for before trying to solve the problem.
Understanding Putnam & USAMO Strategy Reference
Olympiad problems are often designed so that a direct attack creates too many cases. A useful early habit is to list what changes and what cannot change. In a game or transformation problem, record parity, remainders, total sums, number of objects, and possible distances.
In a divisibility problem, test a few small moduli before expanding expressions. In a set or graph problem, identify a smallest or largest object. These are not random tricks.
They reduce a large situation to one feature that is easier to control. A good solution usually begins by translating the story into a precise claim about integers, sets, sequences, or configurations.
Invariants are especially useful when a problem allows repeated moves. The important work is not merely checking that a quantity stays fixed. It is choosing a quantity connected to the final goal.
Colorings often create strong invariants. For example, a checkerboard coloring can track whether a move changes the balance between black and white squares. Parity tracks whether a count is even or odd.
Modular arithmetic gives a more detailed version of parity, since it separates numbers by their remainders after division. Monovariants serve a different purpose. They show that a process cannot continue forever because some whole-number measure moves in one direction but cannot pass a limit.
Be careful to prove both parts. Show the measure changes on every legal step, then show it is bounded.
Extremal arguments turn a complicated collection into one carefully chosen example. If a set of positive integers is involved, selecting the smallest member often gives strong information because nothing smaller is available. In geometry, choosing the nearest pair of points can prevent other points from lying in certain regions.
In combinatorics, selecting an object with the most or fewest connections can force a useful local pattern. The choice must matter later in the proof. Students sometimes name a largest object but never use the fact that it is largest.
After making an extremal choice, write down every consequence of that choice before moving on. This often reveals the contradiction or the construction needed for the next step.
Inequalities require attention to conditions and equality cases. Before applying an inequality, check signs, denominators, and whether the quantities are nonnegative. Equality cases are clues rather than decoration.
If equality can occur only when several variables are equal, that may tell you the likely best configuration. Induction needs similar care. The base case establishes where the argument begins, while the inductive step must clearly show how earlier cases create the next one.
Strong induction is natural when a number is broken into smaller pieces or when a recurrence uses more than one previous term. In every proof, state what is assumed, justify each transition, and finish by linking the contradiction or bound directly to the claim. Clean logic matters more than clever-looking algebra.