Recurrence 1.2 : The Tower of Brahma

The Tower of Hanoi, the ideation around applying recurrence and solving the recurrence relation has been analyzed in depth in my previous post :

https://lnkd.in/gynGfHmd

The solution to the recurrence relation which helps us calculate the number of moves T(n) for moving n disks is :
T(n) = 2^n - 1 { n >= 0 }

French mathematician Edouard Lucas who proposed the Tower of Hanoi puzzle for 8 disks furnished this puzzle with a legend about a much larger Tower of Brahma which consisted of 64 disks of pure gold resting on 3 diamond needles. According to this legend, when time started God placed these 64 disks on one of the needle and tasked a group of priests to transfer the 64 disks to the third needle in accordance with the constraints that follow the same nature as the Tower of Hanoi puzzle. The legend mentions that when the task of the priests is completed, the Tower will crumble and the world will end.

The priests are still moving the disks because if we substitute n = 64 in the solution , the total number of moves is equal to 2^64 - 1 moves which is roughly 18 quintillion.

Even if the priests make 1 move in 1 microsecond, they will need more than 5000 centuries to transfer the Tower of Brahma. 😁

#recurrence #recursion #mathematics #towerofhanoi #discretemath #algorithms #softwareengineering #mythology #towerofbrahma

Recurrence 1.1 : The Tower of Hanoi

Problem Statement:

We are given a tower of eight disks which are arranged in decreasing size on one of the 3 pegs as shown below. The aim is to transfer the entire tower to one of the other pegs and identify the number of moves required for this movement. The puzzle is constrained around the fact that we need to make sure: 

• Only one disk can be moved at a time.
• Never should a larger disk be moved on top of a smaller one.

Smaller sub-problems:

Let us scale down the problem size from 8 disks. We will consider 0, 1 and 2 disks as our sub-problems.

• n = 0 then number of moves required = 0 (no disk)
• n = 1 then number of moves required = 1 (directly move to the destination peg)
• n = 2, number of moves required = 3
• Move the top most disk to the non destination peg.
• Move the bottom disk to the destination peg. 
•  Move the disk from non destination peg to the destination peg which will make sure the entire tower of 2 disks has been moved to the destination peg obeying our constraints.

Generalization and Recurrence relation:

Let us consider that moving n disks to the destination peg will require a minimum of T(n) moves. So, we have T(0) = 0; T(1) = 1 and T(2) = 3 based on our inspection of the smaller cases. 

By applying the perspective that we have gained to these smaller problems and based on the solution for T(2) = 3 we can state that for transferring n disks in general : 

• We first transfer the top (n - 1 disks onto the non destination peg (which requires T(n - 1) moves).
• We then transfer the largest disk at the bottom to the destination peg requiring 1 move.
• We then move all the n-1 disks to the destination peg (which requires another T(n-1) moves).

 

Above generalization leads to following recurrence relations for n disks:

    T(n) = 0  { n = 0 };

    T(n) = 2*T(n-1) + 1 { n > 0 }

Solving the recurrence:

The recurrence relation above allows us to compute the number of moves required T(n) for moving n disks. The solution to the above recurrence would help us instantaneously calculate number of moves required for large values of n.

So, we compute successively as follows : 

T(0) = 0; 

T(1) = 2 * T(0) + 1 = 1 ; 

T(2) = 2 * T(1) + 1 = 2 * 1 + 1 = 3; 

T(3) = 2 * T(2) + 1 = 2 * 3 + 1 = 7;

T(4) = 2 * T(3) + 1 = 2 * 7 + 1 = 15;

T(5) = 2 * T(4) + 1 = 2 * 15 + 1 = 31 and so on ........

The solution to our recurrence seems to be :

T(n) = 2^n - 1 { n >= 0 }

Thus, for n = 8, we will require 2^8 - 1 = 255 moves. 

If we consider that each move takes 1 second then the total time to make 255 moves is equal to 255 seconds which around 4 minutes.