2
$\begingroup$

This week in Algebra II we are studying the Hanoi tower's. Our assignment was to find what type of formula would give the number of moves it would take to solve the puzzle. After using a T-chart (where $x=$number of disks and $y=$ shortest number of moves that gives the solution)I found that

(0 , 0)
(1 , 1)
(2 , 3)
(3 , 7)
(4 , 15)
and
(5 , 31).

Using the information in the T-chart one should be able to find that $y=2^x-1$, however I don't know how to come to this conclusion on my own. My question today is, how do I find this formula with the given T-chart? That is my only question.....(P.S) everything I need to complete the assignment is done so this is more or less of an add on to improve what I know, NOT to get answers.

$\endgroup$
  • 1
    $\begingroup$ It is $y=2^x-1$, you shouldn't have the braces in the formula. $\endgroup$ – Ross Millikan Mar 11 '14 at 2:57
  • $\begingroup$ Finding a technique that will solve the puzzle is relatively easy, as Jared gave a hint for. Proving that this technique is optimal is probably a harder problem than you were intended to solve. I expect that your teacher only wanted you to come to the conclusion that there is a solution with this answer, not that it is the best. $\endgroup$ – DanielV Mar 11 '14 at 3:06
  • $\begingroup$ @RossMillikan yes you are corrects it shouldn't have those braces, thank you. $\endgroup$ – Diamond Louis XIV Mar 17 '14 at 22:04
2
$\begingroup$

Hint: Try to connect the solution for $n$ disks to the one for $n-1$ disks, and proceed by induction.

$\endgroup$
  • $\begingroup$ Sorry for the long amount of time it took me to respond, however I did figure out how to deduce the equation from the T-chart. I will answer my own question and list the steps I used to figure it out. first I made the T-chart and listed the number of disks currently in play under the $x$ column and under the $y$ column I put shortest number of moves possible to solve the puzzle. I then got this:(0,0)(1,1)(2,3)(3,7)(4,15)(5,31) I then found the first differences, which are:1,2,4,8,16 when I looked at this chart I realized that the first differences create.... $\endgroup$ – Diamond Louis XIV Mar 17 '14 at 22:21
  • $\begingroup$ the equation $2^x$ when they stand alone. then I compared that equation above to the T-chart and found that the $y$ values in the original T-chart are also represented by $2^x$ but shifted down by 1, thus I conclude that the original problem can be represented by the equation $2^x-1$ $\endgroup$ – Diamond Louis XIV Mar 17 '14 at 22:28

Not the answer you're looking for? Browse other questions tagged or ask your own question.