Pigeonhole Principle (Residues and Parity)

The principle

Basic form. If $n+1$ objects are placed into $n$ boxes, at least one box contains $\ge 2$ objects.

Generalized (strong) form. If $N$ objects are placed into $n$ boxes, some box contains at least

$\left\lceil \frac{N}{n} \right\rceil$

objects. Equivalently, to keep every box at $\le k$ you can store at most $kn$ objects; the $(kn+1)$-th object forces a box to reach $k+1$.

How exam problems use it

Most konkur pigeonhole questions ask for the smallest $n$ so that every $n$-element subset of $\{1,\dots,m\}$ is guaranteed to contain a special configuration. The reliable recipe:

1. Color (find the boxes). Translate the arithmetic condition into a finite invariant — a residue class mod $q$ or a parity — so the condition becomes "$k$ items share a color."
2. Build the largest bad set. A subset is bad (avoids the configuration) iff it takes at most $k-1$ items from each color class. Its maximum size is $\sum_{\text{classes}} \min(\text{class size},\, k-1)$.
3. Add one. The smallest forcing value is

$\boxed{\,n = (\text{max bad size}) + 1\,}.$

At that size, pigeonhole guarantees some class has $\ge k$ items — the configuration you wanted.

Two reductions worth memorizing

Why parity: $\text{even}^2 \equiv 0$ and $\text{odd}^2 \equiv 1 \pmod 4$, so a sum of four squares mod $4$ just counts the odd terms; it is $\equiv 0$ only with $0$ or $4$ odds, i.e. all four of one parity.

Mini-example

Smallest $n$ so that every $n$-subset of $\{1,\dots,49\}$ has three numbers $x,y,z$ with $49 \mid (x-y)(y-z)(z-x)$. Since $49 = 7^2$ and the numbers are distinct, no single difference is divisible by $49$, so we need all three to share a residue mod $7$. Partition $\{1,\dots,49\}$ into the $7$ residue classes ($7$ elements each). A bad set takes $\le 2$ per class: max bad size $= 7 \times 2 = 14$. Therefore

$n = 14 + 1 = 15.$

A size-$15$ subset forces some class to hold $\lceil 15/7 \rceil = 3$ elements.

Exam trick: Never count the good configurations directly. Recolor the condition into "$k$ items of one color," maximize the bad set (at most $k-1$ per color), and answer (max bad) $+\,1$. The hard step is always step 1 — turning divisibility/sum conditions into a residue or parity coloring.