3.3 THE PIGEONHOLE PRINCIPLE 87picking the rook in the row that has at least one rook. Then go to the row with at least
two rooks. At least one of these rooks will not be in the same column as our first rook,
so select it as the second rook. Next, look at the row that has at least three rooks. One
of these three rooks lives neither in the same column as the first or the second rook.
Select this as our third rook, etc., and we are done! •
This rather elaborate problem was a good illustration of both the pigeonhole prin
ciple and the wishful thinking strategy, i.e., not giving up. When you think that a
problem can be attacked with the pigeonhole principle, first try to do the job neatly.
Look for a way to define pigeons and holes that yields a quick solution. If that doesn't
work, don't give up! Use the pigeonhole principle once to gain a foothold, then try to
use it again. Keep extracting information!
Advanced Pigeonhole
The examples here are harder problems. Some are hard because they require other
specialized mathematical ideas together with the pigeonhole principle. Other problems
require only basic pigeonhole, but the pigeons and/or holes are far from obvious.
The number theory problem below uses only basic pigeonhole, but with very clev
erly chosen pigeons.
Example 3.3.6 (Colorado Springs Mathematical Olympiad 1986) Let n be a positive
integer. Show that if you have n integers, then either one of them is a multiple of n or
a sum of several of them is a mUltiple of n.
Solution: We need to show that something is a multiple of n. How can we do this
with the pigeonhole principle? By Example 3.3.3, you already know the answer: let
the pigeonholes be the n different possible remainders one can have upon division by
n. Then if two numbers lie in the same pigeonhole, their difference will be a multiple
of n. (Why?)
But in Example 3.3.3, we had n + 1 pigeons to place into the n holes. In this
problem, we have only n numbers. How do we create n + 1 or more pigeons? And
also, how can we choose pigeons so that the thing that ends up being a multiple of n is
either one of the original numbers or a sum of several of them?
If we can answer both of these questions, we will be done. The first question is
rather mysterious, since we have so little to work with, but the second question has
a straightforward possible answer: let the pigeons be sums themselves; if we choose
them carefully, the differences of the pigeons will still be sums. How can that be done?
Let the numbers in our set be aI, a2, ... ,an. Consider the sequence
Pn at +a2 + ... +an·We are using the letter P for pigeons; i.e., Pk denotes the kth pigeon. Notice that for
any two distinct indices i < j, the difference Pj -Pi will equal the sum ai+l + ai+2 +