jueves, 3 de marzo de 2011

Familia de funciones enteras

Enunciado

Este es un problema muy duro para estas edades, pero que en realidad lo único que requiere es darse cuenta de una serie de relaciones entre los números.

Para fijar ideas, trataremos de encontrar algunos valores para la función en el caso que nos solicitan (r = 5 y s = 8), hasta poder predecir qué vale F(2010), como piden en el apartado (1).

Probemos con F(1). Como F(1) = 1 + 5 o bien F(1) = 1 - 8, puesto que es un entero positivo, esta última posibilidad queda descartada, luego F(1) = 6. De la misma forma, F(2) = 7, F(3) = 8, y así sucesivamente, hasta que lleguemos a F(9), en el que podemos elegir entre 9 + 5 y 9 - 8, pues ambos son positivos. Sin embargo, si pensamos un poco, encontramos que no queda más remedio que elegir 9 - 8 = 1, ya que todos los números deben ser F(n) para algún n, y 1 debe ser, por tanto, de la forma n - 8 o bien de la forma n + 5. Claro, que 1 no puede ser de la forma n + 5, por lo que debe ser F(9). Así, 1 = F(9), 2 = F(10), y así hasta 5 = F(13).

Es decir, que los 13 primeros valores pasan a ser, sucesivamente, 6, 7, 8, 9, 10, 11, 12, 13, 1, 2, 3, 4, y 5. Ahora, vuelve a pasar algo similar: F(14) no puede ser 14 - 8 = 6, porque 6 ya está "usado" (es F(1)), luego F(14) = 14 + 5 = 19. En resumen, que los siguientes valores son 19, 20, 21, 22, 23, 24. 25, 26, y después volvemos a utilizar la expresión n - 8, porque si no lo hacemos, los números 14 a 18 se quedarán sin ser imagen de ningún número. De forma que continuamos con 14, 15, 16, 17, 18.

Supongo que se aprecia claramente cuál es el patrón ¿no? En realidad usamos el conjunto de enteros positivos de 13 en 13, aplicando la fórmula n + 5 a los 8 primeros y la fórmula n - 8 a los otros cinco. Veamos qué pasa con el 2010.

El 2010, si tratamos de dividirlo entre 13, da 154, y un resto de 8, es decir, 2010 es el octavo del grupo que empieza después del 2002 = 154*13. Luego se le aplica la fórmula n + 5 y por tanto F(2010) = 2015.

Vamos a intentar ahora responder a la segunda parte. En general, si r y s no valen 5 y 8, si no otras cantidades, el sistema para calcular F es similar. Se aplica a conjuntos de r + s números consecutivos, de forma que a los s primeros se les aplica la fórmula n + r, y a los siguientes r se les aplica la fórmula n - s. Es muy fácil extender el razonamiento que hemos usado antes al caso general.

Para entender bien la segunda parte, también lo aplicaremos al caso r = 5, s = 8, y después trataremos de aplicarlo en general. Puesto que cada conjunto de 13 números consecutivos se transforman en ellos mismos de la misma manera, bastará fijarse en los 13 números primeros, ya que si se cumple en ellos, será cierto para cualquier conjunto de números.

Aplicar F dos veces hace, por ejemplo, que F(F(1)) = F(6) = 11. Evidentemente, no basta. Aplicado 3 veces, hace que F(F(F(1))) = F(11) = 3. Si lo aplicamos cuatro veces, tendremos que F4(1) = F(3) = 8. Si lo aplicamos otra vez, F5(1) = F(8) = 13. Así, pasaremos, sucesivamente, por 5, 10, 2, 7, 12, 4, 9, y por fin llegaremos a 1 en F13(1) = F(9) = 1. Con un poco de trabajo, podemos comprobar que 13 es el menor valor de veces que tendremos que aplicar esta función para llegar a F13(n) = n.

¿Será la suma de r + s la respuesta? Pues no, pero antes de llegar a ello, veamos lo que pasa cuando aplicamos repetidamente F. En realidad, sumamos r y restamos s repetidamente, procurando no salirnos del conjunto de 1 a r + s, por lo que llegamos siempre a resultados de la forma ar - bs, donde a y b son números positivos. Las combinaciones de números enteros son muy conocidas de los aficionados a los problemas matemáticos, ya que siempre puede lograrse, eligiendo correctamente a y b, que dé como menor valor un resultado igual al máximo común divisor de r y s.

Es decir, que el número más próximo al 1 por el que pasaremos será 1 + d, donde d es el máximo común divisor (en el caso de 5, 8, pasamos por el 2, ya que 1 = 5*5 - 3*8). Evidentemente, pasamos también por 1 + 2d (el 3 en nuestro caso) y todos los términos de una progresión aritmética de diferencia d, es decir, recorremos a saltos de d todos los números de r + s. En el caso que nos ocupa, puesto que 5 y 8 tienen un MCD de 1, tenemos que dar 13 saltos para volver al original. Además, como no podemos coincidir en el mismo valor en dos saltos diferentes, tendremos que dar exactamente 13 saltos empezando desde cualquier número.

Ahora bien, si r y s tienen otro MCD, entonces es imposible conseguir con sumas de r y restas de s valores menores que d = MCD(r, s), por lo que sólo recorreremos (r + s)/d valores, es decir, que la respuesta en realidad al segundo apartado es que k vale (r + s)/MCD(r, s). Por ejemplo, si r = 4 y s = 6, k vale 5 (el recorrido de 1 sería: 5, 9, 3, 7, 1).

No hay comentarios: