88 CHAPTER^3 TACTICS FOR SOLVING PROBLEMS
... + a j. So our pigeons have the right behavior, but unfortunately, there are only n of
them. But that is not as bad as it seems. Sometimes (as in Example 3.3.4) you can
reduce the number of pigeonholes needed by dividing into cases.
We have n pigeons PI ,P 2 , ... ,Pn. There are two cases.- One of the pigeons has a remainder of 0 upon division by n, in which case we
are done! (Why?) - None of the pigeons has a remainder of 0, so now we have just n - I pigeon
holes to consider. With n pigeons, two of them must have the same remainder,
so their difference, a sum of several of the original numbers, will be a mUltiple
of n, and we are done. _
The next example is a famous problem, due to the great Paul Erd6s,^4 that is re
markable because the difficulty is in the pigeonholes, not the pigeons.
Example 3.3.7 Let n be a positive integer. Choose any (n + I)-element subset of
{I, 2, ... , 2n}. Show that this subset must contain two integers, one of which divides
the other.Investigation: The language of the problem leads us to try the pigeonhole princi
ple, fixing the n + 1 numbers in the chosen subset as the pigeons. We need to create
at most n pigeonholes, since there are n + 1 pigeons. And we want our pigeonholes
chosen so that if two numbers inhabit the same hole, then one of them must divide the
other. Each pigeonhole, then, is a set of integers with the property that if a and b are
any two elements of the set, either a is a multiple of b or b is a multiple of a.
Let's try to construct such a set. If the set contains 7, then all the other numbers
must be either factors of 7 or mUltiples of 7. Let's say the next number in the set is 21.
Then the other numbers now must be either multiples of 21 or factors of 7, etc. So if
7 is the smallest number in the set, the set would be a list of numbers of the following
form: 7, 7a, 7ab, 7abc, 7abcd, ... , where a, b, c, d, etc. are positive integers.
Our task, then, is to partition the set {I, 2, ... , 2n} into at most n disjoint sub
sets with the above property. This is not easy; the best thing to do at this point is
experiment with small values of n. For example, let n = 5. Let's try to partition
{1,2,3,4,5,6, 7, 8, 9 , 1O} into five disjoint subsets with the special property. Each set
has a smallest element, so we need to pick five such "seeds." In striving for a general
method---one that can be used for other values of n-the only "natural" collection of
five seeds is 1,3,5,7,9. (The list 2, 4, 6,8, 10 doesn't include 1, and 1 has to be the
minimum element of one of the sets, so this list is not a "natural" candidate for our
seeds.)
Notice that each seed is odd. To get the remaining numbers, we just have to
multiply the seeds by 2. But that won't quite work, as we will not get all the numbers.
If we keep on multiplying, though, we get the partition
{1,2,4, 8}; {3,6}; {5,1O}; {7}; {9}.(^4) Erdos, who died in 1996 at the age of 83, was the most prolific mathematician of modem times, having
authored or co-authored more than 1,000 research papers.