Problem set 6 Taking logarithms gives In(n2!)In(v2rn' In(V2Tn2)+In The first term is tiny compared to the second which we can rewrite as: In =n21n e(nIn n Solution. The expression in parentheses is always at least 1/2 and at most 1. Thus ze have the bounds Since the first expression and the last are both e (n), so is the one in the middle Problem 8. A triangular number is an integer n of the form n=1+2+3+...+k k(k+1) where k is a positive inte (a)Describe a solution to the four-peg Towers of Hanoi puzzle with k(k+1)/2 disks that requires Tk moves, where Solution Move all but the k largest disks to another peg recursively. This requires T(k Move the k largest disks to another peg using the three-peg strategy. This re- 2k-1 Now move all the other disks on top of the k largest disks recursively. This requires T(k-1)moves� � � � � � � � Problem Set 6 7 Taking logarithms gives: 2 2 2 n ln(n !) ∼ ln(√ 2πn2 n ) e 2 2 n = ln(√ 2πn2) + ln n e The first term is tiny compared to the second, which we can rewrite as: 2 2 n 2 n ln = n 2 ln n = Θ(n 2 ln n) e e (e) �n � �1 k 1 − 2k k=1 Solution. The expression in parentheses is always at least 1/2 and at most 1. Thus, we have the bounds: n �n � � n 1 � 1 � k ≤ k k 2 1 − 2k ≤ k=1 k=1 k=1 Since the first expression and the last are both Θ(n2), so is the one in the middle. Problem 8. A triangular number is an integer n of the form k(k + 1) n = 1 + 2 + 3 + . . . + k = 2 where k is a positive integer. (a) Describe a solution to the four­peg Towers of Hanoi puzzle with k(k + 1)/2 disks that requires Tk moves, where: T1 = 1 Tk = 2Tk−1 + 2k − 1 Solution. • Move all but the k largest disks to another peg recursively. This requires T(k − 1) moves. • Move the k largest disks to another peg using the three­peg strategy. This re￾quires 2k − 1 moves. • Now move all the other disks on top of the k largest disks recursively. This requires T(k − 1) moves