Hay una insólita clase de problemas aritméticos los cuales pueden ser asociados a un problema computacional de iteraciones, "loops" o "bucles". La idea es generar una serie de enteros de acuerdo a cierta regla. Se pregunta entonces uno, si la serie acabará entrando en uno o más bucles, en los que un conjunto de enteros se va repitiendo periódicamente. Y aunque esto suene difícil de comprender, veámoslo con la "conjetura de Collatz":
Tómese algún número entero positivo. Divídase entre dos si es par; si es impar, multiplíquese por tres y sumémosle uno al producto. Si aplicamos este procedimiento repetidamente, eventualmente llegaremos a uno. Si esto ocurre, diremos que el número inicial con el que empezamos la secuencia es maravilloso.
Por ejemplo, consideremos el número 12. Como es par, dividámoslo entre 2. El resultado es 6. Como este es par, dividámoslo de nuevo entre dos. El resultado es 3. Este último entero es impar, por lo que procedemos a multiplicarlo por tres y al producto sumarle uno. Hallamos que esto da 10. Ahora bien, como 10 es par, dividimos entre 2. Esto nos da 5, que al ser impar, multiplicamos por 3 y le sumamos uno, lo cual da 16. El 16 lo dividimos entre 2 y nos da 8. Siendo par 8, dividimos entre dos y da 4. Este 4 dividido entre 2 es 2 y como éste resultado es par, dividimos entre 2 de nuevo y nos da 1. Por ende, el 12 es un número maravilloso (aunque yo preferiría llamarle
número de Collatz, pues fue quien propuso este problema).
La pregunta fundamental de esta conjetura es la siguiente: Dado cualquier número entero positivo y utilizando el procedimiento descrito, ¿se caerá en a secuencia cíclica 2,1,4,2,1,4,...? Nadie hasta ahora ha podido demostrar que esto ocurra forzosamente. Nadie ha podido, sin embargo, hallar un contraejemplo.
A este problema se le denomina también el problema
3x + 1, el cual se resiste a los esfuerzos por resolverlo. Según Richard guy, fue propuesto antes de la Segunda Guerra Mundial por Lothar Collatz, hoy matemático de la Universidad de Hamburgo
(*), cuando era estudiante. En una conferencia que dio en 1970, H.S.M Coxeter ofreció 50 dólares por una demostración que él pudiera entender y 100 dólares por un contraejemplo. Tal fue el diluvio de falsas demostraciones que Coxeter no está ya dispuesto a evaluarlas. Parece, en efecto, que es tan fácil cometer sutiles errores en las demostraciones de este tipo como en las del último teorema de Fermat (que a todo esto, ya ha sido demostrado, según entiendo). De hecho, Paul Erdös, en 1982, expresó su opinión (¿y cuál más calificada que la suya?) de que si la conjetura es verdadera, la teoría de números carece hoy de instrumental para demostrarla.
Un grupo de investigadores del laboratorio de inteligencia artificial del MIT ha puesto a prueba, mediante computadora, todos los enteros positivos hasta el 60,000,000, sin encontrar una sola excepción. Se descubrió además que si la regla
3n + 1 utilizada cuando es impar se reemplaza por
3n - 1, el resultado, en valores absolutos, es el mismo que si se comenzase con un número entero negativo y se siguiera la antigua regla. En este caso se descubrió que todos los enteres negativos hasta -100,000,000 caían en uno de estos tres bucles:
- 2,1,2,...
- 5,14,7,20,10,5,...
- 17,50,25,74,37,110,55,164,82,41,122 61,182,91,272,136,68,34,17,...
Michael Beemer, William Gosper y Rich Schroeppel dan estor resultados en HACKMEM (abreviatura de Hacker Memo), #239, MIT 1972.
Parece que a nadie se le ha ocurrido una feliz idea que permita establecer el caso general para todos los enteros no nulos (el cero pertenece, evidentemente, al bucle 0,0,0,...). Nadie sabe tampoco si hay enteros que generen sucesiones divergentes hacia infinito carentes de bucle.
Así entonces, si se busca un contraejemplo, éste tendría que ser un número que, o bien, fuese generando números siempre mayores, sin repetir jamás ninguno, o bien, cayese en un bucle distinto al 4,2,1. De existir algún contraejemplo, tendría que ser superlativamente grande, porque según Guy, la conjetura ha sido verificada hasta 7x10^11.
Al poco tiempo de empezar este juego, se descubrió que no era preciso ensayar los números pares, ni tampoco los impares de la forma
4k + 1, 16k + 3 o
128k + 1. De este modo, los programas de computadora se abrevian mucho. Evidentemente, tan pronto como una sucesión tropieza con una potencia de 2, muchas veces, tras una serie caótica de altibajos, se desploma vertiginosamente hacia 4,2,1. La potenbcia de 2 hacia la que más sucesiones convergen es 16.
Entre los números menores de 50, el de peor comportamiento es el 27. Tras 77 pasos alcanza una cima de 9232. Bastan después 34 pasos para reducirlo a 1. Cuando el matemático John H. Conway presenta en sus lecciones la conjetura
3x + 1, le gusta ir a la pizarra y decir: "
tomemos un número al azar, el 27 por ejemplo, y veamos qué sucede".
En el siguiente artículo intentaremos demostrar que la conjetura de Collatz es computacionalmente irreductible, lo cual significa, en otras palabras, que sólo mediante la ejecución explícita para cada número, es posible ver si el número en cuestión es maravilloso o no. Lo que equivaldría a decir que no puede existir una demostración analítica del problema en cuestión.
Lo mejor del asunto es que usaremos la teoría de los autómatas celulares para trabajar con este problema.
(*) Collatz murió en 1990.
