lxix. Socks, Handshakes and Pigeonhole Puzzles

Pigeonhole principle. If $N$ objects go into $k$ boxes, some box gets at least $\lceil N/k\rceil$. The art is choosing the boxes.

Puzzle	Boxes	Answer
socks of $k$ colours in the dark: how many to be sure of a pair?	colours	$k+1$
… to be sure of $m$ socks of one colour	colours	$k(m-1)+1$
10 black and 10 white socks, sure of a black pair	worst case: all whites first	$10+2=12$
gloves: 10 pairs, sure of a matching left and right	worst case: all lefts	$11$
367 people: two share a birthday	366 days	always
among $n\ge 2$ people, two have the same number of friends at the party	degrees $\mathrm{0..}n-1$, but $0$ and $n-1$ cannot both occur	always
handshake lemma: the number of people who shook an odd number of hands is even	$\sum \mathrm{deg}=2|E|$	always
$n$ integers: a nonempty contiguous block with sum divisible by $n$	prefix sums mod $n$	always, $O(n)$
$n+1$ numbers from $\mathrm{1..2}n$: two are coprime	pairs $\{2i-1,2i\}$	two consecutive numbers
$n+1$ numbers from $\mathrm{1..2}n$: one divides another	odd parts $1,3,\dots ,2n-1$	same odd part, powers of 2 differ
5 lattice points: the midpoint of two is a lattice point	parities $(x\mathrm{mod}2,y\mathrm{mod}2)$	always
5 points in a unit square: two within $\frac{\sqrt{2}}{2}$	four $\frac{1}{2}\times \frac{1}{2}$ squares	always
any $rs+1$ distinct numbers: increasing run of $r+1$ or decreasing of $s+1$ (Erdős–Szekeres)	labels (longest increasing ending here, longest decreasing ending here)	always, tight
Dirichlet: for real $\alpha$ and $N\ge 1$, some $1\le q\le N$ has $|q\alpha -p|<\frac{1}{N}$	fractional parts of $0,\alpha ,\dots ,N\alpha$ in $N$ intervals	always
two Londoners with the same number of hairs	hair counts $\le 10^6<$ population	always
party of 6: three mutual friends or strangers	see Party Problem	Ramsey $R(3,3)=6$

pair<int, int> divisibleBlock(const vector<ll>& a) {   // [l, r) with sum divisible by n = |a|
    int n = sz(a); vector<int> seen(n, -1); seen[0] = 0; ll s = 0;
    for (int i = 0; i < n; i++) {
        s = ((s + a[i]) % n + n) % n;
        if (seen[s] >= 0) return {seen[s], i + 1};
        seen[s] = i + 1;
    }
    return {-1, -1};                                   // unreachable for n >= 1
}
 
pair<int, int> dividingPair(const vector<int>& v) {   // distinct values in 1..2n, |v| = n + 1: indices i, j with v[i] | v[j]
    int n = sz(v) - 1; vector<int> byOdd(2 * n + 1, -1);
    for (int i = 0; i <= n; i++) {
        int o = v[i]; while (o % 2 == 0) o /= 2;
        if (byOdd[o] >= 0) { int j = byOdd[o]; return v[j] < v[i] ? pair{j, i} : pair{i, j}; }
        byOdd[o] = i;
    }
    return {-1, -1};
}
 
vector<int> erdosSzekeres(const vector<int>& a, int r, int s) {   // |a| >= r s + 1 distinct values
    int n = sz(a); vector<int> inc(n, 1), dec(n, 1), pi(n, -1), pd(n, -1);
    for (int i = 0; i < n; i++) for (int j = 0; j < i; j++) {
        if (a[j] < a[i] && inc[j] + 1 > inc[i]) inc[i] = inc[j] + 1, pi[i] = j;
        if (a[j] > a[i] && dec[j] + 1 > dec[i]) dec[i] = dec[j] + 1, pd[i] = j;
    }
    for (int i = 0; i < n; i++) {
        auto build = [&](const vector<int>& par) { vector<int> idx; for (int k = i; k >= 0; k = par[k]) idx.push_back(k); reverse(all(idx)); return idx; };
        if (inc[i] > r) { auto idx = build(pi); idx.resize(r + 1); return idx; }
        if (dec[i] > s) { auto idx = build(pd); idx.resize(s + 1); return idx; }
    }
    return {};                                         // only if |a| <= r s
}
 
pair<int, int> latticeMidpoint(const vector<pair<ll, ll>>& p) {   // >= 5 points: midpoint of p[i], p[j] is integral
    int first[4] = {-1, -1, -1, -1};
    for (int i = 0; i < sz(p); i++) {
        int c = int((p[i].first & 1) * 2 + (p[i].second & 1));
        if (first[c] >= 0) return {first[c], i};
        first[c] = i;
    }
    return {-1, -1};
}

Proof: the counting puzzles

Pigeonhole. If every box had at most $\lceil N/k\rceil -1<N/k$ objects, there would be fewer than $N$. Socks: $k$ socks can all differ, $k+1$ cannot; for $m$ of a colour, $k(m-1)$ socks can have $m-1$ of each colour, one more forces $m$. Black pair / gloves: the adversary hands out all whites (all lefts) first; after that, every further pick helps, and 2 blacks (1 right) suffice.

Same number of friends. Degrees lie in $\mathrm{0..}n-1$. Someone with $n-1$ friends knows everyone, so nobody has 0; hence the $n$ degrees take at most $n-1$ values, and two coincide. Handshake lemma: each handshake adds 2 to $\sum \mathrm{deg}$, so the sum is even, and so the number of odd terms is even.

Divisible block. The $n+1$ prefix sums $P_0=0,P_1,\dots ,P_n$ take at most $n$ residues mod $n$, so $P_l\equiv P_r$ for some $l<r$, and $a_l+\cdots +a_{r-1}=P_r-P_l\equiv 0$.

$\mathrm{1..2}n$. Split $\mathrm{1..2}n$ into the $n$ pairs $\{2i-1,2i\}$: two chosen numbers share a pair, and consecutive numbers are coprime. Write each number as $2^e\cdot o$ with $o$ odd; there are only $n$ odd numbers below $2n$, so two chosen numbers share $o$, and the one with the smaller power of 2 divides the other. Both bounds are tight: $\{2,4,\dots ,2n\}$ has no coprime pair and $\{n+1,\dots ,2n\}$ no dividing pair.

Lattice midpoints and the unit square. The midpoint of $(x_1,y_1),(x_2,y_2)$ is integral iff $x_1\equiv x_2$ and $y_1\equiv y_2(\mathrm{mod}2)$; 5 points in 4 parity classes. Splitting the unit square into four squares of side $\frac{1}{2}$ puts two of 5 points in one small square, whose diameter is $\frac{\sqrt{2}}{2}$.

Erdős–Szekeres. Label position $i$ with $({\text{inc}}_i,{\text{dec}}_i)$, the longest increasing and decreasing subsequences ending at $i$. For $j<i$: if $a_j<a_i$ then ${\text{inc}}_i>{\text{inc}}_j$, otherwise ${\text{dec}}_i>{\text{dec}}_j$; so labels are distinct. If all $\text{inc}\le r$ and all $\text{dec}\le s$, there are at most $rs$ labels for $rs+1$ positions. Tight: $s$ increasing blocks of length $r$, the blocks in decreasing order. Dirichlet: the $N+1$ numbers $\{k\alpha \}$, $k=\mathrm{0..}N$, fall into the $N$ intervals $[\frac{t}{N},\frac{t+1}{N})$, so two, $\{k_1\alpha \}$ and $\{k_2\alpha \}$ with $k_1<k_2$, differ by less than $\frac{1}{N}$; then $q=k_2-k_1$ works. All four functions were checked against brute force on random inputs.

Related notes

• Invariants, Parity and Extremal Arguments
• Permutation Constructions (Erdős–Szekeres constructions)
• Party Problem
• Birthday Problem (the probabilistic version)