Pigeonhole Principle

Understand the pigeonhole principle and its applications.

The Pigeonhole Principle

If n items are put into m containers and n > m, then at least one container must contain more than one item. This simple idea has powerful applications.

Basic Form:
  If n > m objects are placed into m boxes,
  then at least one box contains ≥ 2 objects.

Example:
  In any group of 367 people, at least two share a birthday.
  (367 people > 366 possible birthdays)

Generalized Pigeonhole Principle

If n objects are placed into m boxes,
then at least one box contains ⌈n/m⌉ objects.

Example:
  In a class of 30 students, at least ⌈30/12⌉ = 3
  students share the same birth month.

Applications

1. Birthday Problem: Among 23 people, probability of shared birthday > 50%

2. Divisibility: Among any 5 integers, at least 2 have the same remainder when divided by 4.
   (Pigeons: 5 integers, Holes: 4 remainders)

3. Sums: In any set of 7 integers, there exist two whose sum or difference is divisible by 10.

4. Ramsey Theory: In any group of 6 people, there are either 3 mutual friends or 3 mutual strangers.

🧪 Quick Quiz

The pigeonhole principle states that if n items are put into m containers with n > m, then:

← Previous Permutations & Combinations

Next → Inclusion-Exclusion