Combinatorics
23 units
-
Formerly, this was a unit on using combinatorial nullstellensatz, mostly for fun. It was later expanded to additionally include uses of generating functions and related polynomial methods on 3/6 level problems, broadening the scope significantly.
-
Some selected problems revolving around the idea that a function from a set to itself can be thought of as a directed graph with all outdegrees equal to 1. In particular, iterating such a function often involves looking at its cycle decomposition.
-
A challenging combinatorics unit to conclude the year, with difficult problems reviewing everything that has appeared earlier.
-
The "ARML combo" unit, this counting unit represents the centroid of Rigid, Induct, Formulas, and Grinding. Also contains several black-magic bijections.
-
A beginner combinatorics unit, meant to help get people oriented with typical proof styles for olympiad problems. Induction, recursion, invariants, and algorithms.
-
An important unit about taking advantage of the equality case in combinatorial problems in order to solve problems. Mandatory for newcomer students.
-
Computational problems involving probability, expected value (in particular linearity of expectation), and Markov chains (processes which move from state to state). A good precursor to the Global unit.
-
A difficult unit on problems from extremal graph theory; finding graphs which maximize X under certain constructions. The most basic example is Turan's theorem, which maximizes the number of edges in a graph avoiding an r-clique. Global/local ideas as well as understanding of equality cases feature prominently. Most of the examples in this unit are more challenging.
-
Problems for which you have a lot of room to make decisions; a lot of the problems in this unit are constructions, for example. You will feel like you are inventing mathematics, rather than discovering it (in contrast to the Rigid unit).
-
Linearity of expectation, switching the order of summation, what's often called pigeonhole principle, counting in two ways, ... turns out they're actually all more or less the same idea.
-
An accelerated version of both the global and local units (both done at once).
-
Combinatorics practice with graphs. The B version of the unit is aimed at students with no previous exposure to graph theory; the harder versions assume prior experience.
-
A fun but difficult unit on combinatorics problems involving rectangular grids.
-
Problems which really use induction and recursion in a substantial way, i.e. the main idea of the problem really is about how (or whether) to induct. Features some AIME-style recursion calculations.
-
This is a duplicate of Induction I, but more difficult and with different artwork.
-
Mixed combinatorics practice at the IMO 2/5 level.
-
Algorithmic problems which involve showing that it is possible to achieve some task (rather than finding invariants or proving impossibility). Features selected problems from the IOI, so some CS background is helpful but not necessary.
-
Problems using linear algebra (rather than problems about linear algebra). Most of the problems here are combinatorial in nature as a result, and there is a mix of linear algebra over $\mathbb R$ and linear algebra over $\mathbb{F}_2$.
-
In contrast to the global unit, this unit is about problems starting from somewhere and perturbing it by a little bit. For example, in a greedy algorithm, if I want a set $S$ of size at least 100 with a certain property, I can imagine starting with $S$ empty and then grabbing things to add to $S$ while trying to avoid bad-ness (whatever that means for the current problem). It's then enough to prove I don't get stuck at any point. Most of the problems in this unit will have a similar algorithmic feeling.
-
This one's a secret. It's a bit weird, but for this unit to work I have to start by not telling you what it's about.
-
This is about staring at a moving process (e.g. windmill) and trying to understand what is going on. (The most common thing people say here is monovariants or invariants, but that's only one example of a way you can understand a process.) In a lot of ways it's like the Rigid unit, except your data is way less concrete, and in some cases unobtainable, so you'll be applying the same intuition in a more hostile environment.
-
This is one of my favorite units. It's about problems which involve taking a fixed structure, and trying to figure out as much as you can about it --- the task the problem asks you to actually prove becomes unimportant, almost like an answer extraction at the end. Rigid problems often have so few degrees of freedom that a lot of what you'll be doing is writing down a lot of concrete examples, and then trying to figure out what they have in common. You will feel like you are discovering mathematics, rather than inventing it (in contrast to the Free unit).
-
A fun unit involving combinatorics problems from Russia.