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₁, a₂, ..., 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.

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₁ = (a₁) mod(N), b₂ =(a₁ + a₂) mod(N), b₃ = (a₁+a₂+a₃) mod(N), ..., b_N = (a₁ + ... + 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.

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