Page 533 - Discrete Mathematics and Its Applications

512 8 / Advanced Counting Techniques

26. a) Find a recurrence relation for the number of ways to a) Find a recurrence relation for the number of moves re-
completely cover a 2 × n checkerboard with 1 × 2 quired to solve the puzzle for n disks with this added
dominoes. [Hint: Consider separately the coverings restriction.
where the position in the top right corner of the b) Solve this recurrence relation to find a formula for the
checkerboard is covered by a domino positioned hor- number of moves required to solve the puzzle for n
izontally and where it is covered by a domino posi- disks.
tioned vertically.] c) How many different arrangements are there of the n
b) What are the initial conditions for the recurrence re- disks on three pegs so that no disk is on top of a smaller
lation in part (a)? disk?
c) How many ways are there to completely cover a d) Show that every allowable arrangement of the n disks
2 × 17 checkerboard with 1 × 2 dominoes? occurs in the solution of this variation of the puzzle.
27. a) Find a recurrence relation for the number of ways to
lay out a walkway with slate tiles if the tiles are red, Exercises 33–37 deal with a variation of the Josephus
green, or gray, so that no two red tiles are adjacent and problem described by Graham, Knuth, and Patashnik in
tiles of the same color are considered indistinguish- [GrKnPa94]. This problem is based on an account by the his-
able. torian Flavius Josephus, who was part of a band of 41 Jewish
b) What are the initial conditions for the recurrence re- rebels trapped in a cave by the Romans during the Jewish-
lation in part (a)? Roman war of the first century. The rebels preferred suicide
to capture; they decided to form a circle and to repeatedly
c) How many ways are there to lay out a path of seven
tiles as described in part (a)? count off around the circle, killing every third rebel left alive.
However, Josephus and another rebel did not want to be killed
28. Show that the Fibonacci numbers satisfy the recurrence this way; they determined the positions where they should
relation f n = 5f n−4 + 3f n−5 for n = 5, 6, 7,..., to- stand to be the last two rebels remaining alive. The variation
gether with the initial conditions f 0 = 0, f 1 = 1, f 2 = 1, we consider begins with n people, numbered 1 to n, stand-
f 3 = 2, and f 4 = 3. Use this recurrence relation to show ing around a circle. In each stage, every second person still
that f 5n is divisible by 5, for n = 1, 2, 3,... .
left alive is eliminated until only one survives. We denote the
∗ 29. Let S(m, n) denote the number of onto functions from number of the survivor by J(n).
a set with m elements to a set with n elements. Show 33. Determine the value of J(n) for each integer n with
that S(m, n) satisfies the recurrence relation 1 ≤ n ≤ 16.
34. Use the values you found in Exercise 33 to conjecture a
n−1 m
m formula for J(n).[Hint: Write n = 2 + k, where m is
S(m, n) = n − C(n, k)S(m, k)
a nonnegative integer and k is a nonnegative integer less
m
k=1 than 2 .]
35. Show that J(n) satisfies the recurrence relation J(2n) =
whenever m ≥ n and n> 1, with the initial condition 2J(n) − 1 and J(2n + 1) = 2J(n) + 1, for n ≥ 1, and
S(m, 1) = 1.
J(1) = 1.
30. a) Write out all the ways the product x 0 · x 1 · x 2 · x 3 · x 4
36. Use mathematical induction to prove the formula you
can be parenthesized to determine the order of multi-
conjectured in Exercise 34, making use of the recurrence
plication.
relation from Exercise 35.
b) Use the recurrence relation developed in Example 5 37. Determine J(100), J(1000), and J(10,000) from your
to calculate C 4 , the number of ways to parenthesize formula for J(n).
the product of five numbers so as to determine the or-
der of multiplication.Verify that you listed the correct Exercises 38–45 involve the Reve’s puzzle, the variation of
number of ways in part (a). the Tower of Hanoi puzzle with four pegs and n disks. Before
presenting these exercises, we describe the Frame–Stewart al-
c) Check your result in part (b) by finding C 4 , using the
gorithm for moving the disks from peg 1 to peg 4 so that no
closed formula for C n mentioned in the solution of
disk is ever on top of a smaller one. This algorithm, given
Example 5.
the number of disks n as input, depends on a choice of an
31. a) Use the recurrence relation developed in Example 5 to integer k with 1 ≤ k ≤ n. When there is only one disk, move
determine C 5 , the number of ways to parenthesize the it from peg 1 to peg 4 and stop. For n> 1, the algorithm pro-
product of six numbers so as to determine the order ceeds recursively, using these three steps. Recursively move
of multiplication. the stack of the n − k smallest disks from peg 1 to peg 2,
b) Check your result with the closed formula for C 5 men- using all four pegs. Next move the stack of the k largest
tioned in the solution of Example 5. disks from peg 1 to peg 4, using the three-peg algorithm from
∗ 32. In theTower of Hanoi puzzle, suppose our goal is to trans- the Tower of Hanoi puzzle without using the peg holding
fer all n disks from peg 1 to peg 3, but we cannot move a the n − k smallest disks. Finally, recursively move the
disk directly between pegs 1 and 3. Each move of a disk smallest n − k disks to peg 4, using all four pegs. Frame
must be a move involving peg 2. As usual, we cannot and Stewart showed that to produce the fewest moves using
place a disk on top of a smaller disk. their algorithm, k should be chosen to be the smallest integer