26-05 — Pigeonhole Principle

Phase: Combinatorics | Subject: 26-05 Prerequisites: 26-01-counting-principles.md Next subject: 26-06-inclusion-exclusion-principle.md

Learning Objectives

By the end of this subject, you will be able to:

1. State and apply the basic pigeonhole principle
2. Use the generalized pigeonhole principle: at least $\lceil n/k \rceil$ objects in some box
3. Apply the pigeonhole principle to number theory problems
4. Solve combinatorial existence problems
5. Recognize pigeonhole scenarios in geometry and graph theory

Core Content

The Basic Pigeonhole Principle

If $n$ pigeons are placed into $m$ pigeonholes and $n > m$, then at least one pigeonhole contains at least two pigeons.

In contrapositive form: If each pigeonhole contains at most one pigeon, then $n \leq m$.

Generalized Pigeonhole Principle

If $n$ pigeons are placed into $m$ pigeonholes, then at least one pigeonhole contains at least $\lceil n/m \rceil$ pigeons.

Proof by contradiction: If every hole has at most $\lceil n/m \rceil - 1$ pigeons, then total pigeons $\leq m(\lceil n/m \rceil - 1) < m(n/m) = n$, contradiction.

Example: Among 100 people, at least $\lceil 100/12 \rceil = 9$ share a birth month.

Classic Pigeonhole Applications

1. Birthday Problem (simple version) Among 367 people, at least two share a birthday (366 possible birthdays including Feb 29).

2. Handshakes at a Party In any group of $n \geq 2$ people, at least two have shaken the same number of hands. (Pigeonholes = {0, 1, ..., n-1} possible handshake counts, but 0 and n-1 can't both occur — one person shakes no hands means nobody can shake n-1 hands. So at most n-1 occupied holes for n people.)

3. Subset Sums Given $n$ integers, some nonempty subset has sum divisible by $n$. (Consider partial sums $s_0 = 0, s_1 = a_1, s_2 = a_1+a_2, \ldots, s_n = \sum a_i$. By pigeonhole principle, two of these $n+1$ sums have the same remainder modulo $n$. Their difference gives a subset sum divisible by $n$.)

Erdős–Szekeres Theorem (special case)

Any sequence of $n^2 + 1$ distinct integers contains a monotone subsequence of length $n+1$.

Example: For $n=3$, any sequence of 10 numbers has an increasing or decreasing subsequence of length 4.

Key Terms

• Pigeonhole Principle
• Generalized Pigeonhole Principle
• Existence Proof

Worked Examples

Example 1: Socks in a Drawer

A drawer has 10 red socks and 10 blue socks, loose. In the dark, how many socks must you pull to guarantee a matching pair?

Solution: Pigeonholes: colors (2). To guarantee a matching pair (2 of same color), by pigeonhole principle, pulling 3 socks guarantees two share a color. General: with $c$ colors, need $c+1$ socks.

Example 2: Points in a Triangle

5 points are placed inside an equilateral triangle of side length 1. Prove at least two points are $\leq 1/2$ apart.

Solution: Divide the triangle into 4 congruent smaller equilateral triangles of side $1/2$ (connect midpoints). By pigeonhole, 5 points in 4 regions → at least one region has 2 points. In a triangle of side $1/2$, max distance between any two points is $1/2$.

Example 3: Decimal Expansions

Prove that among any 101 integers, you can select two whose difference is divisible by 100.

Solution: Pigeonholes: remainders modulo 100 (0-99, 100 holes). With 101 integers, two have the same remainder. Their difference is divisible by 100.

Quiz

Q1: What does the concept of Pigeonhole Principle primarily refer to in this subject?

A) A visual representation of Pigeonhole Principle B) A historical anecdote about Pigeonhole Principle C) A computational error related to Pigeonhole Principle D) The definition and application of Pigeonhole Principle

Correct: D)

• If you chose A: This is incorrect. Pigeonhole Principle is defined as: the definition and application of pigeonhole principle. The other options describe different aspects that are not the primary focus.
• If you chose B: This is incorrect. Pigeonhole Principle is defined as: the definition and application of pigeonhole principle. The other options describe different aspects that are not the primary focus.
• If you chose C: This is incorrect. Pigeonhole Principle is defined as: the definition and application of pigeonhole principle. The other options describe different aspects that are not the primary focus.
• If you chose D: Pigeonhole Principle is defined as: the definition and application of pigeonhole principle. The other options describe different aspects that are not the primary focus. Correct!

Q2: Which of the following is the key formula discussed in this subject?

A) An unrelated formula from a different topic B) \lceil n/k \rceil C) A simplified version of \lceil n/k \rceil... D) The inverse operation of the formula in question

Correct: B)

• If you chose A: This is incorrect. The formula \lceil n/k \rceil is central to this subject. The other options are either simplified versions or unrelated.
• If you chose B: The formula \lceil n/k \rceil is central to this subject. The other options are either simplified versions or unrelated. Correct!
• If you chose C: This is incorrect. The formula \lceil n/k \rceil is central to this subject. The other options are either simplified versions or unrelated.
• If you chose D: This is incorrect. The formula \lceil n/k \rceil is central to this subject. The other options are either simplified versions or unrelated.

Q3: What is the primary purpose of Generalized Pigeonhole Principle?

A) It is used only in advanced research contexts B) It is used to generalized pigeonhole principle in mathematical analysis C) It replaces all other methods in this domain D) It is primarily a historical notation system

Correct: B)

• If you chose A: This is incorrect. Generalized Pigeonhole Principle serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose B: Generalized Pigeonhole Principle serves the purpose described in the correct answer. The other options misrepresent its role. Correct!
• If you chose C: This is incorrect. Generalized Pigeonhole Principle serves the purpose described in the correct answer. The other options misrepresent its role.
• If you chose D: This is incorrect. Generalized Pigeonhole Principle serves the purpose described in the correct answer. The other options misrepresent its role.

Q4: Which statement about Existence Proof is TRUE?

A) Existence Proof is a fundamental concept covered in this subject B) Existence Proof is an advanced topic beyond this subject's scope C) Existence Proof is mentioned only as a historical footnote D) Existence Proof is not related to this subject

Correct: A)

• If you chose A: Existence Proof is a fundamental concept covered in this subject. This subject covers Existence Proof as part of its core content. Correct!
• If you chose B: This is incorrect. Existence Proof is a fundamental concept covered in this subject. This subject covers Existence Proof as part of its core content.
• If you chose C: This is incorrect. Existence Proof is a fundamental concept covered in this subject. This subject covers Existence Proof as part of its core content.
• If you chose D: This is incorrect. Existence Proof is a fundamental concept covered in this subject. This subject covers Existence Proof as part of its core content.

Q5: Based on the worked examples in this subject, what is the correct result?

A) The inverse of the correct answer B) An unrelated numerical value C) Points in a Triangle D) A different result from a common mistake

Correct: C)

• If you chose A: This is incorrect. The worked examples show that the result is Points in a Triangle. The other options represent common errors.
• If you chose B: This is incorrect. The worked examples show that the result is Points in a Triangle. The other options represent common errors.
• If you chose C: The worked examples show that the result is Points in a Triangle. The other options represent common errors. Correct!
• If you chose D: This is incorrect. The worked examples show that the result is Points in a Triangle. The other options represent common errors.

Q6: How are Existence Proof and The Basic Pigeonhole Principle related?

A) Existence Proof and The Basic Pigeonhole Principle are closely related concepts B) Existence Proof is the inverse of The Basic Pigeonhole Principle C) Existence Proof and The Basic Pigeonhole Principle are completely unrelated topics D) Existence Proof is a special case of The Basic Pigeonhole Principle

Correct: A)

• If you chose A: Both Existence Proof and The Basic Pigeonhole Principle are covered in this subject as interconnected topics. Correct!
• If you chose B: This is incorrect. Both Existence Proof and The Basic Pigeonhole Principle are covered in this subject as interconnected topics.
• If you chose C: This is incorrect. Both Existence Proof and The Basic Pigeonhole Principle are covered in this subject as interconnected topics.
• If you chose D: This is incorrect. Both Existence Proof and The Basic Pigeonhole Principle are covered in this subject as interconnected topics.

Q7: What is a common pitfall when working with Classic Pigeonhole Applications?

A) Classic Pigeonhole Applications has no common misconceptions B) The main error with Classic Pigeonhole Applications is using it when it is not needed C) A common mistake is confusing Classic Pigeonhole Applications with a similar concept D) Classic Pigeonhole Applications is always computed the same way in all contexts

Correct: C)

• If you chose A: This is incorrect. Students often confuse Classic Pigeonhole Applications with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose B: This is incorrect. Students often confuse Classic Pigeonhole Applications with similar-sounding or related concepts. Pay attention to the precise definitions.
• If you chose C: Students often confuse Classic Pigeonhole Applications with similar-sounding or related concepts. Pay attention to the precise definitions. Correct!
• If you chose D: This is incorrect. Students often confuse Classic Pigeonhole Applications with similar-sounding or related concepts. Pay attention to the precise definitions.

Q8: When should you apply Erdős–Szekeres Theorem (Special Case)?

A) Avoid Erdős–Szekeres Theorem (Special Case) unless explicitly instructed B) Apply Erdős–Szekeres Theorem (Special Case) to solve problems in this subject's domain C) Use Erdős–Szekeres Theorem (Special Case) only in pure mathematics contexts D) Erdős–Szekeres Theorem (Special Case) is not practically useful

Correct: B)

• If you chose A: This is incorrect. Erdős–Szekeres Theorem (Special Case) is a practical tool used throughout this subject to solve relevant problems.
• If you chose B: Erdős–Szekeres Theorem (Special Case) is a practical tool used throughout this subject to solve relevant problems. Correct!
• If you chose C: This is incorrect. Erdős–Szekeres Theorem (Special Case) is a practical tool used throughout this subject to solve relevant problems.
• If you chose D: This is incorrect. Erdős–Szekeres Theorem (Special Case) is a practical tool used throughout this subject to solve relevant problems.

Practice Problems

1. How many people needed to guarantee at least 3 share a birth month?
   

   Click for answer

   Generalized PHP: $\lceil n/12 \rceil \geq 3 \Rightarrow n/12 > 2 \Rightarrow n > 24$, so $n \geq 25$. (Check: with 25, $\lceil 25/12 \rceil = 3$.)

2. 51 integers are chosen from {1, 2, ..., 100}. Prove two are consecutive.
   

   Click for answer

   Pair the numbers: {1,2}, {3,4}, ..., {99,100} — 50 pairs. Choosing 51 numbers → at least one pair contributes both elements.

3. In a group of 6 people, prove at least 3 are mutual friends or at least 3 are mutual strangers (Ramsey $R(3,3) = 6$).
   

   Click for answer

   Pick person A. Among the other 5, by pigeonhole, A either has $\geq 3$ friends or $\geq 3$ strangers. Analyze that triple — either all mutual or one edge creates a triangle.

4. How many cards must be drawn from a standard 52-card deck to guarantee 3 of the same suit?
   

   Click for answer

   4 suits. $\lceil n/4 \rceil \geq 3 \Rightarrow n \geq 9$. Check: with 9, worst case 2 each suit (8 cards), 9th forces 3 of one suit.

5. Among any 5 points on a unit sphere, prove two points are within $\sqrt{2}$ of each other.
   

   Click for answer

   Divide sphere into 4 hemispheres (e.g., along coordinate planes). 5 points → 2 in same hemisphere → distance $\leq \sqrt{2}$ (diameter of a hemisphere's great circle).

Summary

Key takeaways:

• Basic: $n > m$ pigeons in $m$ holes → some hole has $\geq 2$
• Generalized: $n$ in $m$ → some hole has $\geq \lceil n/m \rceil$
• The principle proves existence without constructing the object
• Common pitfall: identifying the right pigeons and holes
• Useful in number theory (remainders), geometry (subregions), and Ramsey theory

Pitfalls

• Misidentifying what should be the pigeons and what should be the holes: The pigeonhole principle's power comes from the creative assignment of objects to categories. A common failure mode is choosing the wrong assignment and concluding nothing. Example: proving two people have the same number of hairs requires assigning people (pigeons) to hair-count categories (holes). If you reverse the assignment, the principle gives a trivial or useless bound. Always ask: "What am I forcing to collide, and what am I categorizing by?"
• Applying the basic principle when the generalized form is needed: "100 people, at least 9 share a birth month" requires the generalized form $\lceil 100/12 \rceil = 9$, not the basic form. The basic form ($n > m \implies$ at least 2 in some hole) only guarantees a collision, not a specific multiplicity. Whenever the problem asks for $k$ or more objects sharing a property, use the generalized form.
• Forgetting that the pigeonhole principle proves existence but gives no construction: The principle tells you that two numbers among any 101 have the same remainder modulo 100 — but it doesn't tell you WHICH two. For algorithmic problems, an existence proof is only the first step; you often need a constructive method to find the object. Don't confuse "there must exist" with "here's how to find it."
• Missing the subtlety when pigeonhole counts appear to conflict with constraints: In the handshake problem, there are $n$ possible handshake counts ${0, 1, \ldots, n-1}$ for $n$ people — but 0 and $n-1$ cannot both occur (if someone shakes 0 hands, nobody can shake $n-1$ hands). So the effective number of holes is at most $n-1$, and the basic principle applies. Always check whether all apparent holes are actually simultaneously occupiable.
• Applying the pigeonhole principle to infinite sets without care: The principle applies to finite sets: $n$ pigeons into $m$ holes with $n > m$. For infinite sets, cardinality arguments (e.g., the reals are uncountable) don't follow from the finite pigeonhole principle. The infinite analog is that no injection exists from a larger infinite cardinality to a smaller one — a separate result in set theory.

Next Steps

Next up: 26-06-inclusion-exclusion-principle.md — handling overlapping sets and derangements.