Número mínimo de movimientos necesarios para resolver un rompecabezas de ensamblaje

Rompecabezas:
Te dan un rompecabezas que contiene n piezas. Una “ sección ” del rompecabezas es un conjunto de una o más piezas que se han conectado entre sí. Un “ movimiento ” consiste en conectar dos tramos. Dado que inicialmente todas las piezas están separadas, ¿cuál es el número mínimo de movimientos en los que se puede completar el rompecabezas?

Responder

Consideremos el problema anterior caso por caso:

Caso n = 2: En este caso, solo tenemos que combinar dos piezas, lo que se puede hacer en un solo movimiento. Por lo tanto, el número total de movimientos necesarios es 1.
Caso n = 3: aquí, primero podemos unir dos piezas cualesquiera según sea necesario y luego podemos agregar la pieza final a la sección. Esto da como resultado el número total de 2 movimientos.
Caso n = 4: Solo continuando con el último caso, podemos combinar primero dos piezas, luego combinar la tercera y finalmente, la cuarta pieza. El número total de movimientos requeridos en este caso es 3.
Para cualquier valor de n: observe el patrón que se acumula en los 3 casos anteriores. Primero resolvemos el rompecabezas para (n-1) piezas y luego finalmente agregamos la última pieza con 1 movimiento.
Representemos esto matemáticamente:

$Let F(n) be the function denoting the minimum number of moves required to solve the puzzle, where n is the number of pieces we have initially. Then, we have \\* \Rightarrow \hspace{30} F(n) = F(n-1) + 1 \\* \Rightarrow \hspace{30} F(n) - F(n-1) = 1 \\* \Rightarrow \hspace{30}$$\sum_{i=2}^{i=n}\hspace{5}(F(i) - F(i-1) = 1) \\* \Rightarrow \hspace{30}$$\sum_{i=2}^{i=n}\hspace{5}(F(i) - F(i-1)) = $$\sum_{i=2}^{i=n}1 \\* \Rightarrow \hspace{30}(F(n) - F(n-1) + (F(n-1) - F(n-2)) + ..... + (F(2) - F(1)) = n - 1 \\* \Rightarrow \hspace{30} F(n) - F(1) = n - 1 \\* \Rightarrow \hspace{30} F(n) - 0 = n - 1 (F(1) = 0, its\hspace{2}trivial) \\* \Rightarrow \hspace{30} F(n) = n - 1 \\*$