Tengo una duda sobre un ejercicio del capítulo 1 de "Matemáticas concretas". En realidad, mi duda está en un ejercicio ( ejercicio 3 ), pero, como depende del ejercicio anterior (2), lo incluyo aquí también, con la respectiva solución que encontré.
Sí, sé que podría simplemente comprobar la respuesta en el Apéndice A, ya que "Matemáticas concretas" da respuestas a prácticamente todos los ejercicios. Pero he aquí por qué no quiero hacer esto: No sé cuán lejos está mi propio intento de la respuesta correcta. Así que me gustaría que alguien comprobara si mi intento tiene sentido y diera pistas si hay algo incorrecto o incompleto. Si compruebo la solución oficial de inmediato, y está muy lejos de lo que hice, posiblemente acabaría perdiendo la oportunidad de encontrar la respuesta correcta (y tampoco estaría seguro de si mi propio intento es también válido).
2. Encuentre la secuencia más corta de movimientos que traslada una torre de n discos desde la clavija izquierda A a la clavija derecha B, si se descartan los movimientos directos entre A y B. (Cada movimiento debe ser hacia o desde la clavija central. Como es habitual, un disco mayor nunca debe aparecer por encima de uno menor).
Nota: No tengo ninguna duda en este ejercicio en particular, pero lo he incluido porque el ejercicio en el que tengo la duda depende de este. Incluyo la solución completa y detallada sólo para mostrar mi trabajo.
Primero, el caso más sencillo: si hay 0 discos, necesitamos $T_0 = 0$ se mueve. Para $T_n$ necesitamos mover el disco más grande a la clavija B. Para ello, primero tenemos que mover el disco superior $n - 1$ discos a la clavija B, lo que requiere $T_{n-1}$ se mueve. Luego, movemos el disco más grande a la clavija del medio (1 movimiento). Entonces, podemos mover el $n - 1$ discos en la clavija A ( $T_{n-1}$ más movimientos). Luego, movemos el disco más grande a la clavija B (un movimiento más). Por último, podemos mover el $n-1$ discos a la clavija B ( $T_{n-1}$ más movimientos).
Así, obtenemos la siguiente relación de recurrencia:
$T_0=0$
$\\ T_n = 3T_{n-1}+2 \ \ \ \ \text{for } n\geq1$
Por lo tanto, tenemos que $T_0 = 0$ , $T_1 = 3T_0 + 2 = 2$ , $T_2 = 3T_1 + 2 = 8$ , $T_3 = 3T_2 + 2 = 26$ etc. Trabajando con estos ejemplos numéricos, podemos ver finalmente que $T_n = 3^n - 1$ . Esto se puede demostrar por inducción; para el caso base: $T_0 = 3^0 - 1 = 0$ . Para el paso inductivo, supongamos que es cierto que $T_{k} = 3^k - 1$ para algún k; dado esto, queremos demostrar que $T_{k+1} = 3^{k+1} - 1$ . Esto es cierto, porque: $T_{k+1} = 3T_{k} + 2 = 3(3^{k} - 1) + 2 = 3^{k+1} - 3 + 2 = 3^{k+1} - 1$ .
3. (Este es el ejercicio que quiero que alguien verifique). Demuestre que, en el proceso de traslado de una torre bajo las restricciones del ejercicio anterior, nos encontraremos realmente con toda disposición correctamente apilada de n discos sobre tres clavijas.
He probado manualmente algunos casos básicos ( $n = 1$ , $n = 2$ ) utilizando la relación de recurrencia del ejercicio anterior, y llegó a la conclusión de que los pasos necesarios para mover los n discos de la clavija A a la clavija B generan realmente todos los arreglos, y surgen todas las configuraciones posibles de los n discos en las 3 clavijas, incluida la configuración inicial (es decir, cuando todos los discos están en la clavija A).
Ahora, trataré de explicar por qué esta relación de recurrencia da todos los arreglos de n discos. Mi explicación puede no ser muy clara, y puede ser confusa.
En primer lugar, el configuración inicial (es decir, todos los discos están en la clavija A) es una disposición posible. Utilicemos el siguiente razonamiento: sólo hay dos cosas: el disco más grande es una cosa y la parte superior $n-1$ Los discos son otra cosa. Consideremos la parte superior $n-1$ discos como un bloque indivisible (como si fuera un solo disco). Entonces, aplicando la relación de recurrencia, podemos ver que:
1) Cuando el disco más grande está en la clavija A, la parte superior $n-1$ Los discos se mueven sucesivamente de la clavija A a la clavija M (clavija central) y luego a la B. Esto dará todas las disposiciones posibles entre el disco más grande y el superior $n-1$ discos (visualizados como un bloque) donde el disco más grande está en la clavija A.
2) Cuando el disco más grande está en la clavija M, la parte superior $n-1$ los discos se mueven de la clavija B a la clavija M, y luego a la clavija A. Esto dará todos los arreglos posibles donde el disco más grande está en la clavija M.
3) Cuando el disco más grande está en la clavija B, la parte superior $n-1$ los discos se mueven de la clavija A a la clavija M, y luego a la clavija B. Esto dará todos los arreglos posibles donde el disco más grande está en la clavija B.
Como se trata de una función recursiva, el mismo argumento anterior se aplicará recursivamente a los movimientos de la parte superior $n-1$ discos; es decir, el mayor de los $n-1$ discos será una cosa y la parte superior $n-2$ discos será otra cosa. Y así, recursivamente. De aquí podemos concluir que se obtendrán todos los arreglos posibles.
Para terminar esta respuesta, voy a calcular el número de arreglos, de la siguiente manera: para cada uno de los $n$ discos, en orden decreciente de tamaño (del más grande al más pequeño), elige una de las 3 clavijas y coloca el disco en la clavija. Así, para cada disco, hay 3 opciones de clavija. Por lo tanto, el número de arreglos es $3^n$ . Esto tiene sentido, porque el número de movimientos es $3^n-1$ . El número de arreglos es uno más el número de movimientos, porque incluye la configuración inicial (donde todos los discos están en la clavija A).
