Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It only takes a minute to sign up.
Sign up to join this community
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.
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.
