Conjectura de Collatz: Qual é o problema com este argumento simples para mostrar que não há ciclos

Question

Eu me deparei com esse argumento relacionado à conjectura de Collatz .

É claro para mim que o argumento não pode ser válido. É muito simples e, se fosse verdade, seria amplamente conhecido.

Fiz o meu melhor para esclarecer a discussão. Se algum ponto não estiver claro ou se houver uma maneira mais simples de apresentar o mesmo argumento, informe-me e terei o maior prazer em revisar.

Qual é a falha?

Deixei:

• $C(x)$ ser a operação de colaboração de modo que $C(x) = \dfrac{3x+1}{2^n}$ Onde $n$ é o maior poder de $2$ que divide $3x+1$.
• $x>1, y\ge 1$ ser distintos, inteiros ímpares, de modo que $C(C(C(\dots C(x)\dots) = y$.
• $u_0, u_1, \dots, u_n$ ser os resultados intermediários entre $x$ e $y$ de modo a:

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

Afirmação:

Para quaisquer dois inteiros ímpares positivos distintos $x>1, y\ge 1$ Onde $C(C(C(\dots C(x)\dots) = y$, não há números repetidos na sequência até $y$. Ou seja, para todos$i,j$:

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

Argumento:

(1) Podemos assumir que $x$ e $y$não aparecerá como valores intermediários. Ou seja, para$i$, $u_i \ne x$ e $u_i \ne y$. E se$x$ eram um valor intermediário antes $y$, então $y$ nunca poderia ser alcançado desde $C(x)$é uma função e a mesma entrada resultará na mesma saída. E se$y$ fosse um valor intermediário, então poderíamos encerrar a sequência naquele ponto.

Nota: a alegação não é essa $y$ não repete, mas que não há repetições até $y$. Por exemplo, no caso de$y=1$, $C(y)=y$. Embora possa haver repetições após$y$, a alegação é que não há repetições antes $y$.

(2) É claro que $y$ não pode ser divisível por $3$ e além disso $C(y)=y$ somente se $y=1$

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

(3) Podemos assumir que $C(x) \ne y$. E se$C(x)=y$, então o argumento está completo, pois $x$ e $y$ são distintos.

(4) Existe um número inteiro positivo $w > 1$ diferente de $x,y$ Onde $C(w) = y$

(5) Além disso, há um número infinito de tais $w_i$ Onde $C(w_i)=y$:

• Deixei $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, nenhum destes $w_i = x$ desde que assumimos que $C(x) \ne y$ e $C(w_i) = y$ De nossa suposição em (1), nenhum desses $w_i = y$

(6) Suponha que $C(x) \ne w$. E se$C(x)=w$, então o argumento está completo, pois $x, w, y$ são distintos.

(7) Existe um número inteiro positivo $v > 1$ diferente de $x, w$ de tal modo que $C(v) = w$. (Distinto de todos$w_i$ acima desde $C(w) = y \ne w$)

Nota: Outras observações:

• Existe um infinito $v_i$ de tal modo que $C(v_i) = w_i$ para cada $w_i$. Este é o mesmo argumento de (6).
• Nenhum desses $v_i = x$ e nenhum destes $v_i = w_i$ e nenhum destes $v_i = y$ Desde a $C(y) \ne w$. Quando$y \ne 1$, é impossível que $C(y) = w$ Desde a $C(w) = y$. Quando$y=1$, não é possível a partir do pressuposto da etapa (1).

$y = \dfrac{3w_0 + 1}{2^n}$ tão 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) Se tomarmos $w,v,x,y$ como caso básico, podemos agora assumir que, para qualquer $x,y$ existe uma sequência de valores intermediários $u_i$ de tal modo que $C(u_0) = y$, $C(u_1) = u_0$ e assim por diante até $u_n$ Onde $C(u_n) = C(u_{n-1})$. Todos os valores são distintos.

(9) Para completar o argumento, precisamos mostrar que há necessariamente $u_{n+1}$ que tem as mesmas propriedades.

(10) De nossa suposição original, existe $u_{n+1}$ de tal modo que $C(u_{n+1}) = u_n$. Podemos ainda assumir que$u_{n+1}$ é distinto de $x$. Caso contrário, o argumento já está comprovado.

(11) Porque $C(u_{n+1}) = u_n$ e cada $u_i$ é distinto dos outros, segue-se que $u_{n+1}$ é distinto de tudo $u_0, u_1, \dots u_n$. De outra forma,$C(u_{n+1})$ não seria igual $u_n$. Para completar o argumento, só precisamos mostrar que é diferente de$y$ que é o caso de nossa suposição na etapa (1).

Nota: suponha que $u_{n+1} = u_j$ Onde $j < u_{n+1}$, então $C(u_{n+1}) = C(u_j) = u_{j-1}$ mas $C(u_{n+1}) = u_n$ e por suposição $u_n \ne u_{j-1}$ portanto, temos uma contradição e podemos rejeitar a suposição.

Answer 1

A falha é a declaração

Podemos supor que x e y não aparecerão como valores intermediários. Ou seja, para i, ui ≠ x e ui ≠ y. Se x fosse um valor intermediário antes de y, então y nunca poderia ser alcançado, pois C (x) é uma função e a mesma entrada resultará na mesma saída. Se y fosse um valor intermediário, poderíamos encerrar a sequência nesse ponto.

Isso só é válido se você estiver realmente tentando provar a seguinte afirmação:

Suponha $y \neq x$ e essa $n$ é o mínimo $n \in \mathbb{N}$ st $y = C^n(x)$ (Onde $C^n$ significa aplicar $C$ $n$vezes). Então, não há repetições na sequência$x, C(x), C^2(x), ..., C^n(x)$.

Esta afirmação é sempre verdadeira (na verdade, nem é preciso saber nada sobre $C$para provar que isso é verdade). Mas não diz absolutamente nada sobre a existência (ou não) de ciclos.

Para ilustrar este ponto, basta considerar uma "versão simplificada" onde $C : \{0, 1\} \to \{0, 1\}$ é definido por $C(x) = 1 - x$. A afirmação acima também se aplica quando falamos sobre este$C$, mas claramente há um $C$-ciclo.