6
$\begingroup$

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.

$\endgroup$
  • 2
    $\begingroup$ 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? $\endgroup$ – Vor Oct 4 '12 at 8:30
  • $\begingroup$ @Vor increasing diameter like the standard game $\endgroup$ – Parisa Oct 4 '12 at 10:33
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – Raphael Oct 6 '12 at 9:33
  • 1
    $\begingroup$ (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. $\endgroup$ – jmad Oct 7 '12 at 12:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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