Day 45 — Pigeonhole principle

Day 45 — Pigeonhole principle

Stage IV · concept day
Goal: State and apply the basic and generalized pigeonhole principles; use Dirichlet’s form; prove collision, birthday-bound, and modular consequences; know Erdős–Szekeres as a statement; connect to hashing and resource contention.

Why this matters

If more keys than slots, collisions must exist—not “might if unlucky.” Pigeonhole is the finite counting engine behind hash collisions, compression limits, duplicate detection, and many existence proofs without construction. It is elementary and extremely reusable.

Theory

Basic pigeonhole principle (PHP)

If \(n+1\) pigeons are placed into \(n\) holes, then at least one hole contains at least two pigeons.

Set form. Any function \(f: A\to B\) with \(A,B\) finite and \(|A| > |B|\) is not injective: \(\exists a_1\neq a_2\) with \(f(a_1)=f(a_2)\).

Generalized PHP

If \(n\) pigeons go into \(k\) holes, then some hole has at least \(\bigl\lceil n/k \bigr\rceil\) pigeons.

Proof. If every hole had at most \(\lceil n/k\rceil - 1\) pigeons, total
\[\le k\bigl(\lceil n/k\rceil - 1\bigr) < n\]
(standard ceiling argument). Contradiction. \(\square\)

Contrapositive / dual

If each hole has at most \(m\) pigeons, then number of pigeons \(\le k m\).
If you need to avoid \(m+1\) in one hole, you can place at most \(k m\) pigeons.

Dirichlet’s principle

Often the same as PHP; historically used for approximation: among \(N+1\) reals, two are close, etc.
Dirichlet approximation awareness: for real \(\alpha\) and integer \(Q\), exist integers \(p,q\) with \(1\le q\le Q\) and \(|q\alpha - p| \le 1/Q\).

Proof pattern

1. Identify pigeons (objects).
   
2. Identify holes (classes / buckets / residues / pigeonholes).
   
3. Apply \(|A|>|B|\) or generalized count.
   
4. Conclude existence of a crowded hole—translate back to the claim.

Applications catalog

Domain	Pigeons	Holes	Conclusion
Hashing	keys inserted	buckets	collision if more keys than buckets
Birthdays	people	\(365\) days	\(\ge 2\) share if \(366\) people
Hair	people in city	hair counts \(0..M\)	two same count if people \(> M+1\)
Friends	people at party	friend-count \(0..n-1\)	careful: \(0\) and \(n-1\) exclusive
Sequences	…	…	mono subsequence (Erdős–Szekeres)
Modular	\(n+1\) integers	residues mod \(n\)	two congruent mod \(n\)
Socks	socks drawn	colors	guarantee a pair

Birthday bound (collision probability lite)

PHP is worst-case guarantee (\(366\) people).
Probabilistic birthday: among \(k\) random people, \(P(\text{collision})\approx 1 - e^{-k(k-1)/(2\cdot 365)}\).
\(k \approx \sqrt{2\cdot 365\ln 2}\approx 23\) for \(\sim 50\%\) chance.
Hashing: collisions likely when \(k \sim \sqrt{n}\) for \(n\) buckets—not only at \(k=n+1\).
Today: know the bound/statement; deep probability Stage VIII.

Erdős–Szekeres (statement)

Any sequence of more than \((a-1)(b-1)\) distinct numbers has either an increasing subsequence of length \(a\) or a decreasing subsequence of length \(b\).
Proof idea (awareness): map each position to (length of longest inc ending here, longest dec ending here); pigeons into \((a-1)\times(b-1)\) grid if both bounds violated—injection.
Apply PHP on pairs.

Modular pigeon

Among \(n+1\) integers, two have difference divisible by \(n\) (same residue mod \(n\)).
Among any \(n\) integers, either one divisible by \(n\) or two with difference divisible by \(n\)—related.

Non-constructive existence

PHP proves existence of a collision/class without naming which hole—typical non-constructive pattern (Day 30).

Worked examples

Example 1 — Classic

\(367\) people: two share a birthday (ignore leap for \(365\), or use \(366\) holes).

Example 2 — Generalized

\(100\) pigeons, \(9\) holes: some hole \(\ge \lceil 100/9\rceil = 12\).

Example 3 — Hash

\(17\) keys, \(16\) buckets: collision exists.

Example 4 — Socks

\(3\) colors; to guarantee a pair, draw \(4\) (worst \(3\) different +1).

Example 5 — Mod \(n\)

\(11\) integers: two congruent mod \(10\).

Example 6 — Difference

Those two differ by multiple of \(10\).

Example 7 — Hair

If hair count \(\le 200000\), then in a city of \(200001\) people without bald edge cases… two same number.

Example 8 — Friends graph

At a party of \(n\ge 2\) people, two have the same number of friends at the party (graph degree PHP with care that degrees in \(\{0,\ldots,n-1\}\) cannot use both \(0\) and \(n-1\)).

Example 9 — Compression

More than \(2^n\) files of length \(>n\) mapping into \(n\)-bit hashes: collision (actually any map from larger set). Lossless maps cannot shrink all strings (Day 41).

Example 10 — Sequence

Among \(5\) numbers, either increasing subseq of length \(3\) or decreasing of length \(3\) (ES with \(a=b=3\), \((2)(2)=4\), need \(5\)).

Example 11 — Hands

\(13\) people, \(12\) months: two same birth month. Generalized: \(25\) people ⇒ some month has \(\ge 3\) (\(\lceil 25/12\rceil=3\)).

Example 12 — Functions

\(f:\{1,\ldots,m\}\to\{1,\ldots,n\}\), \(m>n\): not injective.

Example 13 — Subset sums (classic)

Among \(n+1\) subsets? Different: any \(n+1\) integers from \(\{1,\ldots,2n\}\) includes two with one dividing the other—or standard subset-sum PHP on prefixes mod \(n\).
Prefix sums \(s_k = a_1+\cdots+a_k\); if some \(s_k\equiv 0\pmod n\) done; else \(n\) prefixes into \(n-1\) nonzero residues ⇒ two equal mod \(n\) ⇒ difference (subarray) \(0\bmod n\).

Example 14 — Birthday probability order

\(k=23\) vs PHP \(k=366\): different questions (likely vs certain).

Exercises

1. State basic and generalized PHP.
   
2. Prove generalized PHP by contradiction.
   
3. Show among any \(11\) integers two have same last digit.
   
4. How many socks to guarantee \(3\) of the same color among \(4\) colors?
   
5. \(50\) students, grades \(0..100\): two same grade?
   
6. Minimum students to guarantee some grade earned by \(\ge 3\)?
   
7. Hash table size \(1024\); how many keys force a collision?
   
8. Explain birthday paradox vs PHP in two sentences.
   
9. Prove: among any \(n+1\) integers two differ by multiple of \(n\).
   
10. Prefix sum argument: any sequence of \(n\) integers has nonempty consecutive subseq sum divisible by \(n\) (Example 13).
    
11. Party of \(6\) people: show two have same number of friends at party (degrees).
    
12. ES: verify that \(5\) distinct reals have mono subseq of length \(3\). Find a sequence of \(4\) without inc or dec length \(3\).
    
13. Prove no injective \(f:\{0,1\}^8 \to \{0,1\}^7\).
    
14. City of \(1\) million; max hair \(200\)k—conclude.
    
15. Generalized: \(n\) holes, want some hole \(\ge r\); how many pigeons needed?
    
16. If \(9\) holes each \(\le 5\) pigeons, max pigeons?
    
17. CS: why are hash collisions inevitable at large load without perfect hashing?
    
18. Cards: how many to guarantee \(2\) aces? (Not pure PHP—hypergeometric; skip or pure: guarantee \(2\) of same suit from \(4\) suits.)
    
19. Guarantee \(5\) of one suit: compute.
    
20. Show any set of \(5\) points in a unit square has two at distance \(\le \sqrt{2}/2\) (divide into \(4\) squares)—classic geometry PHP.
    
21. Dirichlet approx: state the theorem.
    
22. Prove: among any \(6\) people, \(3\) mutual friends or \(3\) mutual strangers is Ramsey \(R(3,3)=6\)—harder; state only if curious.
    
23. Infinite PHP awareness: infinite pigeons finite holes ⇒ some hole infinite.
    
24. Constructive vs not: PHP finds existence of collision—does it give an algorithm to find it? (Scan.)
    
25. Design a PHP proof for: any graph with more edges than… invent a simple claim.

CS connection

• Hash tables: load factor; birthday-bound collisions.
  
• Checksums: small digest ⇒ collisions exist among enough messages.
  
• Load balancing: \(n\) tasks \(k\) servers—some server \(\ge\lceil n/k\rceil\).
  
• Time/space: pigeon on states in cycles (Floyd cycle—related).
  
• Compression: cannot map more messages injectively into fewer bits.
  
• Resource pools: more requests than workers ⇒ queueing.

Common pitfalls

Pitfall	What to do instead
Using birthday \(23\) as certainty	Certainty needs \(n+1\)
Wrong hole count	Define holes precisely
Degrees \(0\) and \(n-1\) both	Graph handshaking subtlety
Ceiling arithmetic slips	Check small numbers
Claiming construction	PHP is existence
Infinite sets without care	Use infinite PHP variant carefully

Checkpoint

• Basic + generalized PHP
  
• Prove one modular consequence
  
• Hash collision necessity
  
• Birthday: certainty vs likelihood
  
• ES statement
  
• Prefix sums divisible by \(n\)
  
• Exercises done or logged

Two takeaways:

1. …
   
2. …

Deep dive — quantitative PHP forms

Form A. \(n\) pigeons, \(k\) holes ⇒ some hole \(\ge \lceil n/k\rceil\).

Form B. To ensure some hole \(\ge r\), need \(n \ge k(r-1)+1\) pigeons.

Form C (infinite). Infinitely many pigeons, finitely many holes ⇒ some hole infinite.

Probabilistic vs adversarial

Question	Tool
Must collision exist?	PHP
Is collision likely?	Birthday / probability
Expected max load	Balls and bins (later)

Erdős–Szekeres proof sketch (more detail)

Assign to each index \(i\) the pair \((a_i,b_i)\) = (longest increasing subseq ending at \(i\), longest decreasing ending at \(i\)). If no inc of length \(a\) and no dec of length \(b\), then \(a_i\le a-1\), \(b_i\le b-1\). Pairs lie in a grid of size \((a-1)(b-1)\). If sequence longer, two indices share a pair—leads to contradiction with maximality of \(a_i\) or \(b_i\) when comparing values. (Fill details from a textbook if desired.)

Subarray sum divisible by \(n\) (full write-up)

Let \(s_0=0\), \(s_k=a_1+\cdots+a_k\) for \(k=1..n\). Consider \(s_0,\ldots,s_n\) — \(n+1\) prefix sums. Their residues mod \(n\) lie in \(\{0,\ldots,n-1\}\) (\(n\) holes). Two prefixes \(s_i,s_j\) (\(i<j\)) share a residue ⇒ \(s_j-s_i\equiv 0\pmod n\) ⇒ \(a_{i+1}+\cdots+a_j\) divisible by \(n\). If some \(s_k\equiv 0\), the prefix itself works. \(\square\)

More worked examples

Example 15 — Form B
\(k=5\) holes, want \(\ge 4\) in some hole: need \(5\cdot 3+1=16\) pigeons.

Example 16 — Months
\(40\) people: some month has \(\ge \lceil 40/12\rceil=4\) birthdays.

Example 17 — Bits
Any \(9\) distinct numbers in \(\{1,\ldots,16\}\): two differ by at most … (pigeon on gaps—variant).

Example 18 — Graph
Simple graph on \(n\) verts max edges without … (Turán later); PHP on degrees for same-degree pair.

Additional exercises

26. Prove Form B from Form A.
    
27. Minimum people so that \(4\) share a birth week (52 weeks).
    
28. Show any sequence of \(n^2+1\) distinct reals has mono subseq length \(n+1\) (ES special case \(a=b=n+1\)).
    
29. Hash: \(m\) buckets, \(m+1\) keys—prove collision and describe an algorithm to find one.
    
30. Infinite PHP: among infinitely many naturals, infinitely many share a residue mod \(10\).

Extended practice workshop

Numerical PHP

1. \(100\) pigeons \(7\) holes—min max load.
   
2. To force \(\ge 5\) in some of \(6\) holes—how many pigeons?
   
3. \(n\) buckets, force collision—how many keys?
   
4. Socks: \(k\) colors, force \(r\) of one color.
   
5. Months: force \(3\) in some month—min people.

Modular / number

6. Among \(n+1\) ints, two congruent mod \(n\).
   
7. Subarray sum divisible by \(n\)—full proof rewrite.
   
8. Two of \(11\) ints differ by multiple of \(10\).

Sequences / ES

9. State Erdős–Szekeres.
   
10. Sequence of \(5\) distinct reals has mono subseq length \(3\).
    
11. Find sequence of \(4\) without inc/dec length \(3\).

CS

12. Hash collision necessity at load \(>1\).
    
13. Birthday \(\sim\sqrt{n}\) vs PHP \(n+1\).
    
14. Compression impossibility via injection.
    
15. Load balance max load lower bound \(\lceil n/k\rceil\).

Proof discipline

16. Identify pigeons and holes in a claim you invent.
    
17. Is your PHP proof constructive? How to find the crowded hole?
    
18. Infinite PHP: infinitely many naturals with same last digit—prove.

Mixed

19. Same degree pair at a party of \(n\ge 2\) (with \(0\)/\(n-1\) care).
    
20. Geometry PHP: \(5\) points in unit square—two within \(\sqrt{2}/2\).

PHP pocket card

Ensure	Need
some hole \(\ge 2\)	\(k+1\) pigeons for \(k\) holes
some hole \(\ge r\)	\(k(r-1)+1\) pigeons
likely collision	\(\sim\sqrt{\pi n/2}\) (birthday; probabilistic)

Synthesis

The pigeonhole principle is a forced collision theorem: maps from a larger finite set to a smaller one cannot be injective. Generalized form controls how crowded the busiest hole is (\(\lceil n/k\rceil\)). Number theory, hashing, and extremal combinatorics (Erdős–Szekeres) all reuse the same pattern: name pigeons, name holes, compute the threshold.

Forms to recite

1. Basic. \(n+1\) pigeons, \(n\) holes ⇒ some hole has \(\ge 2\).
   
2. Generalized. \(n\) pigeons, \(k\) holes ⇒ some hole has \(\ge \lceil n/k\rceil\).
   
3. To force \(\ge r\) in some hole: need \(k(r-1)+1\) pigeons.
   
4. Functional. \(|A|>|B|\) finite ⇒ no injection \(A\to B\).
   
5. Infinite awareness. Infinitely many pigeons, finitely many holes ⇒ some hole infinite.

More worked examples

Example — Residues.
Among \(n+1\) integers, two are congruent mod \(n\): holes = residues \(0,\ldots,n-1\).

Example — Subarray sum divisible by \(n\).
Prefix sums \(s_0=0,s_1,\ldots,s_n\) give \(n+1\) values mod \(n\) ⇒ two equal mod \(n\) ⇒ difference (subarray sum) \(\equiv 0\pmod n\).

Example — Socks.
\(k\) colors, want \(r\) of one color: buy \(k(r-1)+1\) socks.

Example — Hashing.
\(m\) slots, \(m+1\) keys ⇒ collision. Birthday bound: \(\sim\sqrt{\pi m/2}\) keys for likely collision—probabilistic, not PHP worst-case.

Example — Erdős–Szekeres (statement).
Any sequence of more than \(ab\) distinct numbers has increasing subsequence length \(a+1\) or decreasing length \(b+1\). PHP on pair-labels \((i,d)\) of longest inc/dec ending at each position.

Extra exercises (synthesis)

31. Prove: among any \(6\) people, at least \(3\) born on the same day of the week? (Compute threshold for \(r=3\), \(k=7\)—actually need \(15\) for \(\ge 3\); so for \(6\) only \(\lceil 6/7\rceil=1\)—correct the claim and state a true PHP fact about \(6\) people.)
    
32. Force at least \(4\) of \(12\) months: how many people?
    
33. Show that any set of \(n+1\) distinct integers in \(\{1,\ldots,2n\}\) contains two with one dividing the other? (Optional harder—or prove a simpler: two differ by at most \(n\)?)
    
34. Load balance: \(n\) jobs \(k\) machines, min possible max load lower bound.
    
35. Prove infinite PHP: among \(\mathbb{N}\), infinitely many share last decimal digit.
    
36. Compression: why injective map \(\{0,1\}^n\to\{0,1\}^{n-1}\) is impossible.

Discipline checklist

Step	Question
1	What are the pigeons?
2	What are the holes?
3	How many of each?
4	Which form (basic / ceiling / force \(r\))?
5	Is the conclusion existential only? (yes—PHP)

PHP proofs often non-constructive until you scan; algorithms that find the crowded hole are separate. Gate IV will mix PHP with sets, relations, and functions—identify pigeons cleanly under time pressure.

Tomorrow

Day 46 — Gate IV. Sets, power set counts, relation properties, equivalence classes, injection/surjection, pigeonhole, one composition—Stage IV portfolio check.