Ésta es una generalización del post de ayer, que era un sencillísimo problema matemático.
Marta ha horneado cierto número de galletas y las ha dejado en la cocina mientras se enfrían. Por turnos, sus n hijos se cuelan y roban algunas.
- El hijo número 1 se come la mitad de las que hay en el plato más 1 galleta.
- El hijo número 2 se come la mitad de las que quedan en el plato más 2 galletas.
- El hijo número 3 se come la mitad de las que quedan en el plato más 3 galletas.
- ...
- El hijo número n se come la mitad de las que quedan en el plato más n galletas.
Después de que todos los hijos hayan pasado por la cocina, la madre vuelve y descubre que únicamente quedan k galletas en el plato.
¿Cuántas galletas había horneado inicialmente Marta? ¿Puedes hallar un modo de calcular ese número sean n y k los números que sean (naturales, por supuesto)? Puedes ayudarte del caso específico de ayer, para el que n = 3 y k = 1.
En la solución, puedes descubrir una manera recursiva de expresar el resultado. Tú mismo podrás probarla con distintos valores gracias a una herramienta que he programado en JavaScript.
SOLUCIÓN: analicemos el caso particular cuando n = 3 y k = 1. El tercer hijo se come la mitad de cierta cantidad más 3 galletas y deja 1 en el plato. Esto quiere decir que esa cantidad que había antes es 2*(1+3). Ahora mismo, no nos interesa el valor exacto de esa expresión, sólo la forma que tiene. Pasemos al segundo hijo, que se come la mitad de una cantidad más 2 galletas y deja, como acabamos de ver, 2*(1+3). Por lo tanto, las que había antes son 2*(2*(1+3)+2). ¿Vas viendo el patrón? Por último, el primer hijo se come la mitad de la cantidad original más 1 galleta y deja 2*(2*(1+3)+2), por lo que al principio había 2(2(2(1+3)+2)+1) (que es igual a 42, la respuesta del problema).
Si has entendido el proceso, verás que es trivial la generalización:$$2\Big( 2\Big( ... (2(k+n)+(n-1))...+2\Big) +1\Big)$$Salta a la vista la recursividad existente, por lo que podemos intentar expresar la fórmula mediante funciones recursivas.
Sea f la función definida mediante:$$\left\{ \begin{array}{ll} f(k,n,0) = k\\ f(k,n,m) = 2(f(k,n,m-1)+n-m+1) \;\; si \; m>0 \end{array} \right.$$Entonces, la solución de nuestro problema no es más que$$f(k,n,n)$$Puedes comprobar que todo funciona con esta herramienta, programada en JavaScript, que calcula ese valor utilizando el resultado de la función recursiva f a partir de k y n.
k = n =
No hay comentarios:
Publicar un comentario