sábado, 29 de marzo de 2008

El Problema 3n+1 y los Fractales...

" Durante un mes, todo Yale estuvo trabajando en él, sin resultado.
Fenómeno similar se produjo al mencionar, yo, el problema en la Universidad de Chicago.
Incluso llegó a decirse, en broma, que el problema formaba parte de una conjura
para entorpecer la investigación matemática en los Estados Unidos."

Shizuo Kakutani, hacia 1960 aproximadamente.


Hemos visto como la iteración de un proceso geométrico a muchas escalas genera un fractal.
Ahora, vamos a insistir en la idea de generar complejidad a través de simples iteraciones.

Comenzaremos con un clásico de lo irresuelto: el problema 3n+1. Tomemos un número entero positivo cualquiera, xo.

(1) Si el número escogido es impar lo multiplicamos por 3 y le sumamos 1.
(2) Si, por el contrario, es par lo dividimos entre 2.

De esta manera conseguimos x1, sobre el que volvemos a repetir el proceso y así sucesivamente. La iteración puede ser escrita entonces como:

xn+1 =

3xn+1 si xn impar

xn/2 si xn par

Veamos como actúa el algoritmo iterativo sobre algunas semillas iniciales. Comencemos tomando xo=1. Inyectando la semilla inicial en la aplicación iterada obtenemos sucesivamente: 1,4,2,1,4,2,1,... Caemos en un ciclo periódico de tres elementos. Como partimos de un elemento del propio ciclo, recorremos L=3 pasos hasta volver a repetirnos. Puesto que el 2 y el 4 pertenecen al ciclo, utilizarlos como semilla inicial no nos aportaría nueva información. Probemos con xo=3 como semilla inicial. La sucesión de valores en este caso es: 3,10,5,16,8,4,2,1,4,2,1,... y de nuevo tropezamos con el ciclo periódico anterior, pero ahora la longitud de la trayectoria recorrida, el número de iteraciones requerido hasta la repetición de la dinámica, es de tamaño L=8. Observemos que el valor máximo conseguido en la sucesión es max{xi} = 16.

Ahora que estamos más familiarizados con el procedimiento, nos podemos permitir hacer alguna modesta generalización: siempre que tropecemos con una potencia de 2, una sucesión de divisiones nos arrastrará indefectiblemente hacia el valor 1. La caída será en picado. Sin embargo, si bien existen infinitas potencias de 2, nadie nos asegura que a la larga cualquier número acabe en una de ellas.


Si tomamos xo= 27, el camino seguido es extraordinariamente tortuoso. La sucesión alcanza el valor 1 tras L=111 pasos y su valor máximo corresponde a max{xi}= 9232.

Al problema 3n+1 también se le conoce con el nombre problema de los números-granizo: el valor de los sucesivos números asciende y desciende de manera aparentemente errática, como lo hacen las bolitas de granizo en el interior de las nubes, hasta que llega un momento en que se precipitan hacia tierra. En el problema hasta tomar el valor 1.

Cuando nos paramos a reflexionar, las preguntas, de forma natural, comienzan a bullir:

* ¿Qué ocurre con la sucesión de números producidos al introducir un número semilla inicial?
* ¿Caen siempre en picado hacia el valor 1?
* ¿O para algunos valores el crecimiento es imparable?
* ¿Existen más ciclos que el {4, 2, 1}?
* ¿Podemos hacer alguna afirmación sobre la convergencia o divergencia de las sucesiones de valores?

Estamos ante un procedimiento iterativo fácil de describir, pero endiabladamente difícil de estudiar. De hecho, acabamos de describir un problema no resuelto en teoría de números. Un problema fácil de entender por cualquiera y aún no resuelto por nadie.

El problema parece haber sido redescubierto varias veces en momentos distintos, cayendo en el olvido y resurgiendo caprichosamente durante los últimos cuarenta años. La frase del encabezado muestra hasta que extremo el problema se ha mostrado refractario a solución.

Volvamos a nuestras pruebas y sigamos formulando preguntas: ¿Caeremos siempre en el ciclo 4-2-1? Se han efectuado cálculos como los mostrados anteriormente hasta valores de 2 elevado a 40. En todos los casos se comprobó que la sucesión acababa cayendo al ciclo 4-2-1. No se han descubierto otros ciclos. Sin embargo, la conjetura de que todos los números acaben cayendo a este ciclo sigue siendo una cuestión pendiente de demostración teórica.

La lección destacable de este embrollo numérico, donde a veces parecen atisbarse regularidades mezcladas con pautas aparentemente azarosas, es que una ecuación simple y determinista puede crear enorme complejidad y azar aparentemente insalvable. Conocemos la rígida regla y es enormemente sencilla, pero somos incapaces de determinar qué nos deparará su aplicación reiterada.