The Art and Craft of Problem Solving

204 CHAPTER 6 COMBINATORICS

corresponds to (5,0, 6). This method uniquely encodes each triple with a string of 1 3

symbols containing two + symbols and 11 • symbols. There are eD ways of counting

these strings (for each string is uniquely determined by which 2 of the 13 possible slots

we place the + symbol).

Finally, replacing 11 with 50, we see that the answer is

( 52 )

=

52 ·51

• 2 2'

This is of course just one example of a general tool, the balls in urns formula:

The number of different ways we can place b indistinguishable balls

into u distinguishable urns is

The balls in urns formula is amazingly useful, and turns up in many unexpected

places. Let us use it, along with the pigeonhole principle (Section 3.3), to solve Ex­

ample 6.1.1 on page 188. Recall that this problem asked whether there exist lO,OOO

lO-digit numbers divisible by 7, all of which can be obtained from one another by a

reordering of their digits.

Solution: Ignore the issue of divisibility by 7 for a moment, and concentrate on

understanding sets of numbers that "can be obtained from one another by a reorder­

ing of their digits." Let us call two numbers that can be obtained from one another in

this way "sisters," and let us call a set that is as large as possible whose elements are

all sisters a "sorority." For example, 1, 111 ,233, 999 and 9, 929, 313 , 111 are sisters

who belong to a sorority with 4 l 3 � 2

!

members, since the membership of the sorority is

just the number of ways of permuting the digits. The sororities have vastly different

sizes. The most "exclusive" sororities have only one member (for example, the soror­

ity consisting entirely of 6,666,666,666) yet one sorority has 10! members (the one

containing 1,234,567, 890).

In order to solve this problem, we need to show that there is a sorority with at

least 10,000 members that are divisible by 7. One approach is to look for big sororities

(like the one with lO! members), but it is possible (even though is seems unlikely) that

somehow most of the members will not be mUltiples of 7.

Instead, the crux idea is that

It is not the size of the sororities that really matters, but how many

sororities there are.

If the number of sororities is fairly small, then even if the multiples of 7 are dispersed

very evenly, "enough" of them will land in some sorority.

Let's make this more precise: Suppose it turned out that there were only 100

sororities (of course there are more than that). There are llOlO /7 J = 1,428,571 ,428

mUltiples of seven. By the pigeonhole principle, at least one sorority will contain

p ,428,571 ,428/ lOOl multiples of seven, which is way more than we need. In any

event, we have the penultimate step to work toward: compute (or at least estimate) the

number of sororities.