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 exist 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 divisible 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 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.
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.
ឥទ្ធិពលនៃរបៀបនិយាយ
7 years ago
