Section 4.3 Principle of Inclusion and Exclusion; Pigeonhole Principle
271
Use the principle of inclusion and exclusion to determine how many subscribers have access to all three
types of systems.
12. You are developing a new bath soap, and you hire a public opinion survey group to do some market research for you. The group claims that in its survey of 450 consumers, the following criteria were named
as important factors in purchasing bath soap:
Odor
425
Lathering ease
397
Natural ingredients
340
Odor and lathering ease
284
Odor and natural ingredients
315
Lathering ease and natural ingredients
219
All three factors
147
Should you have confidence in these results? Why or why not?
13. a. How many integers n, 1 ≤ n ≤ 100, are multiples of either 2 or 5?
b. How many integers n, 1 ≤ n ≤ 100, are not multiples of either 2 or 5?
14. How many integers n, 1 ≤ n ≤ 1000, are not multiples of either 3 or 7?
15. a. Write the expression for 0 A c B c C c D 0 from Equation (4).
b. Write an expression for the number of terms in the expansion of 0 A 1 c c c A n 0 given by Equation (4).
16. Patrons of a local bookstore can sign up for advance notification of new book arrivals in genres of interest.
In the first month of this service, 32 sign up for mysteries, 34 for spy novels, 18 for westerns, and 41 for
science fiction. Of these, 17 sign for both mysteries and spy novels, 8 for both mysteries and westerns,
19 for mysteries and science fiction, 5 for spy novels and westerns, 20 for spy novels and science fiction,
and 12 for westerns and science fiction. In addition, 2 sign up for mysteries, spy novels and westerns, 11
for mysteries, spy novels and science fiction, 6 for mysteries, westerns, and science fiction, and 5 for spy
novels, westerns, and science fiction. Finally, 2 people sign up for all four categories. How many people
signed up for service in the first month?
17. How many cards must be drawn from a standard 52-card deck to guarantee 2 cards of the same suit?
18. How many cards must be drawn from a standard 52-card deck to guarantee a black card?
19. If 12 cards are drawn from a standard deck, must at least 2 of them be of the same denomination (type)?
20. How many cards must be drawn from a standard 52-card deck to guarantee 2 queens?
21. A computerized dating service has a list of 50 men and 50 women. Names are selected at random; how
many names must be chosen to guarantee one name of each gender?
22. A computerized housing service has a list of 50 men and 50 women. Names are selected at random; how
many names must be chosen to guarantee two names of the same gender?
23. How many people must be in a group to guarantee that 2 people in the group have the same birthday (don’t
forget leap year)?
24. In a group of 25 people, must there be at least 3 who were born in the same month?
25. Prove that if four numbers are chosen from the set {1, 2, 3, 4, 5, 6}, at least one pair must add up to 7.
(Hint: Find all the pairs of numbers from the set that add to 7.)
26. How many numbers must be selected from the set {2, 4, 6, 8, 10, 12, 14, 16, 18, 20} to guarantee that at
least one pair adds up to 22? (See the hint for Exercise 25).
27. Let n be a positive number. Show that in any set of n + 1 numbers, there are at least two with the same
remainder when divided by n.
271
Use the principle of inclusion and exclusion to determine how many subscribers have access to all three
types of systems.
12. You are developing a new bath soap, and you hire a public opinion survey group to do some market research for you. The group claims that in its survey of 450 consumers, the following criteria were named
as important factors in purchasing bath soap:
Odor
425
Lathering ease
397
Natural ingredients
340
Odor and lathering ease
284
Odor and natural ingredients
315
Lathering ease and natural ingredients
219
All three factors
147
Should you have confidence in these results? Why or why not?
13. a. How many integers n, 1 ≤ n ≤ 100, are multiples of either 2 or 5?
b. How many integers n, 1 ≤ n ≤ 100, are not multiples of either 2 or 5?
14. How many integers n, 1 ≤ n ≤ 1000, are not multiples of either 3 or 7?
15. a. Write the expression for 0 A c B c C c D 0 from Equation (4).
b. Write an expression for the number of terms in the expansion of 0 A 1 c c c A n 0 given by Equation (4).
16. Patrons of a local bookstore can sign up for advance notification of new book arrivals in genres of interest.
In the first month of this service, 32 sign up for mysteries, 34 for spy novels, 18 for westerns, and 41 for
science fiction. Of these, 17 sign for both mysteries and spy novels, 8 for both mysteries and westerns,
19 for mysteries and science fiction, 5 for spy novels and westerns, 20 for spy novels and science fiction,
and 12 for westerns and science fiction. In addition, 2 sign up for mysteries, spy novels and westerns, 11
for mysteries, spy novels and science fiction, 6 for mysteries, westerns, and science fiction, and 5 for spy
novels, westerns, and science fiction. Finally, 2 people sign up for all four categories. How many people
signed up for service in the first month?
17. How many cards must be drawn from a standard 52-card deck to guarantee 2 cards of the same suit?
18. How many cards must be drawn from a standard 52-card deck to guarantee a black card?
19. If 12 cards are drawn from a standard deck, must at least 2 of them be of the same denomination (type)?
20. How many cards must be drawn from a standard 52-card deck to guarantee 2 queens?
21. A computerized dating service has a list of 50 men and 50 women. Names are selected at random; how
many names must be chosen to guarantee one name of each gender?
22. A computerized housing service has a list of 50 men and 50 women. Names are selected at random; how
many names must be chosen to guarantee two names of the same gender?
23. How many people must be in a group to guarantee that 2 people in the group have the same birthday (don’t
forget leap year)?
24. In a group of 25 people, must there be at least 3 who were born in the same month?
25. Prove that if four numbers are chosen from the set {1, 2, 3, 4, 5, 6}, at least one pair must add up to 7.
(Hint: Find all the pairs of numbers from the set that add to 7.)
26. How many numbers must be selected from the set {2, 4, 6, 8, 10, 12, 14, 16, 18, 20} to guarantee that at
least one pair adds up to 22? (See the hint for Exercise 25).
27. Let n be a positive number. Show that in any set of n + 1 numbers, there are at least two with the same
remainder when divided by n.