1
$\begingroup$

Suppose we have three rods A, B and C, and rod A contains n disks (Exactly like the original Tower of Hanoi problem). The disks are numbered 1 to n, when the bottom disk is number 1 and the top disk is number n.

I want to build two towers: One on rod B which contains only the odd numbered disks and one on rod C which contains only the even numbered disks. The laws of disk moving is exactly like in the original problem.

I am trying to think if it is possible to solve it with only three rods, and if it is how can it be solved recursively.

I thought about moving the top two disks by hand (maybe depends on the parity of n) and then perform a recursive call, but I am not sure at all how to do it.

$\endgroup$
4
  • $\begingroup$ In your solution, you said that: "moving top two disks by hand". In the Tower of Hanoi problem, this is not allowed. You can only move one disk at a time. $\endgroup$ Jan 19, 2022 at 17:39
  • $\begingroup$ @InuyashaYagami For your first comment: I want to build two new towers with all of the disks: the odd disks to B and the even disks to C. For your second comment: I meant to move both disks one a time (maybe in three moves, but I am not sure how). $\endgroup$
    – Daniel
    Jan 19, 2022 at 17:47
  • $\begingroup$ Do you want minimum number of moves? $\endgroup$ Jan 19, 2022 at 17:53
  • $\begingroup$ @InuyashaYagami Not necessarily, a simple recursive algorithm (like the simple and intuitive algorithm for the original problem) is enough. $\endgroup$
    – Daniel
    Jan 19, 2022 at 18:05

1 Answer 1

1
$\begingroup$

Let $T_i$ be the tower defined by disks: $i,\dotsc,n$.

Here is a simple recursive algorithm:

Initialize i := 1
while(i != n+1)
    If i is even: 
           move the tower T(i+1) on any rod other than C using the standard Tower of Hanoi algorithm. 
           move disk i to rod C
    else:
           move the tower T(i+1) on any rod other than B using the standard Tower of Hanoi algorithm. 
           move disk i to rod B
    i <- i+1
end
$\endgroup$
2
  • 1
    $\begingroup$ Note that in this case, for $i < j$, disk $i$ is smaller than disk $j$. However, I think that makes the algorithm easier to write than in the case of the original post where disk $1$ was the largest. $\endgroup$
    – Nathaniel
    Jan 19, 2022 at 18:29
  • $\begingroup$ @Nathaniel right. I have edited the answer. Thanks! $\endgroup$ Jan 19, 2022 at 18:31

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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