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 a1, a2, ..., aN be the numbers. For each ai, let ri be the remainder that results from dividing ai by N - 1. (So ri = ai mod(N-1) and ri can take on only the values 0, 1, ..., N-2.) There are N-1 possible values for each ri, but there are N ri's. Thus, by the pigeon hole principle, there must be two of the ri's that are the same, rj = rk for some pair j and k But then, the corresponding ai's have the same remainder when divided by N-1, and so their difference aj - ak 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 b1 = (a1) mod(N), b2 =(a1 + a2) mod(N), b3 = (a1+a2+a3) mod(N), ..., bN = (a1 + ... + aN) 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, bi = bj (say i < j). This would then imply that (ai+1 + ... + aj) mod(N) = 0, proving our claim.

q

Exercises

Prove each of the following using the pigeon hole principle.

  1. 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.

  2. 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