Óptimo de las Torres de Hanoi estrategia (3 pilares, desde el pilar a directamente a C no se permite)

Question

Estoy trabajando en un ejercicio donde necesito encontrar el número de pasos (Tn) para la resolución de las Torres de Hanoi, mientras que tener tres pilares (a, B, C). Todos los discos (n) son colocados en el pilar a y la necesidad de ser trasladado a pilar C. no está permitido mover un disco de pilar a pilar C directamente, todos los discos tienen que pasar por el pilar B.

No sé por donde empezar, he intentado escribir un ejemplo para el 2 y 3 discos, pero en cuatro discos, tuve la idea de que estaba haciendo mucho más movimientos de los que realmente necesita.

Cualquier ayuda es muy apreciada,

Gracias!

Answer 1

Para mover $n$ discos de $A$ $C$usted necesita para mover

1. $n-1$ discos de $A$ $C$
2. disco de $n$ $A$ $B$
3. $n-1$ discos de $C$ $A$
4. disco de $n$ $B$ $C$
5. $n-1$ discos de $A$ $C$

Para mover $n$ discos de $C$ $A$usted necesita para mover

1. $n-1$ discos de $C$ $B$
2. disco de $n$ $C$ $A$
3. $n-1$ discos de $B$ $A$

Para mover $n$ discos de $A$ $B$usted necesita para mover

1. $n-1$ discos de $A$ $C$
2. disco de $n$ $A$ $B$
3. $n-1$ discos de $C$ $B$

Para mover $n$ discos de $B$ $A$usted necesita para mover

1. $n-1$ discos de $B$ $C$
2. disco de $n$ $B$ $A$
3. $n-1$ discos de $C$ $A$

Para mover $n$ discos de $B$ $C$usted necesita para mover

1. $n-1$ discos de $B$ $A$
2. disco de $n$ $B$ $C$
3. $n-1$ discos de $A$ $C$

Para mover $n$ discos de $C$ $B$usted necesita para mover

1. $n-1$ discos de $C$ $A$
2. disco de $n$ $C$ $B$
3. $n-1$ discos de $A$ $B$

Esto se traduce en seis de relaciones de recurrencia. Por ejemplo

$$m_{AC}(n)=2+2m_{AC}(n-1)+m_{CA}(n-1)$$

y con todos los seis a continuación, puede calcular esto para $n$ tan grande como te gusta. Por ejemplo (corregido:) $m_{AC}(20)=40424579$.

Answer 2

El uso de Henry notación, el sistema de recurrencias es

$$\left\{\begin{align*} &m_{AC}(n+1)=2m_{AC}(n)+m_{CA}(n)+2\\ &m_{CA}(n+1)=m_{CB}(n)+m_{BA}(n)+1\\ &m_{AB}(n+1)=m_{AC}(n)+m_{CB}(n)+1\\ &m_{BA}(n+1)=m_{BC}(n)+m_{CA}(n)+1\\ &m_{BC}(n+1)=m_{BA}(n)+m_{AC}(n)+1\\ &m_{CB}(n+1)=m_{CA}(n)+m_{AB}(n)+1\;. \end{align*}\right.$$

Entonces $$\begin{align*} m_{CA}(n+1)&=m_{CB}(n)+m_{BA}(n)+1\\ &=2m_{CA}(n-1)+m_{AB}(n-1)+m_{BC}(n-1)+3\\ &=2m_{CA}(n-1)+2m_{AC}(n-2)+m_{CB}(n-2)+m_{BA}(n-2)+5\\ &=2m_{CA}(n-1)+2m_{AC}(n-2)+m_{CA}(n-1)+4\\ &=3m_{CA}(n-1)+2m_{AC}(n-2)+4\;. \end{align*}$$

Por otro lado, $m_{CA}(n)=m_{AC}(n+1)-2m_{AC}(n)-2$, por lo que $$\begin{align*} m_{CA}(n+1)&=m_{AC}(n+2)-2m_{AC}(n+1)-2\;,\\ m_{CA}(n-1)&=m_{AC}(n)-2m_{AC}(n-1)-2\;, \end{align*}$$

y por lo tanto $$\begin{align*} m_{AC}(n+2)-2m_{AC}(n+1)-2&=m_{CA}(n+1)\\ &=3m_{CA}(n-1)+2m_{AC}(n-2)+4\\ &=3m_{AC}(n)-6m_{AC}(n-1)+2m_{AC}(n-2)-2\;, \end{align*}$$

o $$m_{AC}(n+2)=2m_{AC}(n+1)+3m_{AC}(n)-6m_{AC}(n-1)+2m_{AC}(n-2)\;.$$

Finalmente, el cambio de los índices nos da $$m_{AC}(n)=2m_{AC}(n-1)+3m_{AC}(n-2)-6m_{AC}(n-3)+2m_{AC}(n-4)\;.$$

Directo de cálculo de los valores iniciales son $m_{AC}(0)=0$, $m_{AC}(1)=2$, $m_{AC}(2)=7$, y $m_{AC}(3)=19$. Sigue la secuencia $47, 113, 267, 629$ y no está en OEIS.

La ecuación auxiliar es $x^4-2x^3-3x^2+6x-2=0$, que se reduce a $$(x-1)(x^3-x^2-4x+2)=0\;.$$ The cubic factor has three real roots; I didn't feel like writing down the exact expressions for them, but this cubic equation calculator says that they are approximately $$\begin{align*}&2.34292308277717\;,\\ -&1.81360650264833\;,\text{ and}\\ &0.47068341987116\;. \end{align*}$$

En el largo plazo, la primera va a dominar, y la secuencia de crecer en aproximadamente un factor que con cada aumento de uno en el número de discos. Para el registro, $629/267\approx 2.3558$.