256
Sets, Combinatorics, and Probability
Often a counting problem can be solved in more than one way. Although the
possibility of a second solution might seem confusing, it provides an excellent
way to check our work; if two different ways of looking at the problem produce
the same answer, it increases our confidence that we have analyzed the problem
correctly.
example 34
How many four-digit numbers begin with a 4 or a 5?
We can consider the two disjoint cases—numbers that begin with 4 and numbers that begin with 5. Counting the numbers that begin with 4, there is 1 outcome for the subtask of choosing the first digit, then 10 possible outcomes for the
subtasks of choosing each of the other three digits. Hence, by the multiplication
principle there are 1 # 10 # 10 # 10 = 1000 ways to get a four-digit number beginning
with 4. The same reasoning shows that there are 1000 ways to get a four-digit number beginning with 5. By the addition principle, there are 1000 + 1000 = 2000 total
possible outcomes.
■
PraCtiCe 23 If a woman has 7 blouses, 5 skirts, and 9 dresses, how many different outfits does she
have?
example 35
Consider the problem of Example 34 again. We can avoid using the addition principle by thinking of the problem as four successive subtasks, where the first subtask,
choosing the first digit, has two possible outcomes—choosing a 4 or choosing a 5.
Then there are 2 # 10 # 10 # 10 = 2000 possible outcomes.
example 36
How many three-digit integers (numbers between 100 and 999 inclusive) are even?
One solution notes that an even number ends in 0, 2, 4, 6, or 8. Taking these
as separate cases, the number of three-digit integers ending in 0 can be found by
choosing the three digits in turn. There are 9 choices, 1 through 9, for the first digit;
10 choices, 0 through 9, for the second digit; and 1 choice for the third digit, 0.
By the multiplication principle, there are 90 numbers ending in 0. Similarly, there
are 90 numbers ending in 2, 4, 6, and 8, so by the addition principle, there are
90 + 90 + 90 + 90 + 90 = 450 numbers.
Another solution takes advantage of the fact that there are only 5 choices for
the third digit. By the multiplication principle, there are 9 # 10 # 5 = 450 numbers.
For this problem, there is a third solution of the “serendipity” type we discussed in Section 2.1. There are 999 − 100 + 1 = 900 three-digit integers in the
range specified. Half are even and half are odd, so 450 of them must be even.
example 37
Suppose the last four digits of a telephone number must include at least one repeated digit. How many such numbers are there?
Although it is possible to do this problem by using the addition principle directly, it is difficult because there are so many disjoint cases to consider. For example,
if the first two digits are alike but the third and fourth are different, there are
10 # 1 # 9 # 8 ways this can happen. If the first and third digit are alike but the second
Sets, Combinatorics, and Probability
Often a counting problem can be solved in more than one way. Although the
possibility of a second solution might seem confusing, it provides an excellent
way to check our work; if two different ways of looking at the problem produce
the same answer, it increases our confidence that we have analyzed the problem
correctly.
example 34
How many four-digit numbers begin with a 4 or a 5?
We can consider the two disjoint cases—numbers that begin with 4 and numbers that begin with 5. Counting the numbers that begin with 4, there is 1 outcome for the subtask of choosing the first digit, then 10 possible outcomes for the
subtasks of choosing each of the other three digits. Hence, by the multiplication
principle there are 1 # 10 # 10 # 10 = 1000 ways to get a four-digit number beginning
with 4. The same reasoning shows that there are 1000 ways to get a four-digit number beginning with 5. By the addition principle, there are 1000 + 1000 = 2000 total
possible outcomes.
■
PraCtiCe 23 If a woman has 7 blouses, 5 skirts, and 9 dresses, how many different outfits does she
have?
example 35
Consider the problem of Example 34 again. We can avoid using the addition principle by thinking of the problem as four successive subtasks, where the first subtask,
choosing the first digit, has two possible outcomes—choosing a 4 or choosing a 5.
Then there are 2 # 10 # 10 # 10 = 2000 possible outcomes.
example 36
How many three-digit integers (numbers between 100 and 999 inclusive) are even?
One solution notes that an even number ends in 0, 2, 4, 6, or 8. Taking these
as separate cases, the number of three-digit integers ending in 0 can be found by
choosing the three digits in turn. There are 9 choices, 1 through 9, for the first digit;
10 choices, 0 through 9, for the second digit; and 1 choice for the third digit, 0.
By the multiplication principle, there are 90 numbers ending in 0. Similarly, there
are 90 numbers ending in 2, 4, 6, and 8, so by the addition principle, there are
90 + 90 + 90 + 90 + 90 = 450 numbers.
Another solution takes advantage of the fact that there are only 5 choices for
the third digit. By the multiplication principle, there are 9 # 10 # 5 = 450 numbers.
For this problem, there is a third solution of the “serendipity” type we discussed in Section 2.1. There are 999 − 100 + 1 = 900 three-digit integers in the
range specified. Half are even and half are odd, so 450 of them must be even.
example 37
Suppose the last four digits of a telephone number must include at least one repeated digit. How many such numbers are there?
Although it is possible to do this problem by using the addition principle directly, it is difficult because there are so many disjoint cases to consider. For example,
if the first two digits are alike but the third and fourth are different, there are
10 # 1 # 9 # 8 ways this can happen. If the first and third digit are alike but the second