3.3 THE PIGEONHOLE PRINCIPLE 85- After applying the pigeonhole principle, there is often more work to be done.
Sometimes the pigeonhole principle yields only the "penultimate step," and
sometimes just an intermediate result. The skilled problem solver plans for
this when thinking of a strategy.
Here's a simple problem that illustrates the coordination of a good penultimate
step with the pigeonhole principle. You will use this problem as a building-block in
many other problems later.
Example 3.3.3 Show that among any n + 1 positive integers, there must be two whose
difference is a mUltiple of n.
Solution: The penultimate step, of course, is realizing that the two desired num
bers must have same remainder upon division by n. Since there are only n possible
remainders, we are done. _
This next problem is a bit more intricate. Also note the strategic element of con
fidence present in the solution. This is not a terribly hard problem for those who are
brave and tenacious.
Example 3.3.4 (IMO 1972) Prove that from a set of ten distinct two-digit numbers (in
the decimal system), it is possible to select two disjoint subsets whose members have
the same sum.
Solution: We want to have two subsets have the same sum, so it is reasonable
to make the subsets be the pigeons, and the sums be the holes. How do we do this
precisely? First, let's look at the sums. The smallest possible sum is 10 and the largest
possible sum is 99 +98 +97 + ... +90. Using the Gaussian pairing trick (for practice),
this is 189·5 = 945. Consequently, there are 945 - 10 + 1 = 936 different sums.
Now we need to count the number of pigeons. The number of subsets (see Sec
tion 6. 1) is just 2 IO = 1024. Since 1024 > 936, there are more pigeons than holes, so
we are done: two of the subsets must have the same sum.
But are we done? Not quite yet. The problem specifies that the two subsets are
disjoint! Don't panic. It would of course be bad problem solving form to abandon our
solution at this point, for we have already achieved a partial solution: we have shown
that there are two different subsets (perhaps not disjoint) that have the same sum. Can
we use this to find two disjoint subsets with the same sum? Of course. Let A and B be
the two sets. Divide into cases:
• A and B are disjoint. Done!
• A and B are not disjoint. From each set, remove the elements that they have in
common. Now we have disjoint sets, but the sums are still the same (why?), so
we are done! _You might wonder, "What if, after removing the common elements, we had noth
ing left from one of the sets?" That is impossible. Why?