(Tower of Hanoi) There are discs of distinct sizes stacked on peg in increasing order of size (largest at the bottom), and two empty pegs and . A move consists of transferring the top disc from one peg to another, and at no time may a larger disc be placed on a smaller disc.
Prove that: (a) it is possible to move the entire stack from to (say) ; (b) the task can be completed in exactly moves.
Sign in or create an account to reveal answers, view the solution, and save your progress. Create a free account to unlock practice and keep track of your work.
One puzzle per day. Cryptarithm, Magic Square, Summit. No sign-up required to play.
Play daily puzzle →Interactive problems and curated lessons—water pouring, magic squares, knight's tour, and more.
Browse library →See how you rank. Top solvers by problems solved correctly. Sign in to climb the ranks.
View leaderboard →