Pigeonhole & Extremal

If every box held at most $k$ objects there would be at most $kn$ in all — that is the proof. So everything rests on design: boxes are the classes of an equivalence relation (same residue, same odd part, same small square), and the relation must be chosen so that “same class” implies the desired property. A good test before counting: take two objects in one box and check that the conclusion really follows. If it doesn't, the boxes are wrong, however the numbers come out.

Step 1 — boxes: write each number as $2^j m$ with $m$ odd, and put it in box $m$. The odd parts are among $1, 3, \ldots, 2n - 1$: $n$ boxes.

Step 2 — $n + 1$ numbers in $n$ boxes: two share an odd part, $2^i m$ and $2^j m$ with $i < j$, and the first divides the second.

Step 3 — sharpness: $\{n + 1, n + 2, \ldots, 2n\}$ has $n$ numbers and no divisibility, since the smallest proper multiple of $k \ge n + 1$ is $2k > 2n$. $\blacksquare$ (The same bound with boxes $\{1, 2\}, \{3, 4\}, \ldots$ shows two chosen numbers are consecutive, hence coprime.)

How to find it. Divisibility inside a chain $m, 2m, 4m, \ldots$ is automatic. So partition $\{1, \ldots, 2n\}$ into $n$ such chains.

Step 1 — the objects are the $n + 1$ prefix sums $S_0 = 0, S_1 = a_1, \ldots, S_n = a_1 + \cdots + a_n$; the boxes are their residues mod $n$, of which there are $n$.

Step 2 — two prefix sums share a residue: $S_i \equiv S_j$ with $i < j$. Then $n \mid S_j - S_i = a_{i+1} + \cdots + a_j$, a nonempty block. $\blacksquare$

How to find it. Sums of consecutive terms are differences of prefix sums, and “difference divisible by $n$” is “same residue”. The empty prefix $S_0$ is what supplies the $(n+1)$-st pigeon.

Step 1 — label each term $x_i$ with the pair $(a_i, d_i)$: the length of the longest increasing, and of the longest decreasing, subsequence ending at $x_i$.

Step 2 — the labels are distinct. For $i < j$, if $x_i < x_j$ then appending $x_j$ to an increasing subsequence ending at $x_i$ gives $a_j \ge a_i + 1$; if $x_i > x_j$, likewise $d_j \ge d_i + 1$.

Step 3 — if every $a_i \le m$ and every $d_i \le n$, there are at most $mn$ possible labels for $mn + 1$ terms: two terms would share a label. So some $a_i \ge m + 1$ or some $d_i \ge n + 1$. $\blacksquare$ For $5, 8, 2, 9, 1, 6, 3, 10, 4, 7$ ($m = n = 3$) the labels are $(1,1), (2,1), (1,2), (3,1), (1,3), (2,2), (2,3), (4,1), (3,3), (4,2)$, and the label $(4, 2)$ of the last term records the increasing subsequence $1, 3, 4, 7$.

How to find it. The boxes are not given; you manufacture them as labels. When a pigeonhole argument has no visible boxes, attach to each object the data you would like to be large and show that no two objects can carry the same data.

The logic is the well-ordering principle: a nonempty set of nonnegative integers has a least element, and a finite set of reals has a least and a greatest. Choosing the extreme object gives you a free inequality — nothing is smaller — which often is exactly the missing hypothesis. The two things to check in every extremal proof are that the extreme exists (finiteness, or integer values, or compactness) and that the new object is genuinely of the same kind as the old.

Step 1 — the values are positive integers, so there is a smallest value $m$, attained at some cell $c$.

Step 2 — $m$ is the average of four numbers, each at least $m$; the average equals $m$ only if all four equal $m$. So every neighbour of $c$ also holds $m$.

Step 3 — repeating the argument at those neighbours, and so on, every cell reachable by steps between neighbours — that is, every cell — holds $m$. $\blacksquare$

How to find it. “Each value is the average of its neighbours” is a statement that fails at a strict minimum. The integer hypothesis is there to make the minimum exist.

Step 1 — there are $n!$ perfect red-blue matchings, finitely many; take one with the smallest total length.

Step 2 — suppose two of its segments $R_1B_1$ and $R_2B_2$ cross at $X$. Replace them by $R_1B_2$ and $R_2B_1$. By the triangle inequality, $R_1B_2 < R_1X + XB_2$ and $R_2B_1 < R_2X + XB_1$ (strict, since no three points are collinear), and the right sides add up to $R_1B_1 + R_2B_2$.

Step 3 — the new matching is shorter, contradicting minimality. So the minimal matching has no crossings. $\blacksquare$

How to find it. Crossing segments can always be uncrossed, but uncrossing may create new crossings elsewhere, so a step-by-step fix needs a measure that improves every time. Total length does, and the shortest matching is the fixed point.

Step 1 — let $v$ have the most wins, and suppose some $w$ is not reached in two steps: $v$ did not beat $w$, so $w$ beat $v$, and no one beaten by $v$ beat $w$, so $w$ beat everyone $v$ beat. Then $w$ beat all of $v$'s victims and $v$ as well: more wins than $v$. Contradiction.

Step 2 — for the listing, take a longest sequence $v_1, \ldots, v_k$ in which each beat the next. If some $w$ is missing: if $w$ beat $v_1$, put $w$ first; if $v_k$ beat $w$, put $w$ last. Otherwise $v_1$ beat $w$ and $w$ beat $v_k$; let $i$ be the first index with $w$ beating $v_i$ (so $i \ge 2$), then $v_{i-1}$ beat $w$, and $v_{i-1}, w, v_i$ can be inserted. Every case lengthens the sequence, contradicting maximality, so everyone is listed. $\blacksquare$

How to find it. Both claims assert that something reaches everything. Take the object that reaches the most (most wins, longest path) and show any unreached player would let you reach more.