Autor Tema: Conjetura de Collatz

0 Usuarios y 1 Visitante están viendo este tema.

25 Mayo, 2015, 02:20 pm
Leído 4909 veces

inriki

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 3
  • Karma: +0/-0
  • Sexo: Masculino
Buenos días

Creo haber encontrado una demostración valida para la conjetura de Collatz que me gustaría compartir y conocer vuestra opinión (por favor no seais muy duros conmigo, no soy matemático ;))

La conjetura de Collatz dice que para cualquier n mayor que 0
- Si n es par n1 = n / 2
- Si n es impar n1 = n * 3 +1
Sea cual sea n la serie termina con la repetición de los términos 4, 2, 1, 4, 2, 1…

Pues bien, se cumple que
para cualquier n par, n1 es menor que n
Si para un n impar (n – 1) % 4 = 0, entonces n3 es menor que n
Si para un n impar (n – 1) % 4 ≠ 0
- Si (n – 1) % (2 * (2 ^ 2)) = (2 ^ 2) - 2, entonces (n2 – 1) % (2 ^ 2) = (2 ^ 1) - 2
- Si (n – 1) % (2 * (2 ^ 3)) = (2 ^ 3) - 2, entonces (n2 – 1) % (2 ^ 3) = (2 ^ 2) – 2
- Y en general si (n – 1) % (2 * (2 ^ X)) = (2 ^ X) - 2, entonces (n2 – 1) % (2 ^ X) = (2 ^ (X – 1)) – 2
Esto demuestra que en la secuencia n, …, o, …, p, … de cualquier número ‘n’ existe un número ‘p’ menor que ‘o’, lo que hace que la secuencia siempre termine por llegar al número 1.

Ejemplo con n = 27,
(27 – 1) % 4 ≠ 0
(27 – 1) % 8 = 2, por lo que se ha de cumplir que (n2 – 1) % 4 = 0
n1 = 27 * 3 + 1, n1 = 82
n2 = 82 / 2, n2 = 41, y se cumple que (41 – 1) % 4 = 0, por lo que se ha de cumplir que n5 es menor que n2
n3 = 41 * 3 + 1, n3 = 124
n4 = 124 / 2, n4 = 62
n5 = 62 / 2, n5 = 31 y se cumple que es menor que 41

Demostrar la conjetura para cualquier número ‘n’ es lo mismo que demostrarla para el número ‘o’, lo que es lo mismo que demostrarla para el número ‘p’, como ‘p’ es menor que ‘o’ la serie siempre termina por llegar al número 1

Como demostración formal no es muy elegante pero a mi me parece que es valida ¿no?

25 Mayo, 2015, 07:22 pm
Respuesta #1

argentinator

  • Consultar la FIRMAPEDIA
  • Administrador
  • Mensajes: 7,346
  • País: ar
  • Karma: +0/-0
  • Sexo: Masculino
  • Vean mis posts activos en mi página personal
    • Mis posts activos (click aquí)
[Tuve que borrar mi anterior mensaje, estaba demasiado mal.]

Buenos días

Creo haber encontrado una demostración valida para la conjetura de Collatz que me gustaría compartir y conocer vuestra opinión (por favor no seais muy duros conmigo, no soy matemático ;))

La conjetura de Collatz dice que para cualquier n mayor que 0
- Si n es par n1 = n / 2
- Si n es impar n1 = n * 3 +1
Sea cual sea n la serie termina con la repetición de los términos 4, 2, 1, 4, 2, 1…

Pues bien, se cumple que
para cualquier n par, n1 es menor que n
Si para un n impar (n – 1) % 4 = 0, entonces n3 es menor que n
Si para un n impar (n – 1) % 4 ≠ 0
- Si (n – 1) % (2 * (2 ^ 2)) = (2 ^ 2) - 2, entonces (n2 – 1) % (2 ^ 2) = (2 ^ 1) - 2
- Si (n – 1) % (2 * (2 ^ 3)) = (2 ^ 3) - 2, entonces (n2 – 1) % (2 ^ 3) = (2 ^ 2) – 2
- Y en general si (n – 1) % (2 * (2 ^ X)) = (2 ^ X) - 2, entonces (n2 – 1) % (2 ^ X) = (2 ^ (X – 1)) – 2
Esto demuestra que en la secuencia n, …, o, …, p, … de cualquier número ‘n’ existe un número ‘p’ menor que ‘o’, lo que hace que la secuencia siempre termine por llegar al número 1.

Ejemplo con n = 27,
(27 – 1) % 4 ≠ 0
(27 – 1) % 8 = 2, por lo que se ha de cumplir que (n2 – 1) % 4 = 0
n1 = 27 * 3 + 1, n1 = 82
n2 = 82 / 2, n2 = 41, y se cumple que (41 – 1) % 4 = 0, por lo que se ha de cumplir que n5 es menor que n2
n3 = 41 * 3 + 1, n3 = 124
n4 = 124 / 2, n4 = 62
n5 = 62 / 2, n5 = 31 y se cumple que es menor que 41

Demostrar la conjetura para cualquier número ‘n’ es lo mismo que demostrarla para el número ‘o’, lo que es lo mismo que demostrarla para el número ‘p’, como ‘p’ es menor que ‘o’ la serie siempre termina por llegar al número 1

Como demostración formal no es muy elegante pero a mi me parece que es valida ¿no?


Hola, me cuesta entenderlo porque estás usando una notación mezcla de programación en Pascal con frases en castellano, y notación de secuencias con letras, muy a la antigua.
Primero intentaré traducir a notación matemática tu razonamiento, aunque ya estoy viendo una inferencia que está mal.

La conjetura de Collatz dice que para cualquier \( n\in\mathbb N \), o sea, \( n \) entero y \( n > 0 \).
(Precisar que es entero y positivo es importante para las demostraciones por descenso, como la que has expuesto).

Partimos de un elemento inicial de la sucesión, denotando \( n_1=n \).
Ahora, dado un índice \( k\geq 1 \):
- Si \( n_k \) es par, se define \( n_{k+1} = n / 2 \).
- Si \( n_k \) es impar se define \( n_{k+1} = 3n_k+1 \).
Sea cual sea \( n \) la sucesión termina con la repetición de los términos 4, 2, 1, 4, 2, 1…
(En castellano se dice "sucesión" o "secuencia", pero no "serie", que se reserva para sucesiones de sumas parciales).

Luego dices que:

Para cualquier \( n_k \) par, \( n_{k+1} \) es menor que \( n_k \).
Esto es verdad.
Pero también es importante decir que \( n_{k+1} \) es todavía un entero positivo. Con lo cual escribimos:

\( n_k\in \mathbb N \)  y par, implica \( n_{k+1}\in\mathbb N \) y \( n_{k+1}<n_k \).
--------

Si para un \( n_k \) impar \( n_k- 1\equiv 0 (\mod 4) \), entonces \( n_{k+3}<n_k \).
(Ahí estoy adivinando lo que quisiste decir, o sea, parece que n3 < n quiere decir el elemento generado después de 3 pasos siguiendo a n).
Eso no es verdad del todo, pero casi, pues:
\( n_{k+1}=3n_k+1 \) (es par, y más aún, multiplo de 4, pues \( 3n_k+1\equiv 3+1\equiv 0(\mod 4) \)),
\( n_{k+2}=(3n_k+1)/2 \) (es múltiplo de 2),
\( n_{k+3}=(3n_{k}+1)/4\leq (3n_k+n_k) / 4 \leq n_k \) (hemos usado que \( n_k\geq 1 \)).

En conclusión, hemos obtenido que \( n_{k+3}\leq n_k \).
No puede concluirse que la desigualdad es estricta, porque si vamos a pensar que el caso típico es el final de la sucesión teniendo
algún \( n_k=1 \), allí vale que \( n_{k+3}=n_k=1 \).

Aquí estaría el principal fallo, porque la subsucesión obtenida, que va de 3 en 3: \( n_{k},n_{k+3},n_{n+6} \), no se puede asegurar que sea estrictamente decreciente.

Supongamos por un momento que \( n_k>1 \), o sea, estrictamente mayor que 1.
En ese caso,

\( (3n_k+1)/4 = (3((n_k-1)+1))/ 4 \leq (3(n_k-1)+1)/4 + 1/4 \leq (n_k-1) + 1/4 < n_k. \)

Así que tu afirmación es cierta siempre que \( n_k \) sea mayor que 1.
-------

Si para un \( n_k \) impar \( n_k - 1 \not\equiv 0(\mod 4) \),
esto es equivalente a decir que el resto de \( n_k \) dividido 4 es 3: \( n\equiv 3(\mod 4) \).

- Si \( (n_k-1) \equiv (2 ^ 2)-2(\mod 2 (2 ^ 2)) \),
esto quiere decir que \( n_k \equiv 3 (\mod 8) \),
entonces \( n_{k+2}-1 \equiv (2 ^ 1)-2 (\mod 2 ^ 2) \),
lo cual quiere decir que \( n_{k+2}\equiv 1 \mod 4 \).
Esto es cierto, porque \( n_k \) era impar, y entonces
\( n_{k+1} = 3n_k + 1 \equiv 3\cdot 3 + 1 \equiv 10 \equiv 2 (\mod 8) \), con lo cual \( n_{k+1} \) es par,
dando:

\( n_{k+2} = n_{k+1} / 2 \equiv 1 (\mod 8) \),

lo cual implica de paso que \( n_{k+2}\equiv 1 \mod 4 \).

---

Si \( (n_k-1) \equiv (2 ^ 3) - 2 )\mod 2(2 ^ 3))  \),
esto quiere decir que \( n_k\equiv 5 (\mod 16) \) ¿por qué no módulo 8?
entonces \( (n_{k+2}-1) \equiv (2 ^ 2)-2 (\mod 2 ^ 3) \),
lo cual significa que \( n_{k+2}\equiv 3 (\mod 8) \).
Veamos si esto es cierto:
Como \( n_k \) es impar, resulta:
\( n_{k+1} = 3n_k+1 \equiv 16 \equiv 0 (\mod 16) \), dando que \( n_{k+1} \) es múltiplo de 16,
y por lo tanto
\( n_{k+2}=n_{k+1}/2 \) es par.

Por lo tanto en este caso no llego a la misma conclusión que tú has llegado.


Luego, tampoco puedo generalizar el último párrafo.


A partir de allí ya no puedo seguirte.
Saludos.

26 Mayo, 2015, 11:44 am
Respuesta #2

inriki

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 3
  • Karma: +0/-0
  • Sexo: Masculino
Hola Argentinator, en primer lugar gracias por tu respuesta.

Intentaré usar nomenclatura más formal,

básicamente lo que digo es que que para \( n\in\mathbb N \), impar y \( n > 1 \) se cumple alguna de las siguientes condiciones

Si \( n_k \equiv 1\mod 4 \), entonces \( n_{k+3}<n_k \)
Si no, Si \( n_k \equiv 3\mod 8 \), entonces \( n_{k+5}<n_{k+2} \)
Si no, Si \( n_k \equiv 7\mod 16 \), entonces \( n_{k+7}<n_{k+4} \)
Si no, Si \( n_k \equiv 15\mod 32 \), entonces \( n_{k+9}<n_{k+6} \)
Si no, Si \( n_k \equiv 31\mod 64 \), entonces \( n_{k+11}<n_{k+8} \)
Si no, Si \( n_k \equiv 63\mod 128 \), entonces \( n_{k+13}<n_{k+10} \)
...
Si no, Si \( n_k \equiv (2^x-1)(\mod 2^x^+^1) \), entonces \( n_{k+(2*x+1)}<n_{k+(2*x-2)} \)


Lo que trato de hacer es encontrar en la sucesión un elemento \( n_{k+x} \) que sea menor que \( n_{k+x-3} \)

Demostrar que la conjetura es válida para \( n_k \) es lo mismo que demostrarla para \( n_{k+x-3} \) ya que es un elemento de la sucesión, y lo mismo pasa con \( n_{k+x} \).

Pongamos por ejemplo que ya se ha demostrado que para todos los números menores \( n_{k+x-3} \) se cumple la conjetura, en este caso  \( n_{k+x} \) ya esta demostrado porque es menor.

Es una solución por recursividad que me cuesta explicar formalmente, espero que se pueda coger la idea.

Un saludo

26 Mayo, 2015, 12:08 pm
Respuesta #3

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 49,051
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

básicamente lo que digo es que que para \( n\in\mathbb N \), impar y \( n > 1 \) se cumple alguna de las siguientes condiciones

Si \( n_k \equiv 1\mod 4 \), entonces \( n_{k+3}<n_k \)
Si no, Si \( n_k \equiv 3\mod 8 \), entonces \( n_{k+5}<n_{k+2} \)
Si no, Si \( n_k \equiv 7\mod 16 \), entonces \( n_{k+7}<n_{k+4} \)
Si no, Si \( n_k \equiv 15\mod 32 \), entonces \( n_{k+9}<n_{k+6} \)
Si no, Si \( n_k \equiv 31\mod 64 \), entonces \( n_{k+11}<n_{k+8} \)
Si no, Si \( n_k \equiv 63\mod 128 \), entonces \( n_{k+13}<n_{k+10} \)
...
Si no, Si \( n_k \equiv (2^x-1)(\mod 2^x^+^1) \), entonces \( n_{k+(2*x+1)}<n_{k+(2*x-2)} \)


Lo que trato de hacer es encontrar en la sucesión un elemento \( n_{k+x} \) que sea menor que \( n_{k+x-3} \)

Demostrar que la conjetura es válida para \( n_k \) es lo mismo que demostrarla para \( n_{k+x-3} \) ya que es un elemento de la sucesión, y lo mismo pasa con \( n_{k+x} \).

Pongamos por ejemplo que ya se ha demostrado que para todos los números menores \( n_{k+x-3} \) se cumple la conjetura, en este caso  \( n_{k+x} \) ya esta demostrado porque es menor.

Es una solución por recursividad que me cuesta explicar formalmente, espero que se pueda coger la idea.

Si dado un número cualquiera eres capaz de probar que en un número finito de pasos el algoritmo de Collatz lo convierte en un número más pequeño que el original, desde luego la conjetura está probada.

Eso equivaldría a partir de un \( n_k \) y probar que siempre puedes encontrar un \( n_{k+x} \) menor que \( n_k \). Pero tu no haces eso, tu pruebas que avanzando un poco más en la sucesión encuentras un \( n_{k+x+3} \) más pequeño que \( n_{k+x} \), pero lo que interesa es compararlo con el \( n_k \) inicial. Si no, no podemos concluir nada.

Saludos.

26 Mayo, 2015, 02:11 pm
Respuesta #4

inriki

  • $$\Large \color{#6a84c0}\pi$$
  • Mensajes: 3
  • Karma: +0/-0
  • Sexo: Masculino
Claro, pero probar que para \( n_k \) la conjetura es cierta es lo mismo que probarlo para \( n_{k+x} \) ya que es un termino de la sucesión, lo que yo planteo es una solución recursiva en la que si para cualquier termino de la sucesión se demuestra la conjetura, queda confirmada para todos los siguientes términos y también para los anteriores.

Es decir si sabemos que para n = 7 la sucesión es
7, 22, 11, 34, 17, 52, 26, 13, 40, 20, 10, 5, 16, 8, 4, 2, 1

Y quiero demostrar que la conjetura es valida también para n = 9 no necesito calcular toda la sucesión ya que el termino \( n_3 \) es 7 y para ese termino ya ha quedado demostrada la conjetura.
9, 28, 14, 7


Otra cosa, es posible calcular el termino \( n_k \equiv 1\mod 4 \)

Si \( n \equiv 3\mod 8 \), entonces \( n_k \equiv 1\mod 4 \equiv (n*9+3)/4+1/2 \)
Si no, Si \( n \equiv 7\mod 16 \), entonces \( n_k \equiv 1\mod 4 \equiv (n*27+9)/8+5/4 \)
...
Si no, Si \( n \equiv (2^x-1)(\mod 2^{x+1}) \), entonces \( n_k \equiv 1\mod 4 \equiv (n*3^{x-1}*3^{x-2})/2^{x-1}+\displaystyle\sum_{i=1}^{i=x-2}{3^{i-1}/2^i} \)

Un saludo

26 Mayo, 2015, 06:41 pm
Respuesta #5

Luis Fuentes

  • el_manco
  • Administrador
  • Mensajes: 49,051
  • País: es
  • Karma: +0/-0
  • Sexo: Masculino
Hola

Claro, pero probar que para \( n_k \) la conjetura es cierta es lo mismo que probarlo para \( n_{k+x} \) ya que es un termino de la sucesión, lo que yo planteo es una solución recursiva en la que si para cualquier termino de la sucesión se demuestra la conjetura, queda confirmada para todos los siguientes términos y también para los anteriores.

Es cierto que si tu pruebas que para \( n_{k+x} \) la conjetura es cierta, también lo es comenzando en cualquier término anterior de la sucesión.

Pero el problema es que tu no das realmente un argumento que pueda ser usado de manera recursiva para probar la conjetura para cualquier natural \( n \).

Vuelvo a repetir mi crítica: partes de un \( n_k=n \) y pruebas que más adelante habrá un término \( n_{k+x} \) que decrece posteriormente a otro \( n_{k+x+3} \). Pero si no pruebas que\(  n_{k+x+3}<n_k \) no hay manera de aplicar la recursividad. Fíjate que una sucesión puede tener ese comportamiento y crecer hasta el infinito. Por ejemplo:

\( 2,4,\color{red}8,7,\color{black}16,32,\color{red}64,63,\color{black},128,256,\color{red}512,511,\color{black},\ldots \)

En rojo está marcados un par de números donde se produce un decrecimiento momentáneo de la sucesión; dado cualquier \( n_k \) siempre existe un posterior \( n_{k+x} \) y un \( n_{k+x+1} \) donde la sucesión decrece; pero sin embargo en conjunto la sucesión diverge a infinito.

Con los argumentos que has expuesto y sin añadir algún otro razonamiento, no podemos asegurar que la sucesión de Collatz no pudiese tener ese tipo de comportamiento.

Saludos.