Conjetura de Collatz: ¿Cuál es el problema con este simple argumento para mostrar que no hay ciclos?

Aug 18 2020

Me encontré con este argumento relacionado con la Conjetura de Collatz .

Para mí está claro que el argumento no puede ser válido. Es demasiado simple y si fuera cierto, sería ampliamente conocido.

He hecho todo lo posible para aclarar la discusión. Si algún punto no está claro o si hay una forma más sencilla de presentar el mismo argumento, avíseme y con gusto lo revisaré.

¿Cuál es el defecto?

Dejar:

  • $C(x)$ ser la operación collatz tal que $C(x) = \dfrac{3x+1}{2^n}$ dónde $n$ es el poder más alto de $2$ que divide $3x+1$.
  • $x>1, y\ge 1$ ser enteros distintos e impares tales que $C(C(C(\dots C(x)\dots) = y$.
  • $u_0, u_1, \dots, u_n$ ser los resultados intermedios entre $x$ y $y$ así que eso:

$C(x) = u_n, C(u_n)=C(u_{n-1}), \dots, C(u_1) = u_0, C(u_0) = y$

Reclamación:

Para dos enteros impares positivos distintos $x>1, y\ge 1$ dónde $C(C(C(\dots C(x)\dots) = y$, no hay números repetidos en la secuencia hasta $y$. Es decir, para todos$i,j$:

  • $u_i = u_j$ si $i=j$
  • $u_i \ne x$
  • $u_i \ne y$

Argumento:

(1) Podemos asumir que $x$ y $y$no aparecerán como valores intermedios. Es decir, para$i$, $u_i \ne x$ y $u_i \ne y$. Si$x$ eran un valor intermedio antes $y$, luego $y$ nunca pudo ser alcanzado desde $C(x)$es una función y la misma entrada dará como resultado la misma salida. Si$y$ fuera un valor intermedio, entonces podríamos finalizar la secuencia en ese punto.

Nota: La afirmación no es que $y$ no se repite pero que no hay repeticiones hasta $y$. Por ejemplo, en el caso donde$y=1$, $C(y)=y$. Si bien puede haber repeticiones después$y$, la afirmación es que no hay repeticiones antes $y$.

(2) Está claro que $y$ no puede ser divisible por $3$ y además que $C(y)=y$ sólo si $y=1$

Claramente, $3 \nmid \dfrac{3x+1}{2^n}$ y $y \ne \dfrac{3y+1}{2^n}$ cuando $y \ne 1$

(3) Podemos asumir que $C(x) \ne y$. Si$C(x)=y$, entonces el argumento está completo ya $x$ y $y$ son distintos.

(4) Existe un entero positivo $w > 1$ distinto de $x,y$ dónde $C(w) = y$

(5) Además, hay un número infinito de tales $w_i$ dónde $C(w_i)=y$:

  • Dejar $w_{i+1} = 4w_i + 1$
  • Claramente, $C(w_{i+1}) = \dfrac{3w_{i+1} + 1}{2^n} = \dfrac{3(4w_i + 1) + 1}{2^n} = \dfrac{12w_i + 4}{2^n} = \dfrac{4(3w_i + 1)}{2^n} = \dfrac{3w_i + 1}{2^{n-2}}$
  • Claramente, ninguno de estos $w_i = x$ ya que asumimos que $C(x) \ne y$ y $C(w_i) = y$ De nuestra suposición en (1), ninguno de estos $w_i = y$

(6) Suponga que $C(x) \ne w$. Si$C(x)=w$, entonces el argumento está completo ya $x, w, y$ son distintos.

(7) Existe un entero positivo $v > 1$ distinto de $x, w$ tal que $C(v) = w$. (Distinto de todos$w_i$ arriba desde $C(w) = y \ne w$)

Nota: Otras observaciones:

  • Hay un infinito $v_i$ tal que $C(v_i) = w_i$ para cada $w_i$. Este es el mismo argumento que (6).
  • Ninguno de esos $v_i = x$ y ninguno de estos $v_i = w_i$ y ninguno de estos $v_i = y$ ya que $C(y) \ne w$. Cuando$y \ne 1$, es imposible que $C(y) = w$ ya que $C(w) = y$. Cuando$y=1$, no es posible a partir del supuesto del paso (1).

$y = \dfrac{3w_0 + 1}{2^n}$ entonces, claramente, $\dfrac{3\frac{3w_0 + 1}{2^n}+1}{2^m} = \dfrac{9w_0 + 3 + 2^n}{2^{n+m}} \ne w_0$

(8) Si tomamos $w,v,x,y$ como caso base, ahora podemos suponer que para cualquier $x,y$ existe una secuencia de valores intermedios $u_i$ tal que $C(u_0) = y$, $C(u_1) = u_0$ y así sucesivamente hasta $u_n$ dónde $C(u_n) = C(u_{n-1})$. Todos los valores son distintos.

(9) Para completar el argumento, necesitamos demostrar que necesariamente hay $u_{n+1}$ que tiene las mismas propiedades.

(10) De nuestra suposición original, existe $u_{n+1}$ tal que $C(u_{n+1}) = u_n$. Además podemos asumir que$u_{n+1}$ es distinto de $x$. De lo contrario, el argumento ya está probado.

(11) Porque $C(u_{n+1}) = u_n$ y cada $u_i$ es distinto de los demás, se sigue que $u_{n+1}$ es distinto de todos $u_0, u_1, \dots u_n$. De otra manera,$C(u_{n+1})$ no igualaría $u_n$. Para completar el argumento, solo tenemos que demostrar que es distinto de$y$ que es el caso de nuestra suposición en el paso (1).

Nota: suponga que $u_{n+1} = u_j$ dónde $j < u_{n+1}$, luego $C(u_{n+1}) = C(u_j) = u_{j-1}$ pero $C(u_{n+1}) = u_n$ y por supuesto $u_n \ne u_{j-1}$ entonces tenemos una contradicción y podemos rechazar la suposición.

Respuestas

8 DoctorWho Aug 19 2020 at 05:05

La falla es la declaración

Podemos suponer que xey no aparecerán como valores intermedios. Es decir, para i, ui ≠ x y ui ≠ y. Si x fuera un valor intermedio antes de y, nunca podría alcanzarse y ya que C (x) es una función y la misma entrada dará como resultado la misma salida. Si y fuera un valor intermedio, entonces podríamos terminar la secuencia en ese punto.

Esto solo es válido si realmente está intentando probar la siguiente afirmación:

Suponer $y \neq x$ y eso $n$ es lo menos $n \in \mathbb{N}$ S t $y = C^n(x)$ (dónde $C^n$ significa aplicar $C$ $n$veces). Entonces no hay repeticiones en la secuencia.$x, C(x), C^2(x), ..., C^n(x)$.

Esta afirmación es siempre cierta (de hecho, uno ni siquiera necesita saber nada sobre $C$para demostrar que esto es cierto). Pero no le dice absolutamente nada sobre la existencia (o inexistencia) de ciclos.

Para ilustrar este punto, simplemente considere una "versión simplificada" donde $C : \{0, 1\} \to \{0, 1\}$ es definido por $C(x) = 1 - x$. La declaración anterior también es válida cuando se habla de esto.$C$, pero claramente hay una $C$-ciclo.