The Pigeon Hole Principle
# The Pigeon Hole Principle

The so called **pigeon hole principle** is nothing more than the obvious remark: if you have fewer pigeon holes than pigeons and you put every pigeon in a pigeon hole, then there must result at least one pigeon hole with more than one pigeon. It is surprising how useful this can be as a proof strategy.
## Example

**Theorem.** Among any N positive integers, there exists 2 whose difference is divisible by N-1.

**Proof.** Let a_{1}, a_{2}, ..., a_{N} be the numbers. For each a_{i}, let r_{i} be the remainder that results from dividing a_{i} by N - 1. (So r_{i} = a_{i} mod(N-1) and r_{i} can take on only the values 0, 1, ..., N-2.) There are N-1 possible values for each r_{i}, but there are N r_{i}'s. Thus, by the pigeon hole principle, there must be two of the r_{i}'s that are the same, r_{j} = r_{k} for some pair j and k But then, the corresponding a_{i}'s have the same remainder when divided by N-1, and so their difference a_{j} - a_{k} is evenly divisble by N-1.

q

## Example

**Theorem.** For any N positive integers, the sum of some of these integers
(perhaps one of the numbers itself) is divisible by N.
**Proof.** Consider the N numbers b_{1} = (a_{1}) mod(N), b_{2} =(a_{1} + a_{2})
mod(N), b_{3} = (a_{1}+a_{2}+a_{3}) mod(N), ..., b_{N} = (a_{1} + ... + a_{N}) mod(N). If one of these numbers is zero, then we are done. Otherwise, only the N-1 numbers 1, 2, ..., N-1 are represented in this list, and so two of them must be the same, b_{i} = b_{j} (say i < j). This would then imply that (a_{i+1} + ... + a_{j}) mod(N) = 0, proving our claim.

q

## Exercises

Prove each of the following using the pigeon hole principle.
- If a city has 10,000 different telephone lines numbered by 4-digit numbers and
more than half of the telephone lines are in the downtown, then there
are two telephone numbers in the downtown whose sum is again the number of a
downtown telephone line.
- If there are 6 people at a party, then either 3 of them knew each
other before the party or 3 of them were complete strangers before the
party.

**<==Back To **What Does "Well Defined" Mean?

Back to Proofs