El algoritmo de Syracuse
Original de Adrián Paenza.
Vamos a construir juntos una sucesión de números naturales (enteros positivos). La regla es la siguiente: empezamos por uno cualquiera. Digamos, a manera de ejemplo, que elegimos el número 7. Ese va a ser el primer elemento de nuestra sucesión.
Para generar el segundo elemento, hacemos lo siguiente: si el que elegimos primero es par, lo dividimos por dos. En cambio, si es impar, lo multiplicamos por 3 y le sumamos 1.
En nuestro ejemplo, al haber elegido el 7, como no es par, tenemos que multiplicarlo por 3 y sumarle 1. Es decir, se obtiene el número 22, ya que 3 x 7 = 21 y sumando uno, queda 22.
Ahora bien: tenemos entonces los primeros dos elementos de nuestra sucesión: {7,22}.
Para generar el tercer número de la sucesión, como el 22 es un número par, lo dividimos por dos, y obtenemos 11. Ahora tenemos {7,22,11}.
Como 11 es impar, la regla dice “multiplíquelo por 3 y súmele 1”. O sea, 34. Se tiene {7,22,11,34}.
Luego, como 34 es par, el próximo elemento de la sucesión es 17. Y el siguiente es 52. Luego 26. Y después 13. Y sigue 40. Luego 20. Hasta acá tenemos {7,22,11,34,17,52,26,13,40,20}.
Seguimos dividiendo por dos los pares y multiplicando por 3 y sumando 1 a los impares: {7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1}.
Y en el número 1, paramos.
Lo invito ahora a que elijamos cualquier otro número para empezar, digamos el 24. La sucesión que se tiene es: {24, 12, 6, 3, 10, 5, 16, 8, 4, 2, 1}.
Si ahora empezamos con el 100, se sigue: {100, 50, 25, 76, 38, 19, 58, 29, 88, 44, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1}.
Como se alcanza a ver, todas las sucesiones que elegí terminan en el número 1. En realidad, aunque no lo dije antes, al llegar al número 1 el proceso se detiene, porque si uno siguiera, entraría en un lazo, ya que del 1 pasaría al 4, del 4 al 2 y del 2 → 1. Por eso es que cuando al construir la sucesión llegamos al número uno, detenemos el proceso. En este enlace puedes introducir el número que quieras para comprobar esta conjetura, y comprobar que siempre se llega a uno (no me he fijado el límite del número elegido).
Bien. Hasta hoy, julio de 2016, en todos los ejemplos conocidos siempre se termina la sucesión en el número 1. Pero, no se tiene ninguna demostración que pruebe que el resultado es válido para cualquier número. Este problema se conoce con el nombre del “Problema 3x + 1”, o también como el “Problema de Collatz”, o “Problema de Syracuse”, o “Problema de Kakutani” o “Algoritmo de Hasse” o “Problema de Ulam”.
Como ven, tiene muchos nombres, pero ninguna solución. Es una buena oportunidad para empezar. Con todo, así como escribí el otro día respecto de la Conjetura de Goldbach, es poco probable que a un “lego” se le ocurra cómo resolver el problema general. Pero, en la historia de la humanidad hay múltiples ejemplos de personas que tuvieron el ingenio suficiente para superar dificultades para la que se suponía que no estaban preparadas. Y lo hicieron, casi sin historia en el área ni herramientas sofisticadas.
La conjetura de Collatz http://t.co/TBmxQ3mYZt— ZTF-FCT (@ztf_fct) 7 de julio de 2013
Fuentes para investigar
La conjetura de Collatz. En Gaussianos.
Collatz Conjecture (en inglés). En Wikipedia.
Collatz Problem (en Wolfram).
Artículo: Is this the simplest unprovable math problem ever?.
Escuchar a Raúl Ibañez en: La conjetura de Collatz (audio).
[VIDEO] La Conjetura de Collatz
No hay comentarios:
Publicar un comentario