CSE 215 Lecture 16: Mathematical Induction
28 Mar 2017
School
Department
Course
Professor
Document Summary
Move disks from pole a to c, one at a time. Ensure that a bigger disk is never above a smaller disk. No matter how you move disks, you have to go through the position below. This is because we have to move the largest disk to c and we cannot move a larger disk on top of a smaller disk. The common problem to solve with this problem is to move it the most efficient way. We know that the bottom disk is not needed in the transfer besides just moving from a to c. Let mk = minimum number of moves needed to move k disks from one pole to another. Note that mk is independent of the starting and ending poles. Then, mk = mk-1 + 1 + mk-1 = 2mk-1 + 1. Mk-1 as shown twice in the equation above stands for the optimal number of moves to move the disks over each peg.
