86 CHAPTER^3 TACTICS FOR SOLVING PROBLEMS
Intermediate Pigeonhole
Here is a more elaborate version of the pigeonhole principle, one that is used in practice
more often than the basic pigeonhole principle described above. [The notation r xl
(the ceiling of x) means the smallest integer greater than or equal to x. For example,
r 1r 1 = 4. See page 146 for more information.]If you have p pigeons and h holes. then at least one of the holes
contains at least r p / h 1 pigeons.Notice that the basic pigeonhole principle is a corollary of this statement: we have
p > h, so the quantity r p / h 1 is at least 2.
Make sure you understand the statement of this "intermediate pigeonhole princi
ple" by working through several examples. Make sure you understand why the state
ment is true.
If you are lucky, a single, beautiful application of a technique will solve your prob
lem. But generally, we are not so lucky. It is not surprising that some problems require
multiple applications of the pigeonhole principle. Each time the pigeonhole principle
is used, information is gained. Here is an example that uses repeated application of the
intermediate pigeonhole principle.Example 3.3.5 (A. Soifer, S. Slobodnik) Forty-one rooks are placed on a 10 x 10
chessboard. Prove that there must exist five rooks, none of which attack each other.
(Recall that rooks attack each piece located on its row or column.)Solution: When you see the number 41 juxtaposed with 10, you suspect that
the pigeonhole principle may be involved, since 41 is just one more than 4· 10. Once
attuned to the pigeonhole principle, we cannot help but notice that r 41/10 1 = 5, which
is encouraging, for this is the number of rooks we seek. This of course is not a solution,
but it does suggest that we probe carefully for one using the pigeonhole principle.
Let us do so. We seek five rooks that do not attack one another. Two rooks do
not attack if they are located on different rows and different columns. So we need to
find five rooks, each living in a different row, and each living in a different column. A
vague strategy: we need five different rows, each with "lots" of rooks. Then we could
pick a rook from one row, find another rook in a different column in the other row,
etc. There are 10 rows and 41 rooks, so the pigeonhole principle tells us that one row
must contain at least r 41/ 101 = 5 rooks. This is a start. Can we apply the pigeonhole
principle again to get more information? Yes! What is happening with the other rows?
We want to find other rows that have lots of rooks. We have isolated one row with at
least five rooks. Now remove it! At most, we will remove 10 rooks. That leaves 31
rooks on the remaining nine rows. The pigeonhole principle tells us that one of these
nine rows must contain at least r3 1 /91 = 4 rooks.
Now we are on a roll. Removing this row, and "pigeonholing" once more, we
deduce that there is another row containing at least r2 1 /81 = 3 rooks. Continuing
(verify!), we see that another row must have at least two rooks, and one more row
must contain at least one rook.
Therefore there are five special rows on the chessboard, containing at least 5, 4, 3,
2 and 1 rooks, respectively. Now we can construct the "pacifistic quintuplet": Start by