Tower of Hanoi : Part 1 of 3

For those who really don't know what is the Tower of Hanoi, you are suggested to read from here.

If you know what is the Tower of Hanoi, this series of posts is going to prove the formula of the least number of steps required to finish an n-disk Tower of Hanoi puzzle WITHOUT USING INDUCTION (I will explain why.).

What is the Tower of Hanoi?

It is a mathematical puzzle that perfectly demonstrates induction and recursion.

It consists of 3 rods and several disks with different diameters which can slide into every rod.

let's name the rods rodA, rodB, rodC.

The set up of the puzzle is to stack all the disks in rodA, with the largest disk at the bottom, such that no disk with a larger diameter is above a disk with a shorter diameter, i.e. bottom to top, largest to shortest.

The goal of the puzzle is to

move all the disk from RodA to RodC (or RodB, both are "topologically" the same.) by obeying the following rules:

(1) you are only allowed to move only 1 disk from a rod to a different one at once, and this will be considered as a step

(2) no disk with a larger diameter can appear above a disk with a shorter diameter.

Get 3 Coins, or anything legit ~

Let's start with something simple, let's start with a 2-disk Tower of Hanoi:

[1,2][][] //each [] is a rod, the element in the [] is listed from top to bottom (on the rod), left to right (in written form)

So the steps required to solve that would be something like:

[1,2][_,_][_,_]
[_,2][_,1][_,_]
[_,_][_,1][_,2]
[_,_][_,_][1,2]

Now add a new disk and go give it a try.

Did you notice something interesting here?

Didn't get it ? You somehow did a puzzle of 2disk twice during the process.

state 0 : [1,2,3][_,_,_][_,_,_]
state 1 : [_,2,3][_,_,_][_,_,1]
state 2 : [_,_,3][_,_,2][_,_,1]
state 3 : [_,_,3][_,1,2][_,_,_]
state 4 : [_,_,_][_,1,2][_,_,3]
state 5 : [_,_,1][_,_,2][_,_,3]
state 6 : [_,_,1][_,_,_][_,2,3]
state 7 : [_,_,_][_,_,_][1,2,3]

you moved the 2disc tower from rodA to rodB, and then from rodB to rodC.

we can get another disk (or maybe another bigger coin if that is what you are using or anything which is legit) and see that the 4disc puzzle also contains two 3disc puzzles which each of them contains two 2disc puzzles.

state 00 : [1,2,3,4][_,_,_,_][_,_,_,_] ┐        ┐
state 00 : [_,2,3,4][_,_,_,1][_,_,_,_] │ 3disk  │ 2disk
state 00 : [_,_,3,4][_,_,_,1][_,_,_,2] │ A to B │ A to C
state 00 : [_,_,3,4][_,_,_,_][_,_,1,2] │        ┘
state 00 : [_,_,_,4][_,_,_,3][_,_,1,2] │        ┐
state 00 : [_,_,1,4][_,_,_,3][_,_,_,2] │        │ 2disk
state 00 : [_,_,1,4][_,_,2,3][_,_,_,_] │        │ C to B
state 00 : [_,_,_,4][_,1,2,3][_,_,_,_] ┘        ┘
state 00 : [_,_,_,_][_,1,2,3][_,_,_,4] ┐        ┐
state 00 : [_,_,_,_][_,_,2,3][_,_,1,4] │ 3disk  │ 2disk
state 00 : [_,_,_,2][_,_,_,3][_,_,1,4] │ B to C │ B to A
state 00 : [_,_,1,2][_,_,_,3][_,_,_,4] │        ┘
state 00 : [_,_,1,2][_,_,_,_][_,_,3,4] │        ┐
state 00 : [_,_,_,2][_,_,_,1][_,_,3,4] │        │ 2disk
state 00 : [_,_,_,_][_,_,_,1][_,2,3,4] │        │ A to C
state 00 : [_,_,_,_][_,_,_,_][1,2,3,4] ┘        ┘

we will start proving the formula in Part 2.