282 views
0 votes
0 votes

In the Tower of Hanoi puzzle, suppose our goal is to transfer all $n$ disks from peg $1$ to peg $3,$ but we cannot move a disk directly between pegs $1$ and $3.$ Each move of a disk must be a move involving peg $2.$ As usual, we cannot place a disk on top of a smaller disk.

  1. Find a recurrence relation for the number of moves required to solve the puzzle for n disks with this added restriction.
  2. Solve this recurrence relation to find a formula for the number of moves required to solve the puzzle for n disks.
  3. How many different arrangements are there of the n disks on three pegs so that no disk is on top of a smaller disk?
  4. Show that every allowable arrangement of the n disks occurs in the solution of this variation of the puzzle.

Please log in or register to answer this question.

Related questions