A probability problem by Anita Paul

Tower of honai problem... Minimum moves will be (2^n) -1. Where n = no of disk

2^n - 1. N=9 therefore 2^9 - 1 = 511

Well, let's assume we don't know the formula for Tower of Hanoi Problem and try to deduce it. (I really didn't know at first, but kind of deduced it.) In my opinion, if we don't know the formula beforehand, it really ain't just a Level 1 problem.

Start with small numbers. Let n = number of disks.

When n=1, min. moves will be 1 (obviously)

n=2, min. moves will be 3

n=3, min. moves will be 7

Now, given the min. moves when n=3, we try to deduce the min. moves when n=4.

Let's say we used 7 moves to move the first 3 disks to rod 2. Then, we move disk 4 to rod 3. We use another 7 moves to move the first 3 disks to rod 3. Hence, the minimum moves when n=4 is 7 + 1 + 7 = 15.

In other words, when the min. moves for k disks is m, the min. moves for (k+1) disks is 2m + 1. We'll use this relationship later to prove our conjecture.

We are ready to spot the pattern and form a conjecture.

$1 = 2^{1} - 1$

$3 = 2^{2} - 1$

$7 = 2^{3} - 1$

$15 = 2^{4} - 1$

...

min. moves for n disks $= 2^{n} - 1$ .

We'll use induction to prove our conjecture. As mentioned earlier, $1 = 2^{1} - 1$ and $3 = 2^{2} - 1$ .

Let's assume our conjecture works for k disks, ie.

min. moves for k disks, m $= 2^{k} - 1$

For (k+1) disks, we have found that the min. moves is 2m + 1.

$2m+1 = 2 ( 2^{k} - 1) + 1$

$2m+1 = 2^{k + 1} - 1$

min. moves for (k+1) disks $= 2^{k + 1} - 1$ ,

which is our conjectured formula for (k+1) disks.

Thus, our conjecture is proven.

When n=9, min. moves $= 2^{9} - 1 = \boxed{511}$

Minimum moves formula ( 2^n - 1 )...

This 'formula' valid for 3 rods problems. with n=numbers of disks

$Minimum Moves={ 2 }^{ n }-1$

2^n - 1. We got 9 discs so 2^9 - 1 = 511

This is classic Towers of Hanoi problems. The formula for the number of minimum moves is (2^n) -1. So for n=9; there are (2^9) -1 = 511 moves.

The problem of "Towers of Hanoi," in which the minimum number of moves should be 2^n-1 (n is the number of pegs on the first rod)

Hanoi Formula, for n disks, the number of the minimum moves is (2^n)-1.

So for n=9

We found (2^9)-1 = 512 - 1 = 511