# Resolución del problema

## Método de inducción

Ahora que ya tenemos una expresión con la que creemos se puede calcular el número de movimientos, tenemos que demostrar que es válida para las 64 piezas. Esto lo haremos por medio del método de inducción matemática.

El método de inducción matemática consiste en realizar tres pasos:

1. Caso Base : Verificar un caso base;
2. Hipótesis de inducción : Suponer que es verdadero para n;
3. Paso inductivo : Demostrar que es válido al agregar un elemento más (n+1).

Piensa en este método como una fila infinita de fichas de dominó alineadas. Cuando tiras la primera, la siguiente se cae en consecuencia, pero al caer la siguiente provocará que se caiga una tercera y así sucesivamente.

Otra forma de verlo es si demostramos que funciona para n+1 y funciona para 1, entonces funciona para 1+1. Y como funciona para 2, funciona para 2+1, y como funciona para 3, entonces funciona para 3+1... Y así podríamos seguir para cualquier valor de n.

En general, lo complicado es ver (demostrar) que, si es válido para n, al agregar un elemento más, es decir, sumarle 1, llegamos a una expresión que involucre a n+1.

Objetivo
Intentemos demostrar que el número mínimo de movimientos para n discos será 2n -1, haciendo uso de la inducción matemática.
Para ello sigamos los pasos que se listaron anteriormente.

### 1) Verificar un caso base (Caso Base)

En las escenas anteriores comprobamos que para 1, 2 y 3 discos se cumple la fórmula, ya que: \begin{align} 2^1 - 1 &= 1 \\ 2^2 - 1 &= 3 \\ 2^3 - 1 &= 7 \\ \end{align} Por lo que ya tenemos por lo menos un caso base.

Es importante hacer notar que la n de nuestro caso base debe de ser lo más pequeña posible, ya que sólo podemos decir que es válido para las n mayores o iguales a nuestro caso base.

### 2) Suponer verdadero para \(n\) (Hipótesis de inducción)

Este paso sólo consiste en decir que es válido para \(n\). En nuestro caso, vamos a decir que la fórmula funciona para \(n\) discos, es decir, que se cumple \(2^n-1\) cuando tenemos \(n\) discos. A partir de aquí, llamaremos hipótesis de inducción a la expresión \(2^n-1\).

### 3) Demostrar que es valido al agregar un elemento más (\(n +1\)) (Paso inductivo)

Supongamos que ya movimos los discos de la torre a excepción del último, o dicho de otra manera, ya movimos una torre de \(n\) discos a otro poste y le agregamos un disco más. Entonces tenemos que determinar cuántos movimientos nos faltan a partir de la configuración actual para mover una torre de \( n+1 \) discos.

Determina cuántos movimientos adicionales necesitas hacer para mover el último disco y los otros discos de tal manera que la torre completa quede en el poste vacío.

Si observas, primero tuviste que mover el último disco al poste vacío (\(1\) movimiento) y luego hiciste \( 2^n - 1 \) movimientos para acomodar la torre que ya teníamos sobre el nuevo disco. Si hacemos la suma de la cantidad de movimientos nos da un total de \( 2^n - 1 + 1 = 2^n \).

Pero ¿cuántos movimientos se tuvieron que hacer previamente para acomodar los discos a como inicialmente se mostraron en el espacio interactivo ?
Movimientos previos :

Entonces el número total de pasos para mover la torre completa es : \begin{align} Movimientos &= 2^n + (2^n-1) \\ &= 2(2^n) - 1 \\ &= 2^{n+1} - 1 \\ \end{align} Y con esto queda demostrado, ya que llegamos a una expresión que involucra a n+1 y tiene la misma forma que nuestra suposición.

Número de movimientos
Ahora que estamos seguros de que nuestra fórmula \( 2^n -1\) funciona, podemos hacer el cálculo para 64 discos.
$$ 2^{64} - 1 \approx 1.844674407×10^{19} $$ Si los monjes pudieran mover un disco cada segundo, entonces el tiempo que les llevaría cambiar los discos de una torre a otra sería: $$ {1.844674407×10^{19} \over {60 \times 60 \times 24}} \approx 2.135039823×10^{14} días\ o... $$ $$ ¡\ 584,942,417,355\ años! $$

Condiciones de uso