Tan S.T. Finite Mathematics for the Managerial, Life, and Social Sciences
Подождите немного. Документ загружается.
In Exercises 49 and 50, let U denote the set of all stu-
dents in the business college of a certain university. Let
A ⴝ
{
x 苸 U 兩 x had taken a course in accounting
}
B ⴝ
{
x 苸 U 兩 x had taken a course in economics
}
C ⴝ
{
x 苸 U 兩 x had taken a course in marketing
}
Write the set that represents each statement.
49. a. The set of students who have not had a course in
economics
b. The set of students who have had courses in accounting
and economics
c. The set of students who have had courses in accounting
and economics but not marketing
50. a. The set of students who have had courses in economics
but not courses in accounting or marketing
b. The set of students who have had at least one of the
three courses
c. The set of students who have had all three courses
In Exercises 51 and 52, refer to the following diagram,
where
U is the set of all tourists surveyed over a 1-week
period in London and where
A ⴝ
{
x 苸 U 兩 x has taken the underground [subway]
}
B ⴝ
{
x 苸 U 兩 x has taken a cab
}
C ⴝ
{
x 苸 U 兩 x has taken a bus
}
Express the indicated regions in set notation and in
words.
51. a. Region 1
b. Regions 1 and 4 together
c. Regions 4, 5, 7, and 8 together
52. a. Region 3
b. Regions 4 and 6 together
c. Regions 5, 6, and 7 together
In Exercises 53–58, use Venn diagrams to illustrate each
statement.
53. A 債 A 傼 B; B 債 A 傼 B 54. A 傽 B 債 A; A 傽 B 債 B
55. A 傼 (B 傼 C) (A 傼 B) 傼 C
56. A 傽 (B 傽 C) (A 傽 B) 傽 C
U
C
A B
76
3
1
42
5
8
57. A 傽 (B 傼 C) (A 傽 B) 傼 (A 傽 C)
58. (A 傼 B)
c
A
c
傽 B
c
In Exercises 59 and 60, let
U ⴝ
{
1, 2, 3, 4, 5, 6, 7, 8, 9, 10
}
A ⴝ
{
1, 3, 5, 7, 9
}
B ⴝ
{
1, 2, 4, 7, 8
}
C ⴝ
{
2, 4, 6, 8
}
Verify each equation by direct computation.
59. a. A 傼 (B 傼 C) (A 傼 B) 傼 C
b. A 傽 (B 傽 C) (A 傽 B) 傽 C
60. a. A 傽 (B 傼 C) (A 傽 B) 傼 (A 傽 C)
b. (A 傼 B)
c
A
c
傽 B
c
In Exercises 61–64, refer to the accompanying figure and
list the points that belong to each set.
61. a. A 傼 B b. A 傽 B
62. a. A 傽 (B 傼 C) b. (B 傽 C)
c
63. a. (B 傼 C)
c
b. A
c
64. a. (A 傽 B) 傽 C
c
b. (A 傼 B 傼 C)
c
65. Suppose A 傺 B and B 傺 C, where A and B are any two sets.
What conclusion can be drawn regarding the sets A and C?
66. Verify the assertion that two sets A and B are equal if and
only if (1) A 債 B and (2) B 債 A.
In Exercises 67–72, determine whether the statement is
true or false. If it is true, explain why it is true. If it is
false, give an example to show why it is false.
67. A set is never a subset of itself.
68. A proper subset of a set is itself a subset of the set but not
necessarily vice versa.
69. If A 傼 B , then A and B .
70. If A 傽 B , then either A or B .
71. (A 傼 A
c
)
c
72. If A 債 B, then A 傽 B A.
U
C
B A
st
x
w
r
√
u
z
y
322 6 SETS AND COUNTING
87533_06_ch6_p313-352 1/30/08 10:01 AM Page 322
1. a. A
c
is the set of all elements in U but not in A. Therefore,
A
c
{4, 5, 6, 7}
b. A 傼 B consists of all elements in A and/or B. Hence,
A 傼 B {1, 2, 3, 4, 5, 6}
c. B 傽 C is the set of all elements in both B and C. There-
fore,
B 傽 C {3, 4}
d. Using the result from part (b), we find
(A 傼 B) 傽 C {1, 2, 3, 4, 5, 6} 傽 {2, 3, 4}
{2, 3, 4}
e. First, we compute
A 傽 B {3}
Next, since (A 傽 B) 傼 C is the set of all elements in
(A 傽 B) and/or C, we conclude that
(A 傽 B) 傼 C {3} 傼 {2, 3, 4}
{2, 3, 4}
f. From part (a), we have A
c
{4, 5, 6, 7}. Next, we
compute
B 傼 C {3, 4, 5, 6} 傼 {2, 3, 4}
{2, 3, 4, 5, 6}
from which we deduce that
(B 傼 C )
c
{1, 7}
Finally, using these results, we obtain
A
c
傽 (B 傼 C )
c
{4, 5, 6, 7} 傽 {1, 7} {7}
2. a. D 傽 F denotes the set of all elements in both D and F.
Since an element in D is a Democrat and an element in F
is a female representative, we see that D 傽 F is the set of
all female Democrats in the House of Representatives.
b. Since F
c
is the set of male representatives and R is the
set of Republicans, it follows that F
c
傽 R is the set of
male Republicans in the House of Representatives.
c. L
c
is the set of representatives who are not lawyers by
training. Therefore, D 傽 F 傽 L
c
is the set of female
Democratic representatives who are not lawyers by
training.
6.2 THE NUMBER OF ELEMENTS IN A FINITE SET 323
6.1 Solutions to Self-Check Exercises
6.2 The Number of Elements in a Finite Set
Counting the Elements in a Set
The solution to some problems in mathematics calls for finding the number of ele-
ments in a set. Such problems are called counting problems and constitute a field of
study known as combinatorics. Our study of combinatorics is restricted to the results
that will be required for our work in probability later on.
The number of elements in a finite set is determined by simply counting the ele-
ments in the set. If A is a set, then n(A) denotes the number of elements in A. For exam-
ple, if
A {1, 2, 3, . . . , 20} B {a, b} C {8}
then n(A) 20, n(B) 2, and n(C) 1.
The empty set has no elements in it, so n() 0. Another result that is easily seen
to be true is the following: If A and B are disjoint sets, then
n(A 傼 B) n(A) n(B) (3)
EXAMPLE 1
If A {a, c, d} and B {b, e, f, t}, then n(A) 3 and n(B) 4, so
n(A) n(B) 7. Moreover, A 傼 B {a, b, c, d, e, f, t} and n(A 傼 B) 7. Thus,
Equation (3) holds true in this case. Note that A 傽 B .
In the general case, A and B need not be disjoint, which leads us to the formula
(4)
n1A 傼 B2 n1A2 n1B 2 n1A 艚 B 2
The set of elements
in
U
but not in
B
傼
C
87533_06_ch6_p313-352 1/30/08 10:01 AM Page 323
324 6 SETS AND COUNTING
To see this, we observe that the set A 傼 B may be viewed as the union of three
mutually disjoint sets with x, y, and z elements, respectively (Figure 8). This figure
shows that
n(A 傼 B) x y z
Also,
n(A) x y and n(B) y z
so
n
(
A
傽
B
)
y
Solving for n(A 傼 B), we obtain
n(A 傼 B) n(A) n(B) n(A 傽 B)
which is the desired result.
EXAMPLE 2
Let A {a, b, c, d, e} and B {b, d, f, h}. Verify Equation (4)
directly.
Solution
A 傼 B {a, b, c, d, e, f, h} so n(A 傼 B) 7
A 傽 B {b, d} so n(A 傽 B) 2
Furthermore,
n(A) 5 and n(B) 4
so
n(A) n(B) n(A 傽 B) 5 4 2 7 n(A 傼 B)
APPLIED EXAMPLE 3
Consumer Surveys In a survey of 100 coffee
drinkers, it was found that 70 take sugar, 60 take cream, and 50 take both
sugar and cream with their coffee. How many coffee drinkers take sugar or cream
with their coffee?
Solution
Let U denote the set of 100 coffee drinkers surveyed, and let
A {x 僆 U 0x takes sugar}
B {x 僆 U 0x takes cream}
Then, n(A) 70, n(B) 60, and n(A 傽 B) 50. The set of coffee drinkers who
take sugar or cream with their coffee is given by A 傼 B. Using Equation (4), we find
n(A 傼 B) n(A) n(B) n(A 傽 B)
70 60 50 80
Thus, 80 out of the 100 coffee drinkers surveyed take cream or sugar with their
coffee.
An equation similar to (4) can be derived for the case that involves any finite number
of finite sets. For example, a relationship involving the number of elements in the sets
A, B, and C is given by
(5)
n1A 傼 B2 n1A 艚 B 2
1x y z2 y
n1A2 n1B2 1x y 2 1y z2
A
x
y
B
z
FIGURE 8
n(A 傼 B) x y z
Explore & Discuss
Prove Formula (5), using an
argument similar to that used to
prove Formula (4). Another
proof is outlined in Exercise 41
on page 329.
n1A 艚 C2 n1B 艚 C2 n1A 艚 B 艚 C2
n1A 傼 B 傼 C2 n1A2 n1B 2 n1C 2 n1A 艚 B 2
87533_06_ch6_p313-352 1/30/08 10:01 AM Page 324
As useful as equations such as (5) are, in practice it is often easier to attack
a problem directly with the aid of Venn diagrams, as shown by the following example.
APPLIED EXAMPLE 4
Marketing Surveys A leading cosmetics
manufacturer advertises its products in three magazines: Allure,
Cosmopolitan, and the Ladies Home Journal. A survey of 500 customers by the
manufacturer reveals the following information:
180 learned of its products from Allure.
200 learned of its products from Cosmopolitan.
192 learned of its products from the Ladies Home Journal.
84 learned of its products from Allure and Cosmopolitan.
52 learned of its products from Allure and the Ladies Home Journal.
64 learned of its products from Cosmopolitan and the Ladies Home Journal.
38 learned of its products from all three magazines.
How many of the customers saw the manufacturer’s advertisement in
a. At least one magazine?
b. Exactly one magazine?
Solution
Let U denote the set of all customers surveyed, and let
A {x 僆 U 0x learned of the products from Allure}
C {x 僆 U 0x learned of the products from Cosmopolitan}
L {x 僆 U 0x learned of the products from the Ladies Home Journal}
The result that 38 customers learned of the products from all three magazines
translates into n(A 傽 C 傽 L) 38 (Figure 9a). Next, the result that 64 learned
of the products from Cosmopolitan and the Ladies Home Journal translates into
n(C 傽 L) 64. This leaves
64 38 26
who learned of the products from only Cosmopolitan and the Ladies Home Jour-
nal (Figure 9b). Similarly, n(A 傽 L) 52, so
52 38 14
learned of the products from only Allure and the Ladies Home Journal, and
n(A 傽 C) 84, so
84 38 46
learned of the products from only Allure and Cosmopolitan. These numbers
appear in the appropriate regions in Figure 9b.
(a) All three magazines (b) Two or more magazines
Continuing, we have n(L) 192, so the number who learned of the products
from the Ladies Home Journal only is given by
192 14 38 26 114
U
L
A C
U
L
A
C
38
14
46
38
26
6.2 THE NUMBER OF ELEMENTS IN A FINITE SET 325
FIGURE 9
87533_06_ch6_p313-352 1/30/08 10:01 AM Page 325
326 6 SETS AND COUNTING
(Figure 10). Similarly, n(C) 200, so
200 46 38 26 90
learned of the products from only Cosmopolitan, and n(A) 180, so
180 14 38 46 82
learned of the products from only Allure. Finally,
500 (90 26 114 14 82 46 38) 90
learned of the products from other sources.
We are now in a position to answer questions (a) and (b).
a. Referring to Figure 10, we see that the number of customers who learned of
the products from at least one magazine is given by
n(A 傼 C 傼 L) 500 90 410
b. The number of customers who learned of the products from exactly one maga-
zine (Figure 11) is given by
n(L 傽 A
c
傽 C
c
) n(C 傽 A
c
傽 L
c
) n(A 傽 L
c
傽 C
c
)
114 90 82 286
U
L
A
C
82 90
114
U
L
A
90
C
82
14
114
26
38
46
90
FIGURE 10
The completed Venn diagram
1. Let A and B be subsets of a universal set U and suppose
that n(U) 100, n(A) 60, n(B) 40, and n(A 傽 B)
20. Compute:
a. n(A 傼 B) b. n(A 傽 B
c
) c. n(A
c
傽 B)
2. In a survey of 1000 readers of Video Magazine, it was
found that 166 own at least one HD player in the HD-DVD
format, 161 own at least one HD player in the Blu-ray
format, and 22 own HD players in both formats. How
many of the readers surveyed own a HD player in the HD-
DVD format only? How many of the readers surveyed do
not own a HD-player in either format?
Solutions to Self-Check Exercises 6.2 can be found on
page 329.
1. a. If A and B are sets with A 傽 B , what can you say
about n(A) n(B)? Explain.
b. If A and B are sets satisfying n(A 傼 B) n(A) n(B),
what can you say about A 傽 B? Explain.
2. Let A and B be subsets of U, the universal set, and suppose
A 傽 B . Is it true that n(A) n(B) n(B
c
) n(A
c
)?
Explain.
In Exercises 1 and 2, verify the equation
n(A 僔 B) ⴝ n(A) ⴙ n(B)
for the given disjoint sets.
1. A {a, e, i, o, u} and B {t, h, k, l, m}
2. A {x 0x is a whole number between 0 and 4}
B {x 0x is a negative integer greater than 4}
3. Let A {2, 4, 6, 8} and B {6, 7, 8, 9, 10}. Compute:
a. n(A) b. n(B)
c. n(A 傼 B) d. n(A 傽 B)
FIGURE 11
Exactly one magazine
6.2 Self-Check Exercises
6.2 Concept Questions
6.2 Exercises
87533_06_ch6_p313-352 1/30/08 10:01 AM Page 326
4. Let U {1, 2, 3, 4, 5, 6, 7, a, b, c, d, e}. If A {1, 2, a, e}
and B {1, 2, 3, 4, a, b, c}, find:
a. n(A
c
) b. n(A 傽 B
c
)
c. n(A 傼 B
c
) d. n(A
c
傽 B
c
)
5. Verify directly that n(A 傼 B) n(A) n(B) n(A 傽 B)
for the sets in Exercise 3.
6. Let A {a, e, i, o, u} and B {b, d, e, o, u}. Verify by direct
computation that n(A 傼 B) n(A) n(B) n(A 傽 B).
7. If n(A) 15, n(A 傽 B) 5, and n(A 傼
B) 30, then what
is n(B)?
8. If n(A) 10, n(A 傼 B) 15, and n(B) 8, then what is
n(A 傽 B)?
In Exercises 9 and 10, let A and B be subsets of a univer-
sal set U and suppose n(U) ⴝ 200, n(A) ⴝ 100, n(B) ⴝ 80,
and n(AB) ⴝ 40. Compute:
9. a. n(A 傼 B) b. n(A
c
) c. n(A 傽 B
c
)
10. a. n(A
c
傽 B) b. n(B
c
) c. n(A
c
傽 B
c
)
11. Find n(A 傼 B) given that n(A) 6, n(B) 10, and
n(A 傽 B) 3.
12. If n(B) 6, n(A 傼 B) 14, and n(A 傽 B) 3, find n(A).
13. If n(A) 4, n(B) 5, and n(A 傼 B) 9, find n(A 傽 B).
14. If n(A) 16, n(B) 16, n(
C) 14, n(A 傽 B) 6,
n(A 傽 C ) 5, n(B 傽 C) 6, and n(A 傼 B 傼 C ) 31,
find n(A 傽 B 傽 C ).
15. If n(A) 12, n(B) 12, n(A 傽 B) 5, n(A 傽 C ) 5,
n(B 傽 C) 4, n(A 傽 B 傽 C ) 2, and n(A 傼 B 傼
C)
25, find n(C).
16. A survey of 1000 subscribers to the Los Angeles Times
revealed that 900 people subscribe to the daily morning
edition and 500 subscribe to both the daily morning and the
Sunday editions. How many subscribe to the Sunday edi-
tion? How many subscribe to the Sunday edition only?
17. On a certain day, the Wilton County Jail held 190 prison-
ers accused of a crime (felony and/or misdemeanor). Of
these, 130 were accused of felonies and 121 were accused
of misdemeanors. How many prisoners were accused of
both a felony and a misdemeanor?
18. Of 100 clock radios with digital tuners and/or CD players
sold recently in a department store, 70 had digital tuners
and 90 had CD players. How many radios had both digital
tuners and CD players?
19. C
ONSUMER
S
URVEYS
In a survey of 120 consumers con-
ducted in a shopping mall, 80 consumers indicated that
they buy brand A of a certain product, 68 buy brand B, and
42 buy both brands. How many consumers participating in
the survey buy
a. At least one of these brands?
b. Exactly one of these brands?
c. Only brand A?
d. None of these brands?
僔
20. C
ONSUMER
S
URVEYS
In a survey of 200 members of a local
sports club, 100 members indicated that they plan to attend
the next Summer Olympic Games, 60 indicated that they
plan to attend the next Winter Olympic Games, and 40
indicated that they plan to attend both games. How many
members of the club plan to attend
a. At least one of the two games?
b. Exactly one of the games?
c. The Summer Olympic Games only?
d. None of the games?
21. I
NVESTING
In a poll conducted among 200 active investors,
it was found that 120 use discount brokers, 126 use full-
service brokers, and 64 use both discount and full-service
brokers. How many investors
a. Use at least one kind of broker?
b. Use exactly one kind of broker?
c. Use only discount brokers?
d. Don’t use a broker?
22. C
OMMUTER
T
RENDS
Of 50 employees of a store located in
downtown Boston, 18 people take the subway to work, 12
take the bus, and 7 take both the subway and the bus. How
many employees
a. Take the subway or the bus to work?
b. Take only the bus to work?
c. Take either the bus or the subway to work?
d. Get to work by some other means?
23. C
ONSUMER
S
URVEYS
In a survey of 200 households re-
garding the ownership of desktop and laptop computers,
the following information was obtained:
120 households own only desktop computers.
10 households own only laptop computers.
40 households own neither desktop nor laptop computers.
How many households own both desktop and laptop com-
puters?
24. C
ONSUMER
S
URVEYS
In a survey of 400 households regard-
ing the ownership of VCRs and DVD players, the follow-
ing data were obtained:
360 households own one or more VCRs.
170 households own one or more VCRs and one or more
DVD players.
19 households do not own a VCR or a DVD player.
How many households own only one or more DVD players?
In Exercises 25–28, let A, B, and C be subsets of a univer-
sal set U and suppose n(U) ⴝ 100, n(A) ⴝ 28, n(B) ⴝ 30,
n(C) ⴝ 34, n(AB) ⴝ 8, n(AC) ⴝ 10, n(BC) ⴝ 15,
25. a. n(A 傼 B 傼 C) b. n(A
c
傽 B 傽 C)
26. a. n[A 傽 (B 傼 C)] b. n[A 傽 (B 傼 C)
c
]
27. a. n(A
c
傽 B
c
傽 C
c
) b. n[A
c
傽 (B 傼 C)]
28. a. n[A 傼 (B 傽 C)] b. n[(A
c
傽 B
c
傽 C
c
)
c
]
僔僔僔
6.2 THE NUMBER OF ELEMENTS IN A FINITE SET 327
and n(ABC) ⴝ 5. Compute:
僔僔
87533_06_ch6_p313-352 1/30/08 10:01 AM Page 327
29. E
CONOMIC
S
URVEYS
A survey of the opinions of 10 leading
economists in a certain country showed that, because oil
prices were expected to drop in that country over the next
12 months,
7 had lowered their estimate of the consumer inflation rate.
8 had raised their estimate of the gross national product
(GNP) growth rate.
2 had lowered their estimate of the consumer inflation rate
but had not raised their estimate of the GNP growth rate.
How many economists had both lowered their estimate of
the consumer inflation rate and raised their estimate of the
GNP growth rate for that period?
30. S
TUDENT
D
ROPOUT
R
ATE
Data released by the Department
of Education regarding the rate (percentage) of ninth-grade
students who don’t graduate showed that, out of 50 states,
12 states had an increase in the dropout rate during the past
2 yr.
15 states had a dropout rate of at least 30% during the past
2 yr.
21 states had an increase in the dropout rate and/or a
dropout rate of at least 30% during the past 2 yr.
a. How many states had both a dropout rate of at least
30% and an increase in the dropout rate over the 2-yr
period?
b. How many states had a dropout rate that was less than
30% but that had increased over the 2-yr period?
31. S
TUDENT
R
EADING
H
ABITS
A survey of 100 college students
who frequent the reading lounge of a university revealed
the following results:
40 read Time.
30 read Newsweek.
25 read U.S. News & World Report.
15 read Time and Newsweek.
12 read Time and U.S. News & World Report.
10 read Newsweek and U.S. News & World Report.
4 read all three magazines.
How many of the students surveyed read
a. At least one of these magazines?
b. Exactly one of these magazines?
c. Exactly two of these magazines?
d. None of these magazines?
32. SAT S
CORES
Results of a Department of Education survey
of SAT test scores in 22 states showed that
10 states had an average composite SAT score of at least
1000 during the past 3 yr.
15 states had an increase of at least 10 points in the aver-
age composite SAT score during the past 3 yr.
8 states had both an average composite SAT score of at
least 1000 and an increase in the average composite
SAT score of at least 10 points during the past 3 yr.
a. How many of the 22 states had composite SAT scores
of less than 1000 and showed an increase of at least 10
points over the 3-yr period?
b. How many of the 22 states had composite SAT scores
of at least 1000 and did not show an increase of at least
10 points over the 3-yr period?
33. C
ONSUMER
S
URVEYS
The 120 consumers of Exercise 19
were also asked about their buying preferences concerning
another product that is sold in the market under three
labels. The results were
12 buy only those sold under label A.
25 buy only those sold under label B.
26 buy only those sold under label C.
15 buy only those sold under labels A and B.
10 buy only those sold under labels A and C.
12 buy only those sold under labels B and C.
8 buy the product sold under all three labels.
How many of the consumers surveyed buy the product sold
under
a. At least one of the three labels?
b. Labels A and B but not C?
c. Label A?
d. None of these labels?
34. S
TUDENT
S
URVEYS
To help plan the number of meals
(breakfast, lunch, and dinner) to be prepared in a college
cafeteria, a survey was conducted and the following data
were obtained:
130 students ate breakfast.
180 students ate lunch.
275 students ate dinner.
68 students ate breakfast and lunch.
112 students ate breakfast and dinner.
90 students ate lunch and dinner.
58 students ate all three meals.
How many of the students ate
a. At least one meal in the cafeteria?
b. Exactly one meal in the cafeteria?
c. Only dinner in the cafeteria?
d. Exactly two meals in the cafeteria?
35. I
NVESTMENTS
In a survey of 200 employees of a company
regarding their 401(k) investments, the following data
were obtained:
141 had investments in stock funds.
91 had investments in bond funds.
60 had investments in money market funds.
47 had investments in stock funds and bond funds.
36 had investments in stock funds and money market
funds.
36 had investments in bond funds and money market funds.
5 had investments only in some other vehicle.
328
6 SETS AND COUNTING
87533_06_ch6_p313-352 1/30/08 10:01 AM Page 328
a. How many of the employees surveyed had investments
in all three types of funds?
b. How many of the employees had investments in stock
funds only?
36. N
EWSPAPER
S
UBSCRIPTIONS
In a survey of 300 individual
investors regarding subscriptions to the New York Times
(NYT ), Wall Street Journal (WSJ), and USA Today (UST ),
the following data were obtained:
122 subscribe to the NYT.
150 subscribe to the WSJ.
62 subscribe to the UST.
38 subscribe to the NYT and WSJ.
20 subscribe to the NYT and UST.
28 subscribe to the WSJ and UST.
36 do not subscribe to any of these newspapers.
a. How many of the individual investors surveyed sub-
scribe to all three newspapers?
b. How many subscribe to only one of these newspapers?
In Exercises 37–40, determine whether the statement is
true or false. If it is true, explain why it is true. If it is
false, give an example to show why it is false.
37. If A 傽 B , then n(A 傼 B) n(A) n(B).
38. If A 債 B, then n(B) n(A) n(A
c
傽 B).
39. If n(A 傼 B) n(A) n(B), then A 傽 B .
40. If n(A 傼 B) 0, then A .
41. Derive Equation (5).
Hint: Equation (4) can be written as n(D 傼 E) n(D) n(E)
n(D 傽 E). Now, put D A 傼 B and E C. Use (4) again if
necessary.
42. Find conditions on the sets A, B, and C so that n(A 傼 B 傼 C)
n(A) n(B) n(C).
6.3 THE MULTIPLICATION PRINCIPLE 329
6.2 Solutions to Self-Check Exercises
1. Use the given information to construct the following Venn
diagram:
Using this diagram we see that
a. n(A 傼 B) 40 20 20 80
b. n(A 傽 B
c
) 40
c. n(A
c
傽 B) 20
2. Let U denote the set of all readers surveyed, and let
A {x 僆 U 0x owns at least one HD-player in the HD-DVD
format}
B {x 僆 U 0x owns at least one HD-player in the Blu-ray
format}
A
U
B
40 20 20
20
Then, the fact that 22 of the readers own HD-players in
both formats means that n(A 傽 B) 22. Also, n(A) 166
and n(B) 161. Using this information, we obtain the fol-
lowing Venn diagram:
From the Venn diagram, we see that the number of readers
who own a HD-player in the HD-DVD format only is given
by
n(A 傽 B
c
) 144
The number of readers who do not own a HD-player in
either format is given by
n(A
c
傽 B
c
) 695
A
U
B
139
695
144 22
6.3 The Multiplication Principle
The Fundamental Principle of Counting
The solution of certain problems requires more sophisticated counting techniques than
those developed in the previous section. We look at some such techniques in this and
the following section. We begin by stating a fundamental principle of counting called
the multiplication principle.
87533_06_ch6_p313-352 1/30/08 10:01 AM Page 329
EXAMPLE 1
Three trunk roads connect town A and town B, and two trunk roads
connect town B and town C.
a. Use the multiplication principle to find the number of ways a journey from town
A to town C via town B can be completed.
b. Verify part (a) directly by exhibiting all possible routes.
Solution
a. Since there are three ways of performing the first task (going from town A to
town B) followed by two ways of performing the second task (going from town
B to town C), the multiplication principle says that there are 3
2, or 6, ways to
complete a journey from town A to town C via town B.
b. Label the trunk roads connecting town A and town B with the Roman numerals I,
II, and III, and label the trunk roads connecting town B and town C with the low-
ercase letters a and b. A schematic of this is shown in Figure 12. Then the routes
from town A to town C via town B can be exhibited with the aid of a tree dia-
gram (Figure 13).
If we follow all of the branches from the initial point A to the right-hand edge of
the tree, we obtain the six routes represented by six ordered pairs:
(I, a), (I, b), (II, a), (II, b), (III, a), (III, b)
where (I, a) means that the journey from town A to town B is made on trunk
road I with the rest of the journey, from town B to town C, completed on trunk
road a, and so forth.
A
C
B
I
II
III
a
b
a
b
a
b
(I, a)
(I, b)
(II, a)
(II, b)
(III, a)
(III, b
)
Combined
outcomes
A
C
B
I
II
III
a
b
The Multiplication Principle
Suppose there are m ways of performing a task T
1
and n ways of performing
a task T
2
. Then, there are mn ways of performing the task T
1
followed by the
task T
2
.
330 6 SETS AND COUNTING
FIGURE 13
Tree diagram displaying the possible
routes from town A to town C
FIGURE 12
Roads from town A to town C
87533_06_ch6_p313-352 1/30/08 10:01 AM Page 330
APPLIED EXAMPLE 2
Menu Choices Diners at Angelo’s Spaghetti
Bar can select their entree from 6 varieties of pasta and 28 choices of
sauce. How many such combinations are there that consist of 1 variety of pasta
and 1 kind of sauce?
Solution
There are 6 ways of choosing a pasta followed by 28 ways of choos-
ing a sauce, so by the multiplication principle, there are 6
28, or 168, combina-
tions of this pasta dish.
The multiplication principle can be easily extended, which leads to the generalized
multiplication principle.
6.3 THE MULTIPLICATION PRINCIPLE 331
Explore & Discuss
One way of gauging the performance of an airline is to track the arrival times of its flights.
Suppose we denote by E, O, and L a flight that arrives early, on time, or late, respectively.
1. Use a tree diagram to exhibit the possible outcomes when you track two successive
flights of the airline. How many outcomes are there?
2. How many outcomes are there if you track three successive flights? Justify your answer.
PORTFOLIO
Working as a detective in the
computer crimes division of the
Maricopa County Sheriff’s Office,
I find applied mathematics tech-
niques play a significant role in my job when I search for
evidence contained on computer hard drives and other
forms of media. To obtain evidence, I am required to have
a working knowledge of certain applied mathematics skills
so that I can effectively communicate with the computer
forensic analyst who will be decoding the evidence. To con-
duct an effective investigation, I am also required to under-
stand these data in a wide variety of formats. With this infor-
mation, I can work with the analyst to reconstruct data that
may play a significant roll in determining events that
occurred pertaining to a crime.
During the course of an investigation, I have to look at
the data not only in text but also in code. Using this view,
the analyst can decipher different file types and possible
evidence in unallocated space throughout the hard drive.
This unallocated space can contain deleted files that may
contain potential evidence. The analyst also has to decode
files by hand, and at this point, recognizing patterns among
the files becomes very important. From here, we can derive
an algorithm to define those patterns. By producing an algo-
rithm, it makes it possible to write a program that will
decode the files.
For example, there was a case that involved a suspect
who was receiving files through a mail server. This suspect
was then opening the files and deleting the email. Mem-
bers of my computer forensic laboratory and I viewed these
files in their original code to try to discover any patterns or
inconsistencies within the code to find a solution to the
problem. We did find a clue buried within the code. We
then derived an algorithm defining its pattern. By inputting
the algorithm, we could then extract the files from the
coded data.
Although I do not have a solid background in computer
science or even mathematics, my
knowledge of applied mathematics
helps me understand the procedures
involved in obtaining evidence. Best
of all, I am able to clearly convey my
needs to the forensic analysts in my
department.
Stephanie Molina
TITLE Computer Crimes Detective
INSTITUTION Maricopa County Sheriff’s Office
© Beaconstox/Alamy
87533_06_ch6_p313-352 1/30/08 10:01 AM Page 331