Page 422 - Discrete Mathematics and Its Applications

6.2 The Pigeonhole Principle 401

The pigeonhole principle is a useful tool in many proofs, including proofs of surprising
results, such as that given in Example 4.

EXAMPLE 4 Show that for every integer n there is a multiple of n that has only 0s and 1s in its decimal
expansion.

Solution: Let n be a positive integer. Consider the n + 1 integers 1, 11, 111,..., 11 ... 1 (where
the last integer in this list is the integer with n + 1 1s in its decimal expansion). Note that there
are n possible remainders when an integer is divided by n. Because there are n + 1 integers in
this list, by the pigeonhole principle there must be two with the same remainder when divided
by n. The larger of these integers less the smaller one is a multiple of n, which has a decimal
expansion consisting entirely of 0s and 1s. ▲

The Generalized Pigeonhole Principle

The pigeonhole principle states that there must be at least two objects in the same box when
there are more objects than boxes. However, even more can be said when the number of objects
exceeds a multiple of the number of boxes. For instance, among any set of 21 decimal digits
there must be 3 that are the same. This follows because when 21 objects are distributed into
10 boxes, one box must have more than 2 objects.

THEOREM 2 THE GENERALIZED PIGEONHOLE PRINCIPLE If N objects are placed into k
boxes, then there is at least one box containing at least N/k objects.

Proof: We will use a proof by contraposition. Suppose that none of the boxes contains more
than N/k − 1 objects. Then, the total number of objects is at most

N N
k − 1 <k + 1 − 1 = N,
k k
where the inequality N/k <(N/k) + 1 has been used. This is a contradiction because there
are a total of N objects.

A common type of problem asks for the minimum number of objects such that at least r
of these objects must be in one of k boxes when these objects are distributed among the boxes.
When we have N objects, the generalized pigeonhole principle tells us there must be at least r
objects in one of the boxes as long as N/k ≥ r. The smallest integer N with N/k > r − 1,
namely, N = k(r − 1) + 1, is the smallest integer satisfying the inequality N/k ≥ r. Could
a smaller value of N suffice? The answer is no, because if we had k(r − 1) objects, we could
put r − 1 of them in each of the k boxes and no box would have at least r objects.
When thinking about problems of this type, it is useful to consider how you can avoid having
at least r objects in one of the boxes as you add successive objects. To avoid adding a rth object
to any box, you eventually end up with r − 1 objects in each box. There is no way to add the
next object without putting an rth object in that box.
Examples 5–8 illustrate how the generalized pigeonhole principle is applied.

EXAMPLE 5 Among 100 people there are at least 100/12 = 9 who were born in the same month. ▲