Originally posted by joe shmoBecause the two ways you mention are saying exactly the same:
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?
[-1+2^(n-1)]*2 + 1 = -1 + 2^n
- Joined
- 10 Dec 06
- Moves
- 8528
Originally posted by joe shmoWhen I did it the long way
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.
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
Originally posted by joe shmoI 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:
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.
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.
- Joined
- 10 Dec 06
- Moves
- 8528
Originally posted by Mephisto2thanks
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.
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.
- Joined
- 10 Dec 06
- Moves
- 8528
Originally posted by geepamoogleI think I'm halfway there, how would 4 pegs affect the series? I tinkered with it but had no sucess.
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]
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.