0

In the Tower of Hanoi game, we have three pegs A, B, and C, with a pile of n rings on peg A such that each ring has a smaller diameter than the ring immediately below it and thus the largest ring is at the bottom of the pile. The aim of the game is to move the rings individually between pegs, at no stage placing a larger ring on top of a smaller ring, so that the whole pile is ultimately shifted to another peg, say B.
Let $H_n$ be the minimal number of moves required to shift a pile of n rings from one peg to another.
Obtain a recurrence relation for $H_n$.

I tried taking small cases and it looks like the solution is $2^n -1$ which means that $H_n = 2H_{n-1} -1$ or something like that.

How would I be able to logically "talk" out the steps to obtain the recursive formula?
(where one would take disjoint cases to discuss. E.g. In the question of constructing a binary string of length $n$ with a repeating $00$ somewhere, we would do something like: Let $a_n$ be number of ways for binary string that has a repeating $00$ somewhere. Then if the string starts with $1$, then we are left with a string of length $n-1$. So we can construct it in $a_{n-1}$ ways. If the string starts with $01$, then it is $a_{n-2}$. If it starts with $00$, then the number of ways is $2^{n-2}$. In total, $a_n = a_{n-1}+a_{n-2} + 2^{n-2}$.)

Natash1
  • 1,379

1 Answers1

1

The idea behind the recursive formula is this:

In order to move the entire tower to peg $C$, you need to move everything except the last ring to peg $B$, then move the last ring to peg $C$, then move everything back on top of the largest ring.

None of the other rings care where the largest ring is, so moving them off the largest ring or back onto is exactly the same as just moving a tower that's one ring smaller.

Arthur
  • 199,419
  • I see. How would I reason this out though?
    I feel like this is an argument like: Define $H_n$ to be the minimal amount of moves to move $n$ ring to another peg. "Move $1$ ring to peg $B$. Then now focusing on $A$ and $C$, then by definition, moving the $n-1$ rings to peg $C$ is equal to $H_{n-1}$. So the total is just $H_n = 1 + H_{n-1}$."
    I'm not sure how to reason in a way that includes the coefficient of $2$.     – Natash1 Oct 16 '17 at 07:46
  • 1
    Move everything except ring $n$ to peg $B$. That takes $H_{n-1}$ moves. Then move ring $n$ to peg $C$. That's one move. Then move everything back ponto ring $n$. That's another $H_{n-1}$ moves. In total $2H_{n-1} + 1$ moves. There is some fiddling showing that this is actually minimal, but that can be done recursively as well: you can't move the largest ring unless all the other rings are stacked on a single peg. – Arthur Oct 16 '17 at 07:48