Set Decomposition Principle 431Example 10. Suppose a group of vacationers is split into 159 teams. How many leagues
must be formed if a league should contain at most 8 teams? 10 teams? 12 teams?Solution. The Generalized Pigeon-Hole Principle tells us that the answers are
Fl591 r 1591 r^1 59-1
-59 = (^20) [-1-5 = (^16) j159]=
14
It remains for the organizers to determine which size of a league is most manageable. U
In many applications, the Pigeon-Hole Principle is used to prove that a problem cannot
be solved. A typical example involves deciding what letter and digit patterns to use on
a state's license plates. Problems that must be considered when designing license plates
include how long the plates will be used and what scheme of letters and digits should
appear on a plate so that every car that is registered during the period can have a distinct
letter-digit pattern. The counting problems for license plates are good, simple examples
of using the Multiplication Principle, because each position must contain a fixed kind of
symbol. (Later, we will consider problems for which we do not know explicitly that a letter
or a digit will occur in a particular place in a pattern, just that letters and digits will occur.)
Example 11. Determine the number of different license plates that are possible using
each of the following schemes, where D represents one of the digits 0, 1, 2,..., 9 and L
represents one of the letters A, B, C ... , Z. The leading digit must not be zero (the digit in
the leftmost position).
(a) DDDDDD
(b) DDDDDL
(c) DDDLDDD
(d) DDDLLL
Solution.
(a) There are nine choices for the first digit, since it cannot be zero. There are 10 choices
for each of the other five digits. By the Multiplication Principle, the number of possi-
bilities is
9 • 10 = 900,000
(b) There are nine choices for the first digit, since it cannot be zero. There are 10 choices
for each of the other four digits. The letter can be chosen in 26 ways. By the Multipli-
cation Principle, the number of possibilities is
- 104 • 26 = 2,340,000
(c) There are nine choices for the first digit, since it cannot be zero. There are 10 choices
for each of the other five digits. There are 26 choices for the letter. By the Multiplica-
tion Principle, the number of possibilities is
- 102 .26.103 = 23,400,000
(d) There are nine choices for the first digit, since it cannot be zero. There are 10 choices
for each of the other two digits. There are 26 choices for each of the letter positions.
By the Multiplication Principle, the number of possibilities is
- 102'. 26' = 15,818,400 E