El problema 3n+1 : ciclos de largo 5 (II)

Piste bleue Le 16 novembre 2011  - Ecrit par  Shalom Eliahou
Le 4 juin 2019  - Traduit par  Mariana Haim
Article original : Le problème 3n+1 : cycles de longueur 5 (II) Voir les commentaires
Lire l'article en  

¿La transformación $3n+1$ de Collatz, admite trayectorias cíclicas de largo 5 ? Sí, la de $-5$. Pero la respuesta es negativa para los números positivos. ¿De dónde viene esta diferencia ?

En esta nota sobre el problema $3n+1$ mostramos que no existe ciclo de largo 5 para la transformación de Collatz sobre los naturales.

De hecho, se puede probar más : no existe ningún ciclo de largo comprendido entre 3 y aproximadamente 17 billones, como veremos en un siguiente artículo.

El interés de esta prueba separada para largo 5 es que es bastante elemental, y al mismo tiempo contiene la idea esencial para lo que sigue : muestra una ecuación muy restrictiva asociada a un ciclo. Para ir más lejos, tendremos que aventurarnos basándonos en más conocimientos, equipándonos de logaritmos y aproximaciones racionales ; aquí no precisaremos tanto.

Algunos preliminares

Recordemos la definición de la transformación de Collatz, presentada anteriormente en esta serie [1] : si $n$ es un entero par, lo transformamos en $n/2$ ; si es impar, lo transformamos en $3n+1$.

Representamos esta transformación por una pequeña flecha. Por ejemplo, $10 \rightarrow 5$ (que puede leerse ’’10 va sobre 5’’) y $5 \rightarrow 16$. La regla general se escrbe entonces $n \rightarrow n/2$ o $n \rightarrow 3n+1$, según si $n$ es par o impar, respectivamente.

La trayectoria de $n$ es la sucesión obtenida si se parte de $n$ y se aplica la tranformación de Collatz de manera repetida. Por ejemplo, la trayectoria de 1 es la sucesión 1,4,2,1, 4, ..., que es un ciclo de largo 3.

El problema de Collatz consiste en determinar si es cierto que toda trayectoria tiene necesariamente al 1.

Ciclos en los enteros negativos

La transformación de Collatz puede extenderse a los enteros negativos, con exactamente las mismas fórmulas :

  • si $n$ es par, va sobre $n/2$ ;
  • si $n$ es impar, va sobre $3n+1$.

Por ejemplo, la trayectoria de $-1$ es un ciclo de largo 2 :
\[-1 \rightarrow -2 \rightarrow -1.\]
La trayectoria de $-5$ es otro ciclo, esta vez de largo 5 :

PNG

Regreso a los enteros positivos

¿Podría exisitir un ciclo de largo 5 en los enteros positivos ? La respuesta es negativa. Para probarlo, procederemos por el absurdo : si existiera uno, algunas manipulaciones llevan a una ecuación asociada al ciclo, y se observa que dicha ecuación no tiene solución en los enteros positivos.

El elemento más pequeño en un ciclo

Comencemos por una observación a la vez simple y útil : dado un ciclo de la tranformación de Collatz sobre los enteros positivos, su elemento más pequeño es necesariamente impar.

En efecto, si $m$ fuera par, su transformado sería $m/2$, y tendríamos un elemento del ciclo más pequeño que $m$.

El caso de largo 5

Consideremos ahora un hipotético ciclo de largo 5 en los enteros positivos. Observemos que sus cinco elementos son distintos dos a dos y podemos representarlos así :

PNG - 11.4 ko

.

Renombrando los índices, se puede suponer que el más pequeño es $a_1$, que por lo observado arriba es impar. En particular $a_2=3a_1+1$. Además, $a_1$ es diferente de 1, puesto que la trayectoria de 1 es un ciclo de largo 3. Se tiene entonces que $a_1$ es mayor o igual a 3.

Estabilidad de la transformación de Collatz

Si aplicamos la transformación de Collatz a la lista \[a_1,a_2,a_3,a_4,a_5\] de los elementos del ciclo, obtenemos la misma lista desfasada de un lugar : \[a_2,a_3,a_4,a_5,a_1.\]
Expresamos esto diciendo que el ciclo es estable bajo la transformación de Collatz. Es evidente, pero será crucial en lo que sigue.

Repartición de los partes y de los impares

Para saber concretamente cómo la transformación de Collatz actúa sobre $a_1,\ldots,a_5$, debemos saber cuáles de estos números son pares y cuáles impares. Ya sabemos -por minimalidad de $a_1$ en el ciclo- que $a_1$ es impar. En cuanto a los otros cuatro términos, vamos a demostrar en etapas sucesivas que :

  • $a_2$, $a_4$ y $a_5$ son pares ;
  • $a_3$ es impar.

He aquí la prueba.

(1) Como $a_1$ es impar, se tiene $a_2=3a_1+1$. Entonces $a_2$ es par.

(2) Por lo tanto, $a_3=a_2/2 = (3a_1+1)/{2}$. ¿Podría $a_3$ ser par ? Si fuera el caso, tendríamos $a_4=a_3/2$ y esto daría
\[ \begin{array}{rcl} a_4 & = & \frac{a_3}2\\ & = & \frac{a_2}4\\ & = & \frac{3a_1+1}{4}. \end{array} \]
Pero esto implicaría $a_4 < a_1$, lo que contradice la minimalidad de $a_1$. La hipótesis de que $a_3$ es par conduce, por tanto, a una contradicción. Concluimos que $a_3$ es impar.

(3) Se deduce $a_4=3a_3+1$, por lo que$a_4$ es par. Se sigue que $a_5=a_4/2$.

(4) Para terminar $a_5$ es par. En efecto, tenemos $a_5 > a_1$ y $a_5 \rightarrow a_1$. La única posibilidad es que $a_5$ sea par y que sea $a_1=a_5/2$.

Conocemos ahora la repartición exacta de pares e impares en nuestro ciclo. Resumamos las fórmulas obtenidas en el camino, que expresan cada término del ciclo en función del anterior :
\[ \begin{array}{rcl} a_1 & = & \frac{a_5}{2}\\ a_2 & = & 3a_1+1\\ a_3 & = & \frac{a_2}{2}\\ a_4 & = & 3a_3+1\\ a_5 & = & \frac{a_4}{2}. \end{array} \]

El producto de los términos del ciclo

La etapa siguiente consiste en tomar el producto de estos 5 términos, que llamaremos $P$. Multiplicando las $5$ igualdades de arriba, se obtiene
\[P\, = \, (3a_1+1) \frac{a_2}{2} (3a_3+1) \frac{a_4}{2} \frac{a_5}{2} .\]

Algunas manipulaciones

Esta ecuación contiene informaciones interesantes. Pero para revelarlas, hace falta permitirse algunas manipulaciones algebraicas. Comencemos por multiplicar los denominadores y obtener
\[ a_1 a_2 a_3 a_4 a_5 \, = \, \frac{(3a_1+1) a_2 (3a_3+1) a_4 a_5}{8}. \]
Ahora multipliquemos por $8$ de ambos lados :
\[ 8 a_1 a_2 a_3 a_4 a_5 \, = \, (3a_1+1) (3a_3+1) a_2 a_4 a_5. \]
Podemos dividir todo por $a_2a_4a_5$ que es no nulo, y obtenemos
\[ 8 a_1 a_3 \, = \, (3a_1+1) (3a_3+1). \]
Dividimos ahora por $a_1a_3$, que también es no nulo :
\[ 8 \, = \, \frac{(3a_1+1)}{a_1} \frac{(3a_3+1)}{a_3}. \]
Aplicando la identidad general \[\frac{a+b}c = \frac ac + \frac bc\] a los dos factores del término de la derecha, obtenemos finalmente :

\[ 8 \, = \, (3+\frac1{a_1}) (3+\frac1{a_3}). \]

Es la ecuación anunciada, en su forma depurada, asociada a cualquier ciclo hipotético de largo 5.

Fin de la prueba

Podemos ahora concluir : como $a_1$ y $a_3$ se suponen positivos, la ecuación de arriba no tiene solución, puesto que el término de la derecha es superior a $9$ y el de la izquierda es inferior.

Acabamos de demostrar que la transformación de Collatz no admite ningún ciclo de largo 5 sobre los enteros positivos.

Una aparente contradicción

Hay una rareza para comprender : el desarrollo de arriba sigue siendo válido sobre los enteros negativos, pues basta reemplazar las desigualdades por desigualdades en valor absoluto (por ejemplo, $-1$ es mayor que $-2$, pero en valor absoluto es más pequeño). ¿Cómo es que, a pesar de esto, existe un ciclo de largo 5 en los enteros negativos ?

La explicación de esta aparente contradicción está en el último argumento de la prueba : a pesar de ser incompatible en los enteros positivos, ¡la ecuación asociada admite soluciones en los enteros negativos ! En efecto, pongamos $a_1=-5$ et $a_3=-7$. Un pequeño cálculo muestra que tenemos una igualdad,
\[ 8 \, = \, (3+\frac1{-5}) (3+\frac1{-7}). \]
De hecho, esta solución viene, como era de esperar, de los dos términos impares del ciclo $-5,-14,-7,-20,-10,-5$.

Epílogo

Además de las trayectorias de $-1$ y $-5$, conocemos otro ciclo para la transformación de Collatz sobre los enteros negativos. Es la trayectoria de $-17$, que es de largo 18 :
\[ \begin{array}{l} & -17 \rightarrow -50 \rightarrow-25 \rightarrow-74 \rightarrow-37 \rightarrow-110 \rightarrow -55 \rightarrow-164\\ & \rightarrow-82 \rightarrow-41 \rightarrow-122 \rightarrow-61 \rightarrow -182 \rightarrow-91 \rightarrow-272 \\ & \rightarrow-136 \rightarrow-68 \rightarrow-34 \rightarrow-17 \rightarrow \ldots \end{array} \]

En el próximo artículo de esta serie, excluiremos primero los ciclos de largo 18 sobre los enteros positivos. Haremos esto mediante argumentos análogos a los presentados aquí para largo 5 salvo por una diferencia importante : en largo 18, se vuelve casi imposible conocer la repartición de pares e impares, pues la combinatoria de estos se vuelve muy complicada.

Para sobrellevar esta dificultad, habría que hacer un pequeño salto en la abstracción, introduciendo una notación específica para distinguir a los pares de los impares en un hipotético ciclo.

Solamente en una segunda parte del nuevo artículo invocaremos los logaritmos y la aproximación racional para poder excluir, sobre los enteros positivos, la existencia de ciclos de longitud entre 4 y 17.000.000.000.

Post-scriptum :

El autor agradece a Etienne Ghys y Bruno Martin por sus comentarios, y a Carole Gaboriau por su ayuda técnica. La redacción de Paisajes Matemáticos, así como el autor, agradecen por la atenta relectura a Struffi (seudónimo), P. Levallois, Gandonou Akoudo David, Joël Merker et Gilles Damamme.

Article original édité par Étienne Ghys

Partager cet article

Pour citer cet article :

Mariana Haim — «El problema 3n+1 : ciclos de largo 5 (II)» — Images des Mathématiques, CNRS, 2019

Crédits image :

Image à la une - El autor agradece a Jason Davies, creador del logo.

Commentaire sur l'article

Laisser un commentaire

Forum sur abonnement

Pour participer à ce forum, vous devez vous enregistrer au préalable. Merci d’indiquer ci-dessous l’identifiant personnel qui vous a été fourni. Si vous n’êtes pas enregistré, vous devez vous inscrire.

Connexions’inscriremot de passe oublié ?