Olympiad Combinatorics II: Colorings, Games & Graphs

The two halves of every extremal argument: an UPPER BOUND from a partition or a counting/pigeonhole argument, and a CONSTRUCTION that attains it. Boards and grids love partitions into small blocks; the construction is usually a periodic pattern (a lattice of white cells, a checkerboard, stripes). If the bound and the construction differ, one of them is wrong — and the gap tells you which direction to think in.

MISSISSIPPI with no two I's adjacent: arrange the seven non-I letters ($\tfrac{7!}{4!2!} = 105$), choose $4$ of the $8$ gaps ($70$): $7350$. The gap method generalizes to circular arrangements (gaps = items) and to "at least $k$ apart" (reserve $k - 1$ spacers per gap). A forest on $n$ vertices has $n - c$ edges, so $n$ edges force a cycle — the pigeonhole of graph theory.

The backward-induction table is mechanical; the SKILL is spotting the pattern (a modulus, a parity, an invariant) so it can be proved for all $n$: state the claimed set of P-positions, then show every move from a P-position lands in N and every N-position has a move into P. Symmetry strategies ("mirror the opponent") are the other standard family — valid only when the mirror move is always available, which must be argued.

Color the board with four colors by $(i + j) \bmod 4$. Every $1\times4$ tile covers one cell of each color, but the $10\times10$ board has color counts $26, 25, 25, 24$ (they are not all equal, since $100$ is divisible by $4$ but the diagonal count pattern is uneven). Unequal counts mean no tiling exists.

Each component is a tree; a tree on $k$ vertices has $k - 1$ edges (induct: a tree with $k \ge 2$ vertices has a leaf — a longest path's endpoint — and removing it leaves a tree on $k - 1$ vertices with one fewer edge). Summing over components gives $n - c$. $\blacksquare$ Significance: "$n$ edges force a cycle" is the first nontrivial fact about graphs, and it underlies spanning-tree algorithms and the rank of the cycle space.

Two facts. (i) From a position with XOR $0$, every move changes exactly one heap, hence changes the XOR to nonzero (XOR-ing a nonzero change). (ii) From XOR $s \ne 0$, take the highest bit of $s$; some heap $h$ has that bit set, and $h \oplus s < h$, so reducing that heap to $h \oplus s$ is a legal move making the total XOR $0$. The terminal position (all zero) has XOR $0$ and is a loss for the mover; induction on the total stones finishes it. $\blacksquare$ Significance: every impartial game is equivalent to a Nim heap (Sprague–Grundy) — this single proof classifies a whole genre.

Step 1 — look for an invariant: the SUM of positions is preserved (a decreases by $1$, $b$ increases by $1$), and so is... the sum of SQUARES? $(a-1)^2 + (b+1)^2 = a^2 + b^2 + 2(b - a) + 2 > a^2 + b^2$ — strictly increases (a monovariant).

Step 2 — if all tokens sat at one point $x$, then $2026x = \sum k = 2026\cdot\tfrac{2027}{2}$, so $x = 1013.5$ — not an integer position.

Step 3 — so the configuration is impossible: the conserved sum forces a non-integer center. (The monovariant separately shows the process, if unrestricted, never cycles.) Invariants answer "can it be done"; monovariants answer "must it stop."

Step 1 — suppose the second player had a winning strategy $S$.

Step 2 — the first player makes an arbitrary move, then pretends to be the second player and follows $S$; if $S$ ever asks for the cell already claimed, make another arbitrary move instead.

Step 3 — an extra claimed cell never hurts in this game (claiming can only help complete lines), so the first player wins — contradicting that $S$ was winning for the second player.

Step 4 — hence with best play the first player wins or draws. The argument is non-constructive: it proves the first player CAN'T lose without saying how to play — a classic olympiad move.