(Solved): 9. There is a famous puzzle called the Tower of Hanoi, which is constructed using 3 pegs, and \( D ...

9. There is a famous puzzle called the Tower of Hanoi, which is constructed using 3 pegs, and \( D \) discs, all of which have different sizes. The puzzle begins with all of the discs on the leftmost peg, with the largest disc on the bottom, then the second largest above that, and so forth. The goal of the puzzle is to move all discs to the rightmost peg, while only moving one disc at a time. The challenge is that you are not able to place a larger disc on top of a smaller disc. The puzzle for \( D=5 \) is shown below. Prove by induction that if you are given any number \( D \) discs, you can solve the puzzle by making \( 2^{D}-1 \) moves. 10. Given any \( n \geq 1 \), it is always possible to break cut an equilateral triangle into \( 4^{n} \) smaller equilateral triangles. The case for \( n=2 \) is shown below. Prove by induction that if one of the small triangles in the corner is excluded (like shown above), you can tile the triangle for any \( n \) using trapezoidal tiles that look like below. Hint: Remember the tiling problem from lecture/discussion!