Next: Induction Up: Induction and Counting Previous: Induction and Counting   Contents

# The Pigeonhole Principle

Proposition 8.1.1 (The Pigeonhole Principle)   If objects are placed into boxes then some box contains more than objects.

Proof. we use a contrapositive argument. Assume no box contains more than objects. So the total number of objects is at most . Contradiction.

A few examples of its use may be helpful.

Example 8.1.2   In a sequence of at least distinct numbers there is either an increasing subsequence of length at least or a decreasing subsequence of length at least .

Solution
Let the sequence be . For each position let be the length of the longest increasing subsequence starting with . Let be the length of the longest decreasing subsequence starting with . If and then there are only at most distinct pairs . Thus we have and for some . This is impossible, for if then and if then . Hence either some or .

Example 8.1.3   In a group of 6 people any two are either friends or enemies. Then there are either 3 mutual friends or 3 mutual enemies (we do not consider the in-between casew; our world is black an white only).

Solution
Fix a person . Then has either 3 friends or 3 enemies. Assume the former. If a couple of friends of are friends of each other then we have 3 mutual friends. Otherwise, 's 3 friends are mutual enemies.
Dirichlet used the pigeonhole principle to prove that for any irrational there are infinitely many rationals satisfying .

Next: Induction Up: Induction and Counting Previous: Induction and Counting   Contents
root 2002-06-10