Tower of Hanoi with a twist
I hope you are familiar with the
Tower of Hanoi
. In this modified version, you have to move all the disks from peg 1 to peg 3 with one constraint. You cannot transfer a disk directly from peg 1 to peg 3 or vice versa. In other words all moves must either begin or end in peg 2.
In this modified version it take 2 moves to move one disk from peg 1 to peg 3 and 8 moves for 2 disks.
What are the last three digits of the minimum number of moves required to solve this modified version of the Tower of Hanoi with 12 disks?
Image Credit: Wikimedia .
The answer is 440.
This section requires Javascript.
You are seeing this because something didn't load right. We suggest you, (a) try
refreshing the page, (b) enabling javascript if it is disabled on your browser and,
finally, (c)
loading the
non-javascript version of this page
. We're sorry about the hassle.
1 solution
I will give a brief sketch of the solution. In the original version, the recursion is moving n − 1 disks from peg 1 to peg 2, then moving the n t h disk from peg 1 to peg 3, finally moving the n − 1 disks from peg 2 to peg 3.
In this modified version we move the n − 1 disks from peg 1 to peg 3 ( T ( n − 1 ) moves). Then move the n t h disk from peg 1 to peg 2 (1 move). After that move the n − 1 disks from peg 3 to peg 1 ( T ( n − 1 ) moves). Now move the n t h disk to the peg 3 from peg 2 (1 move). Finally move the remaining n − 1 disks from peg 1 to peg 3 ( T ( n − 1 ) moves).
This gives the recurrence relation,
T ( n ) = 3 T ( n − 1 ) + 2
It can be easily seen that the solution for this recurrence is 3 n − 1 .