next up previous contents
Next: Induction Up: Induction and Counting Previous: Induction and Counting   Contents

The Pigeonhole Principle

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

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

A few examples of its use may be helpful.

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

Solution
Let the sequence be $ c_1, c_2, \dots, c_{k l + 1}$. For each position let $ a_i$ be the length of the longest increasing subsequence starting with $ c_i$. Let $ d_j$ be the length of the longest decreasing subsequence starting with $ c_j$. If $ a_i \le k$ and $ d_i \le l$ then there are only at most $ k l$ distinct pairs $ (a_i,d_j)$. Thus we have $ a_r = a_s$ and $ d_r = d_s$ for some $ 1 \le r < s \le k l + 1$. This is impossible, for if $ c_r < c_s$ then $ a_r > a_s$ and if $ c_r > c_s$ then $ d_r > d_s$. Hence either some $ a_i > k$ or $ d_j > l$.

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 $ X$. Then $ X$ has either 3 friends or 3 enemies. Assume the former. If a couple of friends of $ X$ are friends of each other then we have 3 mutual friends. Otherwise, $ X$'s 3 friends are mutual enemies.
Dirichlet used the pigeonhole principle to prove that for any irrational $ \alpha$ there are infinitely many rationals $ \frac{p}{q}$ satisfying $ \lvert\alpha - \frac{p}{q}\rvert < \frac{1}{q^2}$.
next up previous contents
Next: Induction Up: Induction and Counting Previous: Induction and Counting   Contents
root 2002-06-10