| Math Logic |
|
|
| Question : |
|
What is 'Tower of Hanoi' in arithmetic ? |
Answer : |
|
Tower of Hanoi is an Arithmetical puzzle brought out by M.Claus in 1883. |
|
Problem: |
 |
|
There are three pegs fastened to a stand, consisting of eight circular discs of wood, each of which has a hole in the
middle through which a peg can be passed. These discs are of different radii, and initially they are placed all on one
peg, so that the biggest is at the bottom, and the radii of the successive discs decrease as we ascend : thus the smallest
disc is at the top. This arrangement is called the Tower. The problem is to shift the discs from one peg to another in
such a way that a disc shall never rest on one smaller than itself, and finally rested to one of the other pegs. |
|
Solutions : |
|
1. Recursive solution |
|
The following is a procedure for moving a tower of h disks from a peg1 onto a peg2, with peg3 : |
- If h>1 then move the h-1 smaller disks from peg1 to peg3.
- Now the disk h-1 can be moved from peg1 to peg2.
- If h>1 then again use this procedure to move the h-1 smaller disks from peg3 to peg2.
|
| 2. Non-recursive
solution |
|
The following is a procedure for moving a tower of h disks from a peg1 onto a peg2, with peg3 in alternative moves: |
- Move the smallest disk to the peg it has not recently come from.
- Move another disk
|
|
If the number of disks is even then, |
- Move disk 0 from peg1 to peg3 ignoring peg2.
- Move disk 1 from peg1 to peg2 ignoring peg3.
- Move disk 0 from peg3 to peg2 ignoring peg1.
- Move disk 2 from peg1 to peg3 ignoring peg2.
- Move disk 0 from peg2 to peg1 ignoring peg3.
- Move disk 1 from peg2 to peg3 ignoring peg1.
- Move disk 0 from peg1 to peg3 ignoring peg2.
- Move disk 3 from peg1 to peg2 ignoring peg3.
- Move disk 0 from peg3 to peg2 ignoring peg1.
- Move disk 1 from peg3 to peg1 ignoring peg2.
- Move disk 0 from peg2 to peg1 ignoring peg3.
- Move disk 2 from peg3 to peg2 ignoring peg1.
- Move disk 0 from peg1 to peg3 ignoring peg2.
- Move disk 1 from peg1 to peg2 ignoring peg3.
- Move disk 0 from peg3 to peg2 ignoring peg1.
- Move disk 4 from peg1 to peg3 ignoring peg2.
etc..
|
|
Also observe that, |
- Disks whose ordinals have even parity move in the same sense as the smallest disk.
- Disks whose ordinals have odd parity move in opposite sense.
- If h is even, the peg3 during successive moves is 2, 3, 1, 2, 3, 1, etc.
- If h is odd, the peg3 during successive moves is 3, 2, 1, 3, 2, 1, etc.
|
|
The Tower of Hanoi is frequently used in psychological research on problem solving.
It can also be used as Backup rotation scheme when performing computer data backups where multiple tapes
or media are involved. |
