MathNovatory/Applied Maths/Game Maths/Brahma


The Tower of Hanoi

Number of Disk Moves
Where "n" represents the number of disks in the Tower, the minimum number of moves required to move the Tower is 2n - 1, a frequently seen formula.

Disk Moves From The Top
The top disk moves every 2nd turn, 2n-1 times. The second from the top moves every 4th turn, 2n-2 times. The third from the top moves every 8th turn, 2n-3 times, and so on. The disk at the bottom moves only once.

Disk Moves From The Bottom
Counting now from the bottom, each odd-numbered disk always moves counter-clockwise, and each even-numbered disk always moves clockwise.

How They Sit
Each odd-numbered disk always sits on an even-numbered disk, and each even-numbered disk always sits on an odd-numbered disk. The odd-numbered disks never touch each other, nor do the even-numbered disks.

The Ternary Structure Of The Board
Following the moves of each disk, starting with Disk #10 on the bottom, will allow us to see more clearly the number of times a disk goes completely around the triangle of the pegs (3 moves), with "A" indicating the anticlockwise direction and "C" denoting the clockwise direction.
#10 - A1 = 1 move
#9 - C2 = 2 moves
#8 - A1 + 1x3 = 4 moves
#7 - C2 + 2x3 = 8 moves
#6 - A1 + 1x3 + 4x3 = 16 moves
#5 - C2 + 2x3 + 8X3 = 32 moves
#4 - A1 + 1x3 + 4x3 + 16x3 = 64 moves
#3 - C2 + 2x3 + 8X3 + 32x3 = 128 moves
#2 - A1 + 1x3 + 4x3 + 16x3 + 64x3 = 256 moves
#1 - C2 + 2x3 + 8X3 + 32x3 + 128x3 = 512 moves
for a total of 1023 moves (1024 - 1)

The Little Waltz
The ternary structure of the board also creates an interesting blend with the binary movements. In a pile of disk 1 over disk 2, two moves of disk 1, in one direction, will bring it to the same position as one move of disk 2, in the other direction, creating a ternary whole. This is how the pile of 2 is moved : disk 1 gets off (in its direction) ; disk 2 is free to move (in its opposite direction) ; disk 1 gets back on. An "empty" (for disks 1 and 2) beat will be added to square out the binary rhythm and to allow a larger disk to move in its turn.

waltz1-4

Clockwork
In a pile of 4 disks, the movement of each disk is represented by a horizontal bar -
     disk 1 is on top with 8 black bars, then disk 2 with 4 red bars, disk 3 with 2 black bars, disk 4 with 1 red bar.
(a) Disks 1 and 2 dance their little 3-move waltz (disk 1 gets off, disk 2 is free to move, disk 1 gets back on),
     indicated by a red saucer-shaped semi-hexagon which occurs four times.
(b) Disks 2 and 3 dance their little 3-move waltz (disk 2 gets off, disk 3 is free to move, disk 2 gets back on),
     indicated by a black saucer-shaped semi-hexagon which occurs twice.
(c) Disks 3 and 4 dance their little 3-move waltz (disk 3 gets off, disk 4 is free to move, disk 3 gets back on),
     indicated by a red saucer-shaped semi-hexagon which occurs only once.
A magnificent example of the law of HIERARCHY which tightly holds the entire process together.