The Tower Of Hanoi Puzzle

Published On :2021-05-08 00:24:00

Post Image

 The Tower Of Hanoi Puzzle (Nineteen Century)

There are 3 pegs . Initially the first peg has n disks that are placed in order of size.

Rule: Allow disks to be moved one at a time from one peg to another as long as a disk is never placed on top of a smaller one.

Goal: Move all disks to the other pegs.

Example: 


Let Hn denotes the number of moves needed to solve the Tower of Hanoi puzzle. 

Transfer the top n-1 disks. This can be done in Hn-1 steps. Transfer the largest disk (one step). Then transfer the (n-1) pegs on the largest disk (This can be 

done in Hn-1ways).


Thus  

begin{array}{l} {H_n} = 2{H_{n - 1}} + 1;,;;;;;;;;;Initial;Condition;{H_1} = 1\\ {H_n} = 2{H_{n - 1}} + 1;,;;;;;;;{H_1} = 1\\ {H_n} = 2left( {2{H_{n - 2}} + 1} right) + 1 = {2^2}{H_{n - 2}} + 2 + 1\\ {H_n} = {2^2}(2{H_{n - 3}} + 1) + 2 + 1 = {2^3}{H_{n - 3}} + {2^2} + 2 + 1\\ {H_n} = {2^3}{H_{n - 3}} + {2^2} + 2 + 1\ .\ .\ .\ {H_n} = {2^{n - 1}}{H_1} + {2^{n - 2}} + ldots + 2 + 1\\ {H_n} = {2^{n - 1}} + {2^{n - 2}} + ldots + 2 + 1 = {2^n} - 1\\ (Geometric;;Sum;;1 + p + {p^2} + ... + {p^{(n - 1)}} = ({p^n} - 1)/(p - 1))\ end{array}

“ Monks want to transfer 64 gold disks from one peg to another according to rules of Hanoi Puzzle”

They need to perform 264-1 Steps we need about 500 billion years (If 1 move take a Second).