Section 30.2

Pigeonhole and Extremal Principles

Guarantees via pigeonhole, maximal products of partitions, largest coprime subsets, the taxman game.

Toolkit

These problems extract a guarantee or an extremum from a finite structure by either (a) counting: pigeonhole forces a collision once the number of objects exceeds the number of “slots”, or (b) optimising: a local-exchange argument shows any non-extremal configuration can be improved, pinning down the extremal shape, then an explicit construction matches the bound.

Key tools:

Pigeonhole: $n$ objects into $m$ classes force a class of size $\lceil n/m\rceil$ ; to guarantee a target you need $n > m(t-1)$ .
Double counting / degree-sum identities bound configurations (e.g. pairs, aims, rows) via $\sum = \binom{n}{2}$ or similar.
Exchange argument for products: splitting a part $k\ge5$ into $k-2$ and $2$ (or similar) strictly increases the product; optimal partitions use only parts $2,3$ , with $4=2+2$ reducible, so maximise the count of $3$ s.
Extremal set constructions: build the tightest configuration meeting a necessary bound (cyclic shadings, cyclic aiming patterns, greedy denomination choices) to show the pigeonhole bound is sharp.
For adversarial/alternating games, bound one player’s total by noting each move concedes at least one unit to the opponent, then exhibit a strategy achieving equality.

Problems