Page 588 - Discrete Mathematics and Its Applications

Supplementary Exercises 567

b) How many ways are there to assign seven jobs to three 16. a) Define a derangement.
employees so that each employee is assigned at least b) Why is counting the number of ways a hatcheck per-
one job? son can return hats to n people, so that no one receives
the correct hat, the same as counting the number of
15. Explain how the inclusion–exclusion principle can be derangements of n objects?
used to count the number of primes not exceeding the c) Explain how to count the number of derangements of
positive integer n. n objects.

Supplementary Exercises

1. A group of 10 people begin a chain letter, with each per- for transmittal, and the other signal requires 3 microsec-
son sending the letter to four other people. Each of these onds for transmittal. Each signal of a message is followed
people sends the letter to four additional people. immediately by the next signal.
a) Find a recurrence relation for the number of letters a) Find a recurrence relation for the number of different
sent at the nth stage of this chain letter, if no person signals that can be sent in n microseconds.
ever receives more than one letter. b) What are the initial conditions of the recurrence rela-
b) What are the initial conditions for the recurrence rela- tion in part (a)?
tion in part (a)? c) How many different messages can be sent in 12 mi-
c) How many letters are sent at the nth stage of the chain croseconds?
letter? 6. A small post office has only 4-cent stamps, 6-cent
stamps, and 10-cent stamps. Find a recurrence relation
2. A nuclear reactor has created 18 grams of a particular
radioactive isotope. Every hour 1% of this radioactive for the number of ways to form postage of n cents with
isotope decays. these stamps if the order that the stamps are used mat-
ters. What are the initial conditions for this recurrence
a) Set up a recurrence relation for the amount of this
relation?
isotope left n hours after its creation.
7. How many ways are there to form these postages using
b) What are the initial conditions for the recurrence rela- the rules described in Exercise 6?
tion in part (a)?
a) 12 cents b) 14 cents
c) Solve this recurrence relation.
c) 18 cents d) 22 cents
3. Every hour the U.S. government prints 10,000 more $1 8. Find the solutions of the simultaneous system of recur-
bills, 4000 more $5 bills, 3000 more $10 bills, 2500 more rence relations
$20 bills, 1000 more $50 bills, and the same number of
$100 bills as it did the previous hour. In the initial hour a n = a n−1 + b n−1
1000 of each bill were produced. b n = a n−1 − b n−1
a) Set up a recurrence relation for the amount of money
with a 0 = 1 and b 0 = 2.
produced in the nth hour.
2
9. Solve the recurrence relation a n = a n−1 /a n−2 if a 0 = 1
b) What are the initial conditions for the recurrence rela- and a 1 = 2. [Hint: Take logarithms of both sides to
tion in part (a)?
obtain a recurrence relation for the sequence log a n ,
c) Solve the recurrence relation for the amount of money n = 0, 1, 2,.... ]
produced in the nth hour. ∗ 10. Solve the recurrence relation a n = a 3 a 2 if a 0 = 2
n−1 n−2
d) Set up a recurrence relation for the total amount of and a 1 = 2. (See the hint for Exercise 9.)
money produced in the first n hours.
11. Find the solution of the recurrence relation a n =
e) Solve the recurrence relation for the total amount of
3a n−1 − 3a n−2 + a n−3 + 1if a 0 = 2, a 1 = 4, and a 2 =
money produced in the first n hours. 8.
4. Suppose that every hour there are two new bacteria in a
12. Find the solution of the recurrence relation a n
colony for each bacterium that was present the previous = 3a n−1 − 3a n−2 + a n−3 if a 0 = 2, a 1 = 2, and a 2 = 4.
hour, and that all bacteria 2 hours old die. The colony
∗ 13. Suppose that in Example 1 of Section 8.1 a pair of rabbits
starts with 100 new bacteria.
leaves the island after reproducing twice. Find a recur-
a) Set up a recurrence relation for the number of bacteria rence relation for the number of rabbits on the island in
present after n hours.
the middle of the nth month.
b) What is the solution of this recurrence relation? ∗ 14. In this exercise we construct a dynamic programming al-
c) When will the colony contain more than 1 million bac- gorithm for solving the problem of finding a subset S
teria? of items chosen from a set of n items where item i has
5. Messages are sent over a communications channel using a weight w i , which is a positive integer, so that the to-
two different signals. One signal requires 2 microseconds tal weight of the items in S is a maximum but does not