The tower of hanoi

go to www.primarygames.com, open the math section and go to the tower of hanoi. Make a set of rules to solve. also figure out the least number of moves possible with a tower of 25 rings.

33,554,431 = -1 + 2^25

Originally posted by Mephisto2
33,554,431 = -1 + 2^25

Was that easy for you?

There are two ways of achieving the answer, one way is to double the previous perfect moves and add one two get the next. The other, using the number of rings as the power of two and subtracting one. I can't see how these are related. can you help?

Originally posted by joe shmo
There are two ways of achieving the answer, one way is to double the previous perfect moves and add one two get the next. The other, using the number of rings as the power of two and subtracting one. I can't see how these are related. can you help?

Because the two ways you mention are saying exactly the same:

[-1+2^(n-1)]*2 + 1 = -1 + 2^n

do you think you can put that into words, if it's not to much trouble?
I have not yet solved an equation like that in my College Algebra 1 class
Is that a quadratic equation?

If not what level of math can I expect to see this.

Originally posted by joe shmo
do you think you can put that into words, if it's not to much trouble?
I have not yet solved an equation like that in my College Algebra 1 class
Is that a quadratic equation?

If not what level of math can I expect to see this.

When I did it the long way
the I think the two is signifigant because thats the number of moves possible before you have two re-move one of the original 2 moves.
then I took a lucky guess and raised the 2 two the number of rings trying to solve for and it confused me they seeme to be to similar to be a coincidence except for the +1 and -1

I hope you can understand that, because reading it afterwards proved to be quite a challenge in itself.

Originally posted by joe shmo
do you think you can put that into words, if it's not to much trouble?
I have not yet solved an equation like that in my College Algebra 1 class
Is that a quadratic equation?

If not what level of math can I expect to see this.

I am not up-to-date on math curricula. I expect this to be covered somewhere in 13 - 15 year age math. Let's try to make it simple:

You have three spots s1, s2 and s3. To move the pile from s1 to s3 it works this way:
- a pile of 1 goes immedeately to s3 = 1 move
- a pile of 2 requires that you put first the top on s2, then the bottom on s3 folllowed by the top on s3. Number of moves = 1+ number of moves in the first case *2
- a pile of three is done by putting the top pile of 2 on s2, moving the bottom to s3 and then moving the top pile from s2 to s3 = 1+ twice number of moves in the second case
- and so on ... each time you double the moves from last time, and add one for the bottom one. That is exactly what the formula +1 + 2^(n-1) means. And that formula is exactly the same as -1 + 2^n.

Originally posted by Mephisto2
I am not up-to-date on math curricula. I expect this to be covered somewhere in 13 - 15 year age math. Let's try to make it simple:

You have three spots s1, s2 and s3. To move the pile from s1 to s3 it works this way:
- a pile of 1 goes immedeately to s3 = 1 move
- a pile of 2 requires that you put first the top on s2, then the bottom on s3 folllowed ...[text shortened]... exactly what the formula +1 + 2^(n-1) means. And that formula is exactly the same as -1 + 2^n.

thanks

Let us call f(x) the number of moves required to move x discs in the Tower of Hanoi problem.

f(1) = 1
f(x+1) = 2*f(x) +1

The first is easy to see, the second is you shift the previous x discs, move the one you want, then shift the prvious on top of it.

The simplest way to figure this out is to look at the series..

1, 2*1+1=3, 2*3+1=7, 2*7+1=15..

From this short series, you can surmise the f(x)=2^x - 1, and can plug it in to test it.

So does 2^(x+1) - 1 = 2*2^x - 1? The quick answer is yes. (and 2^1 -1 = 1 as well)

As it happens, the formula could also be written the sum of 2^(x-1) from 1 to x, but this gets into summation notation, which is fairly advanced algebra.

Originally posted by geepamoogle
Let us call f(x) the number of moves required to move x discs in the Tower of Hanoi problem.

[b]f(1) = 1
f(x+1) = 2*f(x) +1

The first is easy to see, the second is you shift the previous x discs, move the one you want, then shift the prvious on top of it.

The simplest way to figure this out is to look at the series..

[i]1, 2*1+1=3, 2*3+ ...[text shortened]... ^(x-1) from 1 to x[/b], but this gets into summation notation, which is fairly advanced algebra.[/b]

I think I'm halfway there, how would 4 pegs affect the series? I tinkered with it but had no sucess.

That would be trickier. For the first 5 numbers, I get 1, 3, 5, 8, 13 moves respectively.

Originally posted by geepamoogle
That would be trickier. For the first 5 numbers, I get 1, 3, 5, 8, 13 moves respectively.

are you assuming that they continue adding the previous to the next
8,13,21,34, ect.

Actually no, I actually did it on paper, and those were the shortest I got for the first five. Although I did note the connection to Fibonachi series (apart from skipping the second 1 and the 2..)

I'm sure you could probably work out the series if you could come up with a consistent and efficient system of transfers using 2 temporary locations, and then study the numbers from that.