Math Riddle?

The Tower of Hanoi puzzle is sold commercially with 7 rings of increasing size.

NUMBERS OF MOVES NEEDED

1 ring: 1 move

2 rings: 3 moves

3 rings: 7 moves

4 rings: 15 moves

5 rings: 31 moves

6 rings: 63 moves

7 rings: 127 moves

n rings: (2^n) -1 moves

METHOD FOR MINIMUM NUMBER OF MOVES

Call the poles A, B and C with all the rings on pole A at the outset and the aim is to transfer them all to Pole B at the conclusion.

The method is as follows:

1 ring: 1 move

A --> B

2 rings: 3 moves

A --> C

A --> B

C --> B

3 rings: 7 moves

A --> B

A --> C

B --> C

A --> B

C --> A

C --> B

A --> B

4 rings: 15 moves

A --> C

A --> B

C --> B

A --> C

B --> A

B --> C

A --> C

A --> B

C --> B

C --> A

B --> A

C --> B

A --> C

A --> B

C --> B

The general principles of how to proceed for n rings can be inferred from the above.

(a) You move (n-1) rings from Pole A to Pole C

(b) You make the only move the largest ring makes from Pole A to Pole B

(c) You move (n-1) rings from Pole C to Pole B

Each solution builds on the method of the previous one, for one less ring.

This is called the 'Tower of Hanoi'.

If you have n rings, you need 2^n - 1 moves to complete them. d:

Edit:

You know that there are 7 moves to transfer 3 rings.

Say you now have 4 rings. Transfer the first 3 rings to the spare pole. [It takes 7 moves.]

Now, transfer the 4th ring to the destination pole. [+1 move]

And, transfer again the 1st 3 rings to the destination pole. [+7 more moves]

The total no of moves is 15. 2^4 - 1 = 15.

The same trick in transferring is also implemented in transferring n rings whenever you know how to transfer (n-1) rings. [2^(n-2) - 1] + 1 + [2^(n-2) - 1] = 2(2^(n-2) - 1) + 1

= 2^(n-1) - 1.