Olympiad Combinatorics II: Colorings, Games & Graphs

Study Sheet

Olympiad Combinatorics II: Colorings, Games & Graphs

Extremal boards, matchings, no-adjacency counts, forests and cycles

Structures and Strategies

Tip
Extremal boards: bound by partition, achieve by pattern
The 27 black cells (shaded): each thick 2 × 2 block of the partition keeps exactly one white cell.

To maximize black cells on a 6×66\times6 board with no fully black 2×22\times2: partition into nine 2×22\times2 blocks, each holding at most 33 — bound 2727; achieve it by whitening every cell with both coordinates even.

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.

Tip
Matchings, gaps, and forced adjacency

Perfect matchings of 2n2n people: (2n−1)!!=(2n)!2nn!(2n - 1)!! = \tfrac{(2n)!}{2^nn!} (945945 for ten). "No two X adjacent": place the other items, then choose gaps for the X's.

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

Tip
Games: work backward from the end

A position is losing (P) iff every move leads to a winning (N) position; label backward from the terminal state. Subtraction games (take 11–33) are losing at multiples of 44; Nim is losing iff the XOR of heap sizes is 00.

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 nn: 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.

Side note
Colorings as invariants

A domino covers one black and one white cell; a 2×12\times1 tiling of a mutilated board fails because the color counts differ. Tile shapes suggest colorings with more colors (three for 1×31\times3 trominoes, diagonals for L-shapes). When a coloring argument fails, try a weighting: assign xiyjx^iy^j to cell (i,j)(i,j) and compare polynomial sums.

Side note
Where it goes wrong

A mirror strategy is a proof only if the mirrored move is always legal. In the domino game on a 2×n2\times n board, the second player wins for even nn by reflecting in the center. For odd nn the same “proof” breaks: the vertical domino in the middle column is its own reflection, so after the first player takes it, the second player has no mirror move — and in fact for n=3n = 3 the first player wins by taking it: two separate 2×12\times1 columns remain, each holding exactly one domino, so the players fill one each and the second player is the one left without a move. The symmetric move must be checked to exist AND to differ from the move just made.

Try it
Try it: a coloring impossibility

Can a 10×1010\times10 board be tiled by 1×41\times4 tiles?

Show the answer

No. Color cell (i,j)(i, j), 0≤i,j≤90 \le i, j \le 9, with (i+j) mod 4(i + j) \bmod 4. A 1imes41 imes4 tile, horizontal or vertical, covers four consecutive values of i+ji + j, so it covers exactly one cell of each color. A tiling would use 2525 tiles and therefore cover exactly 2525 cells of each color. But the board has 2626 cells of color 11, 2525 of colors 00 and 22, and 2424 of color 33 (count along the 1919 anti-diagonals i+j=ki + j = k, which have 1,2,…,10,…,2,11, 2, \ldots, 10, \ldots, 2, 1 cells). Unequal counts: no tiling.

Proofs & Why It Matters

Tip
Proof: a forest on nn vertices with cc components has n−cn - c edges

Hence any graph with at least nn edges contains a cycle.

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

Tip
Proof: Bouton's theorem for Nim

A Nim position is losing for the player to move iff the XOR of heap sizes is 00.

Two facts. (i) From a position with XOR 00, every move changes exactly one heap, hence changes the XOR to nonzero (XOR-ing a nonzero change). (ii) From XOR s≠0s \ne 0, take the highest bit of ss; some heap hh has that bit set, and h⊕s<hh \oplus s < h, so reducing that heap to h⊕sh \oplus s is a legal move making the total XOR 00. The terminal position (all zero) has XOR 00 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.

Going Deeper: Worked Problems

Example
Worked: an invariant in a token game

Tokens sit on 1,2,…,20261, 2, \ldots, 2026 on a number line. A move takes two tokens at a<ba < b and moves them to a−1a - 1 and b+1b + 1. Can all tokens end up on a single point? Prove your answer.

Step 1 — look for an invariant: the SUM of positions is preserved (a decreases by 11, bb increases by 11), and so is... the sum of SQUARES? (a−1)2+(b+1)2=a2+b2+2(b−a)+2>a2+b2(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 xx, then 2026x=∑k=2026⋅202722026x = \sum k = 2026\cdot\tfrac{2027}{2}, so x=1013.5x = 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."

Example
Worked: a strategy-stealing argument

In the game where players alternately claim unclaimed cells of an n×nn\times n board and the first to complete a full row or column wins, show the second player cannot have a winning strategy.

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

Step 2 — the first player makes an arbitrary move, then pretends to be the second player and follows SS; if SS 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 SS 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.