Estoy tratando de resolver el problema de las Torres Bicolores de Hanoi. Es una variación del clásico problema de las Torres de Hanoi. Hay $3$ clavijas (llamémoslas $A$ , $B$ , $C$ ) y $N$ discos en la clavija $A$ . Los discos tienen colores (blanco/negro) y se alternan, de modo que el primero es blanco, el segundo es negro, el tercero es blanco, etc. La tarea consiste en dividir esos discos en 2 clavijas, una formada por discos negros y la otra por discos blancos. Me gustaría encontrar el número mínimo de movimientos para resolver esto. Por ejemplo, si $N = 6$ entonces la respuesta correcta debería ser $45$ se mueve. ¿Cómo se hace esto?
Respuesta
¿Demasiados anuncios?
Que los discos estén numerados $1, \ldots, N$ de menor a mayor. Sin pérdida de generalidad (WLOG), supongamos que todos están en la clavija $A$ al principio.
Discos $N$ y $N - 1$ son de diferentes colores, por lo que como mínimo debe mover disco $N - 1$ fuera del disco $N$ y en otra clavija. WLOG, suponga que decide mover el disco $N - 1$ a la clavija $B$ . Para ello, primero hay que mover los discos $1, \ldots, N - 2$ a la clavija $C$ .
Así que ahora tienes disco $N$ en la clavija $A$ , disco $N - 1$ en la clavija $B$ , y todos los demás discos de la clavija $C$ . Tienes que conseguir disco $N - 2$ en la clavija $A$ . Pero para hacer esto tienes que mover todos los discos pequeños de la clavija $C$ a la clavija $B$ . Haz todo esto, así que ahora tienes discos $N$ y $N - 2$ en la clavija $A$ y todos los demás discos de la clavija $B$ .
Afortunadamente, no tiene que mover el disco $N - 3$ de nuevo, porque ya está ya está exactamente donde lo quieres (en la parte superior del disco $N - 1$ ). De hecho, ahora tienes el mismo problema con el que empezaste, pero con $N - 2$ discos en la clavija $B$ en lugar de $N$ discos en la clavija $A$ , y necesitas mover el disco $N - 3$ a la clavija $A$ .
Se puede hacer un algoritmo recursivo de esto, con la recursión cada vez que el número de discos a mover se reduzca en $2$ . Del mismo modo, se puede hacer una fórmula recursiva para calcular cuántos movimientos requerirá el algoritmo.
