Me referiré a tu primera pregunta, pero no a la del mayor número de varillas; por lo que sé, todavía está muy abierto cuál podría ser la estrategia óptima incluso para $4$ varillas y un pequeño número de discos.
Para mostrar la estrategia óptima para $n$ discos en $3$ varillas es la "habitual", se puede hacer por inducción (que da una solución recursiva). Seguro que hay otras formas de demostrarlo, quizás con números de Lucas como sugieres.
Está claro que la estrategia óptima con $n=1$ es simplemente mover el disco directamente.
Supongamos que ya tienes la estrategia óptima para mover $k$ discos. Para mover $k+1$ discos, necesita mover el disco más grande desde la barra inicial a la barra terminal, pero esa es la única vez que necesita moverse (no puede ayudarle con los otros discos, ya que debe estar en el fondo en cualquier momento, por lo que cualquier otro movimiento sólo requiere más movimientos al final); para mover el fondo ( $k+1$ )st disco de la barra inicial $I$ a la barra de terminales $T$ primero hay que mover la parte superior $k$ discos fuera del camino; esto requiere mover el $k$ discos de la barra inicial $I$ a la barra auxiliar $A$ y la forma óptima de hacerlo es la estrategia óptima que se conoce para $k$ discos. Luego se mueve el $k+1$ disco, y luego quiere mover el resto $k$ discos de la barra auxiliar a la terminal en el menor número de movimientos posible (la forma óptima). Por tanto, la estrategia óptima para $k+1$ discos es mover la parte superior $k$ utilizando la estrategia óptima para $k$ de $I$ a $A$ , entonces mueve el disco más grande de $I$ a $T$ y luego mover la parte superior $k$ discos utilizando la estrategia óptima para $k$ de $A$ a $T$ .
Si se lleva la cuenta del número real de movimientos necesarios en cada paso, se puede dar el número Para $n=1$ el número es $1=2^1-1$ . Supongamos que el movimiento $k$ discos requiere $2^k-1$ movimientos en la estrategia óptima. La estrategia óptima para $k+1$ descrito anteriormente toma $(2^k-1) + 1 + (2^k-1) = 2^k+2^k - 1 = 2^{k+1}-1$ pasos; así, la solución óptima para $n$ discos y $3$ varillas requiere $2^n-1$ se mueve.
(Esto no se generaliza fácilmente a más de $3$ varillas por razones presumiblemente obvias).
Un poco más interesante es intentar demostrar que la solución no recursiva da una solución óptima; esta solución sólo requiere que recuerdes el último disco que has movido en cada momento (la solución recursiva requiere más memoria, por supuesto). Numerar las barras $0$ , $1$ y $2$ . Tenemos tres reglas:
- Nunca mueva el mismo disco dos veces seguidas.
- Sólo se puede mover un disco de la parte superior de una barra a la parte superior de otra barra.
- Mover un disco de la barra $i$ a la varilla $j$ sólo es válido si $i\neq j$ , y cualquiera de las dos varillas $j$ está vacío o el disco superior de la barra $j$ es mayor que el disco superior en barra $i$ .
Con estas reglas, el algoritmo no recursivo tiene dos simples pasos:
- Si está moviendo el disco de varilla $i$ y las otras dos varillas son destinos válidos, entonces muévelo a la varilla $i+1\mod 3$ . Si no, muévelo al único destino válido.
- Si no es posible ningún movimiento, deténgase. De lo contrario, continúe.
Este proceso resolverá el rompecabezas con $3$ varillas en el mínimo número de movimientos.
