Towers of Hanoi Adventure

The Towers of Hanoi and Adventures in Mathematics
(page 1010(2))

So How Many Moves Will the Monks Have to Make?

So we now know that the number of moves required to complete a Towers of Hanoi puzzle of N rings is 2^N - 1, the monks who are working on a tower of 64 rings are going to take:

	2⁶⁴ - 1

which equals:

	18,446,744,073,709,551,615

So What About a Tower of Size 0

Does our formula hold for a tower for size 0? Obviously it takes 0 moves to move a tower of 0 rings, so:

	2⁰ - 1 = Moves(0) = 0
	2⁰ - 1 = 0
	2⁰ = 1

But let's look at that another way:

N	5	4	3	2	1	0	-1	-2
2^N	32	16	8	4	2	?	?	?

It should be clear that subtracting 1 from the index divides the number by 2. For example 2⁵ ÷ 2 is 2⁴. So 2¹ ÷ 2 is 2⁰, and given 2¹/2 is 2/2 which is 1, 2⁰ is 1.

So what is 2^-1? By continuing the series, 2^-1 is 2⁰/2 which is 1/2. Therefore 2^-1 is ½. Similarly 2^-2 is 1 / (2²) which is ¼.

In fact we can state that 2^-N is 1/ (2^N) and 1 / (2^M) is 2^-M.

If we want to multiply powers we just add the exponents as in:

	2³ × 2⁴ = 2^{3 + 4}

This also makes it easy to divide a power by a power.

	2^N ÷ 2^M = 2^N × 2^-M = 2^N-M

hanoi10.qh - 1.4 - 05/10/02