Final Exam Review .MarkE

Final Exam Review 

Section 11.2 # 6

6. Howmany weighings of a balance scale are needed to find a lighter counterfeit coin among four coins? Describe an algorithm to find the lighter coin using this number of weighings.

Section 11.2 #8

∗8. How many weighings of a balance scale are needed to find a counterfeit coin among eight coins if the counterfeit coin is either heavier or lighter than the others?

Describe an algorithm to find the counterfeit coin using this number of weighings.

Section 11.2 # 12

∗12. Find the least number of comparisons needed to sort five elements and devise an algorithm that sorts these elements using this number of comparisons.

11.2 # 38 Suppose that the first four moves of a tic-tac-toe game are as shown. Does the first player

(whose moves are marked by Xs) have a strategy that will always win?

 

 

 

 

Section 8.1 #2a

Find a recurrence relation for the number of permutations of a set with n elements.

 

Section 8.1 #8

1. Find a recurrence relation for the number of bit strings of length n that contain three consecutive 0s.

 

1. What are the initial conditions?

 

1. c) How many bit strings of length seven contain three consecutive 0s?

 

Section 8.1 #14

1. Find a recurrence relation for the number of ternary strings of length n that contain two consecutive 0’s.

 

1. What are the initial conditions?

 

1. c) How many ternary strings of length six contain two consecutive 0s?

 

 

Section 8.1 #28

Show that the Fibonacci numbers satisfy the

recurrence relation f_n = 5f_n−4 + 3f_n−5 for n = 5, 6, 7, . . . , together with the initial conditions f₀ = 0, f₁ = 1, f₂ = 1, f₃ = 2, and f₄ = 3 Use this recurrence relation to show that f_5n is divisible by 5, for n = 1, 2, 3, . . . .

 

Section 8.2 #8

A model for the number of lobsters caught per year is based on the assumption that the number of lobsters caught in a year is the average of the number caught in the two previous years.

1. a) Find a recurrence relation for {L_n}, where L_n is the number of lobsters caught in year n, under the assumption for this model.

 

2. b) Find L_n if 100,000 lobsters were caught in year 1 and 300,000 were caught in year 2.

 

8.3 #14. Suppose that there are n = 2^k teams in an elimination tournament, where there are n/2 games in the first round, with the n/2 = 2^k−1 winners playing in the second round, and so on. Develop a recurrence relation for the number of rounds in the tournament.

If there is only one team, then no rounds are needed, so the base case is R(l) = 0. Since it takes one round to cut the number of teams in half, we have R(n) = 1 + R(n/2).

8.3 #15.  How many rounds are in the elimination tournament described in Exercise 14 when there are 32 teams?

8.3 #16. Solve the recurrence relation for the number of rounds in the tournament described in Exercise 14.

8.4 #2. Find the generating function for the finite sequence 1, 4, 16, 64, 256.

5.1 #6  Prove that 1 · 1! + 2 · 2!+· · ·+n · n! = (n + 1)! – 1 whenever n is a positive integer.

 

5.1 #18 Let P(n) be the statement that n! < nⁿ, where n is an integer greater than 1.

1. a) What is the statement P(2)?
2. b) Show that P(2) is true, completing the basis step of the proof.
3. c) What is the inductive hypothesis?
4. d) What do you need to prove in the inductive step?

5.1 #18

1. e) Complete the inductive step.

f ) Explain why these steps show that this inequality is true whenever n is an

integer greater than 1.

 

5.2 #4 Let P(n) be the statement that a postage of n cents can be formed using just 4-cent stamps and 7-cent stamps. The parts of this exercise outline a strong induction proof that P(n) is true for n ≥ 18.

1. a) Show statements P(18), P(19), P(20), and P(21) are true, completing the basis step of the proof.
2. b) What is the inductive hypothesis of the proof?

 

 

1. c) What do you need to prove in the inductive step?
2. d) Complete the inductive step for k ≥ 21.
3. e) Explain why these steps show that this statement is true whenever n ≥ 18.

5.2 #12 Use strong induction to show that every positive integer n can be

written as a sum of distinct powers of two, that is, as a sum of a subset of the integers 2⁰ =1, 2¹ =2, 2² =4, and so on. [Hint: For the inductive step, separately consider the case where k + 1 is even and where it is odd. When it is even, note that (k + 1)/2 is an integer.]