Questions: Introduction to the Pigeonhole Principle

Question 1

In a drawer with only black and white socks, what is the minimum number of socks you must pull out (in the dark) to guarantee a matching pair?

• A. 2
• B. 3
• C. 4
• D. 10

Answer: (B)

There are 2 colors (pigeonholes) and you need more socks than colors to guarantee a match. With 2 socks, you might get one black and one white — no match. With 3 socks, by the pigeonhole principle, at least two must be the same color. So 3 is the minimum. This works regardless of how many socks of each color are in the drawer.

Question 2

The pigeonhole principle can be used to determine exactly which two people in a group share a birthday.

• T. True
• F. False

Answer: False

The pigeonhole principle proves that a shared birthday must exist in a group of 367+ people (or likely exists in smaller groups), but it does not identify which two people share it. It is an existence proof, not a constructive one. To find the actual pair, you would need to compare birthdays individually.

Question 3

Prove that among any 6 people, at least 3 are mutual acquaintances or at least 3 are mutual strangers.

Model answer: Pick any person, say Alice. She has 5 relationships (with the other 5 people), each either 'acquainted' or 'stranger.' By pigeonhole, at least 3 of these 5 are the same type. Case 1: Alice knows at least 3 people (say Bob, Carol, Dave). If any pair among them knows each other, that pair plus Alice forms 3 mutual acquaintances. If none of them know each other, then Bob, Carol, Dave are 3 mutual strangers. Case 2 (Alice is strangers with 3) is symmetric.

This is a classic Ramsey theory result. The pigeonhole principle provides the initial split (at least 3 of the same type among Alice's 5 connections), and then a small case analysis completes the proof. The elegance comes from combining pigeonhole with proof by cases — both techniques you have already learned.