Prueba de la solución iterativa del problema de la Torre de Hanoi

Question

Así que estaba explorando el El problema de las torres de Hanoi en la wikipedia, y me encontré con el solución iterativa de:

1. Realiza el movimiento legal entre las clavijas A y B (en cualquier dirección)
2. Realiza el movimiento legal entre las clavijas A y C (en cualquier dirección),
3. Realiza el movimiento legal entre las clavijas B y C (en cualquier dirección), repite hasta completar

para un número par de discos, y para un número impar de discos:

1. Realiza el movimiento legal entre las clavijas A y C (en cualquier dirección)
2. Realiza el movimiento legal entre las clavijas A y B (en cualquier dirección),
3. Realiza el movimiento legal entre las clavijas B y C (en cualquier dirección), repite hasta completar.

¿Por qué funciona esta solución iterativa? Exploré un poco más y descubrí que si continúas con este conjunto de instrucciones incluso cuando los discos están todos en el polo derecho, los discos acabarán formando una pila en el polo central. ¿Por qué ocurre esto?

Answer 1

Si te interesa, explico cómo resolver la Torre de Hanoi (además de las pruebas de inducción) en este video .

La solución iterativa se basa básicamente en el principio de la inducción. Si se sabe cómo mover una torre con $n-1$ piezas, entonces puedes averiguar cómo mover una torre con $n$ piezas. La solución es básicamente

1. Mover $n-1$ piezas del polo A al polo C
2. Mueve el disco restante en el polo A al polo B
3. Mueve el $n-1$ torre que dejó en el poste C de nuevo en la parte superior del poste B

Por supuesto, el paso 1) es mucho más complicado que los otros pasos. Desenrollemos el paso 1) y veamos qué patrones observamos.

1. Mueve el $n-2$ piezas del polo A al polo B
2. Mueve el $n-1$ disco que queda en el polo A al polo C
3. Mueve el $n-2$ torre del poste B al poste C
4. Mueve el disco restante en el polo A al polo B
5. Mueve el $n-1$ torre que dejó en el poste C de nuevo en la parte superior del poste B

Aparte del paso 1), los otros pasos implican mover un solo disco (el único movimiento legal) a la vez entre los polos en un patrón indicado por la solución iterativa. Este patrón es $$ A\rightarrow B\\ A\rightarrow C\\ B\rightarrow C\\ A\rightarrow B\\ C\rightarrow A\\ C\rightarrow B $$

Si desenrollamos completamente el paso 1), entonces vemos que la secuencia completa de movimientos para resolver las Torres de Hanoi es simplemente repetir este patrón de $6$ pasos una y otra vez hasta que hayamos terminado. Por supuesto, si queremos que la torre acabe en un poste concreto, puede que tengamos que reordenar los $6$ pasos dependiendo de si la torre inicial tiene un número par o impar de discos.