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

1 Answer 1

5
$\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$
2
  • $\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
    Commented Oct 6, 2012 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
    Commented Oct 7, 2012 at 12:15

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.