Questions: Pigeonhole Principle and Its Applications

Question 1

Among any 5 points placed inside a unit square, at least two must be within distance √2/2 of each other. A student says: 'Great — I can use this result to find which specific two points are closest.' What is wrong with this reasoning?

• A. Nothing — the pigeonhole principle tells you both that a close pair must exist and which pair it is
• B. The student has the distance threshold wrong; the actual bound requires a different subdivision
• C. The pigeonhole principle proves that a close pair must exist, but says nothing about which specific pair
• D. The principle only applies when the points are placed randomly, not in any arrangement

Answer: (C)

The pigeonhole principle is an existence proof: it tells you that a certain configuration must exist, but it does not identify the specific instance. Dividing the unit square into 4 smaller squares (the 'holes') and distributing 5 points (the 'pigeons') guarantees that some sub-square contains at least 2 points — but the principle gives no information about which sub-square or which pair of points satisfies the condition. This non-constructive character is fundamental to the technique.

Question 2

A class of 100 students is assigned to birth months. According to the generalized pigeonhole principle, what is the minimum guaranteed number of students in at least one birth month?

• A. At least 8 — because 100/12 ≈ 8.3, so some month has more than 8 students
• B. At least 9 — because ⌈100/12⌉ = 9, so some month must contain at least 9 students
• C. At least 2 — the basic principle only guarantees two students share a month
• D. Exactly 9 — because 100 ÷ 12 averages to 9 students per month

Answer: (B)

The generalized pigeonhole principle states: if n items go into m containers, some container holds at least ⌈n/m⌉ items. Here n=100, m=12, so ⌈100/12⌉ = ⌈8.33...⌉ = 9. At least one birth month must contain at least 9 students. Option C gives the basic (non-generalized) version. Option D is wrong because ⌈n/m⌉ is a minimum guarantee, not an exact count — the distribution may be uneven.

Question 3

The pigeonhole principle proves that among any 13 people, at least two share a birth month — without identifying which month or which two people.

• T. True
• F. False

Answer: True

The argument runs by contradiction: if every month had at most 1 person, there could be at most 12 people — but we have 13, a contradiction. The argument establishes that a shared month must exist but says nothing about which month or who the two people are. This non-constructive character is precisely what distinguishes existence proofs from constructive algorithms.

Question 4

The pigeonhole principle is mainly useful for locating specific items — like identifying which two people in a group share a birthday.

• T. True
• F. False

Answer: False

The pigeonhole principle is an existence proof technique, not a search algorithm. It tells you that a collision (shared birthday, duplicate value, close pair of points) must exist, but provides no method for finding it. The creative challenge in applying it is identifying the right 'pigeons' and 'holes' for a given problem — once that translation is made, the principle proves existence. Locating the specific instance requires additional work outside the principle.

Question 5

What is the difference between a constructive proof and an existence proof, and how does the pigeonhole principle illustrate the distinction?

Model answer: A constructive proof exhibits the specific object claimed to exist. An existence proof establishes that something must exist without identifying it. The pigeonhole principle is an existence proof: it shows that when n items are distributed among fewer than n containers, some container must hold more than one item — but never points to which container or which items. The mathematical creativity lies in identifying what the 'pigeons' and 'holes' are in a given problem; once that translation is made, counting alone establishes existence.

Many powerful results in mathematics (Ramsey theory, the probabilistic method) are existence proofs that give no construction. The pigeonhole principle proves by contradiction: assume no container has two items; then with m containers we have at most m items, contradicting n > m. The contradiction guarantees a doubly-occupied container without ever pointing to it. Understanding this distinction — existence vs. construction — is foundational to reading and writing proofs in combinatorics.