Page 462 - Discrete Mathematics and Its Applications

Supplementary Exercises 441

3. A test contains 100 true/false questions. How many dif- 13. Show that given any set of 10 positive integers not ex-
ferent ways can a student answer the questions on the test, ceeding 50 there exist at least two different five-element
if answers may be left blank? subsets of this set that have the same sum.

4. How many strings of length 10 either start with 000 or 14. A package of baseball cards contains 20 cards. How many
end with 1111? packages must be purchased to ensure that two cards in
these packages are identical if there are a total of 550
5. How many bit strings of length 10 over the alphabet different cards?
{a, b, c} have either exactly three as or exactly four bs?
15. a) How many cards must be chosen from a standard deck
6. The internal telephone numbers in the phone system on a of 52 cards to guarantee that at least two of the four
campus consist of five digits, with the first digit not equal aces are chosen?
to zero. How many different numbers can be assigned in b) How many cards must be chosen from a standard deck
this system?
of 52 cards to guarantee that at least two of the four
7. An ice cream parlor has 28 different flavors, 8 different aces and at least two of the 13 kinds are chosen?
kinds of sauce, and 12 toppings. c) How many cards must be chosen from a standard deck
a) In how many different ways can a dish of three scoops of 52 cards to guarantee that there are at least two cards
of ice cream be made where each flavor can be used of the same kind?
more than once and the order of the scoops does not d) How many cards must be chosen from a standard deck
matter? of 52 cards to guarantee that there are at least two cards
of each of two different kinds?
b) How many different kinds of small sundaes are there
if a small sundae contains one scoop of ice cream, a ∗ 16. Show that in any set of n + 1 positive integers not exceed-
sauce, and a topping? ing 2n there must be two that are relatively prime.
c) How many different kinds of large sundaes are there ∗ 17. Show that in a sequence of m integers there exists one or
if a large sundae contains three scoops of ice cream, more consecutive terms with a sum divisible by m.
where each flavor can be used more than once and
the order of the scoops does not matter; two kinds of 18. Show that if five points are picked in the interior of a
sauce, where each sauce can be used only once and square with a side length of 2, then at least two of these
√
the order of the sauces does not matter; and three top- points are no farther than 2 apart.
pings, where each topping can be used only once and 19. Show that the decimal expansion of a rational number
the order of the toppings does not matter? must repeat itself from some point onward.
8. How many positive integers less than 1000
20. Once a computer worm infects a personal computer via an
a) have exactly three decimal digits? infected e-mail message, it sends a copy of itself to 100 e-
b) have an odd number of decimal digits? mail addresses it finds in the electronic message mailbox
on this personal computer. What is the maximum number
c) have at least one decimal digit equal to 9?
of different computers this one computer can infect in the
d) have no odd decimal digits? time it takes for the infected message to be forwarded five
times?
e) have two consecutive decimal digits equal to 5?
21. How many ways are there to choose a dozen donuts from
f) are palindromes (that is, read the same forward and
backward)? 20 varieties
a) if there are no two donuts of the same variety?
9. When the numbers from 1 to 1000 are written out in deci-
malnotation,howmanyofeachofthesedigitsareused? b) if all donuts are of the same variety?
a) 0 b) 1 c) 2 d) 9 c) if there are no restrictions?
10. There are 12 signs of the zodiac. How many people are d) if there are at least two varieties among the dozen
needed to guarantee that at least six of these people have donuts chosen?
the same sign? e) if there must be at least six blueberry-filled donuts?
11. A fortune cookie company makes 213 different fortunes. f) if there can be no more than six blueberry-filled
A student eats at a restaurant that uses fortunes from this donuts?
company and gives each customer one fortune cookie at 22. Find n if
the end of a meal. What is the largest possible number
a) P(n, 2) = 110. b) P(n, n) = 5040.
of times that the student can eat at the restaurant without
getting the same fortune four times? c) P(n, 4) = 12P(n, 2).
23. Find n if
12. How many people are needed to guarantee that at least a) C(n, 2) = 45. b) C(n, 3) = P(n, 2).
two were born on the same day of the week and in the
same month (perhaps in different years)? c) C(n, 5) = C(n, 2).