# An Alternative Hanoi Tower problem

We got tower $T_1$ with $n$ odd disks (1,3,5,...) and tower $T_2$ with $n$ even disks (2,4,6,...). Now we want to move all $2n$ disks to tower $T_3$. If $T(p,q)$ is a recurrence relation of minimum number of moves we make to move $p$ disks from $T_1$ and $q$ disks from $T_2$ to $T_3$, we must find $T(n,n)$.

If anyone has any idea, please share.

• What are the rules (allowed/forbidden moves) for the two types of disks ("odd" and "even")? Are they of increasing diameter like in the standard game? What is the target configuration? – Vor Oct 4 '12 at 8:30
• @Vor increasing diameter like the standard game – Parisa Oct 4 '12 at 10:33

Let $T_n$ be the the column of disks $1:2:…:n$.

Let's start by the end:

• $(T_n)()()$ is the final configuration. The only mean to get there is by moving the disk $n-1$ on the stack $(n)$, so the remaining $T_{n-2}$ should be on another stick. So we should get to:

• $(n)(n-1)(T_{n-2})$ in $2^{n-2}$ steps: first move the $n-1$ disk then use $2^{n-2}-1$ steps with Hanoi maneuvers to move the $T_{n-2}$. This again is accessible from

• $(n-2:n)(T_{n-3}:n-1)()$ in $2^{n-3}$ steps, which again is reachable from

• $(n-4:n-2:n)(n-3:n-1)(T_{n-5})$ in $2^{n-5}$ steps, from

• $(T_{n-6}:n-4:n-2:n)(n-5:n-3:n-1)()$ in $2^{n-6}$ steps...

At the end we get $2^{n-2}+2^{n-3}+2^{n-5}+2^{n-6}+… +2^{n-3i+1}+2^{n-3i}+…+c$.

Which is about $3(8^{n/3-1}+8^{n/3-2}+…)= \frac378^{n/3}$ modulo some constant depending on the remaining modulo $6$ of $n$. Testing in practice to determine the constant gives the exact formula for $n$ disks which happens to be surprisingly simple:

$$\left\lfloor \frac37 2^n \right\rfloor \enspace .$$

For $n∈\{1,2,3,4,5,6,7,8\}$ we get $\{0,1,3,6,13,27,54,109\}$ (the first five terms verified by hand) which happens to be OEIS's sequence A033129 which confirms that this is the fastest way.

• Nice touch, finding the result on OEIS. Have you verified that your formula matches the others (for $n>8$)? Also, you added $\lfloor\frac{3}{7} 2^{n+1} \rfloor$ to OEIS, which is correct? – Raphael Oct 6 '12 at 9:33
• (1) You need to verify for $n≤6$ then you can prove it equal with the recurrence relation. (2) It's $\left\lfloor\frac372^n\right\rfloor$ without constraints on where to put the tower. (e.g. if $n=1$ there's nothing to do so we get $0$ steps) The OEIS formula has a different offset. – jmad Oct 7 '12 at 12:15