Congettura di Collatz: Qual è il problema con questo semplice argomento per dimostrare che non ci sono cicli

Question

Mi sono imbattuto in questo argomento relativo alla congettura di Collatz .

Mi è chiaro che l'argomento non può essere valido. È troppo semplice e se fosse vero sarebbe ampiamente conosciuto.

Ho fatto del mio meglio per chiarire l'argomento. Se un punto non è chiaro o se esiste un modo più semplice per sostenere lo stesso argomento, fammelo sapere e sarò lieto di rivedere.

Qual è il difetto?

Permettere:

• $C(x)$ essere l'operazione collatz tale che $C(x) = \dfrac{3x+1}{2^n}$ dove $n$ è il più alto potere di $2$ che divide $3x+1$.
• $x>1, y\ge 1$ essere numeri interi distinti e dispari tali che $C(C(C(\dots C(x)\dots) = y$.
• $u_0, u_1, \dots, u_n$ essere i risultati intermedi tra $x$ e $y$ così che:

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

Richiesta:

Per due numeri interi dispari positivi distinti $x>1, y\ge 1$ dove $C(C(C(\dots C(x)\dots) = y$, non ci sono numeri ripetuti nella sequenza fino a $y$. Cioè, per tutti$i,j$:

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

Discussione:

(1) Possiamo presumere che $x$ e $y$non appariranno come valori intermedi. Cioè, per$i$, $u_i \ne x$ e $u_i \ne y$. Se$x$ erano un valore intermedio prima $y$, poi $y$ da allora non potrà mai essere raggiunto $C(x)$è una funzione e lo stesso input risulterà nello stesso output. Se$y$ fossero un valore intermedio, quindi potremmo terminare la sequenza in quel punto.

Nota: l'affermazione non è quella $y$ non si ripete ma che non ci sono ripetizioni fino a $y$. Ad esempio, nel caso in cui$y=1$, $C(y)=y$. Mentre potrebbero esserci ripetizioni dopo$y$, l'affermazione è che non ci sono ripetizioni prima $y$.

(2) È chiaro che $y$ non può essere divisibile per $3$ e oltre $C(y)=y$ solo se $y=1$

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

(3) Possiamo presumere che $C(x) \ne y$. Se$C(x)=y$, quindi l'argomento è completo da allora $x$ e $y$ sono distinti.

(4) Esiste un numero intero positivo $w > 1$ distinto da $x,y$ dove $C(w) = y$

(5) Inoltre, ce ne sono un numero infinito $w_i$ dove $C(w_i)=y$:

• Permettere $w_{i+1} = 4w_i + 1$
• Chiaramente, $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}}$
• Chiaramente, nessuno di questi $w_i = x$ dato che lo abbiamo ipotizzato $C(x) \ne y$ e $C(w_i) = y$ Dalla nostra ipotesi in (1), nessuno di questi $w_i = y$

(6) Assumilo $C(x) \ne w$. Se$C(x)=w$, quindi l'argomento è completo da allora $x, w, y$ sono distinti.

(7) Esiste un numero intero positivo $v > 1$ distinto da $x, w$ tale che $C(v) = w$. (Distinto da tutto$w_i$ sopra da allora $C(w) = y \ne w$)

Nota: altre osservazioni:

• Ce ne sono infiniti $v_i$ tale che $C(v_i) = w_i$ per ciascuno $w_i$. Questo è lo stesso argomento di (6).
• Nessuno di questi $v_i = x$ e nessuno di questi $v_i = w_i$ e nessuno di questi $v_i = y$ da $C(y) \ne w$. quando$y \ne 1$, è impossibile $C(y) = w$ da $C(w) = y$. quando$y=1$, non è possibile dal presupposto nella fase (1).

$y = \dfrac{3w_0 + 1}{2^n}$ quindi, chiaramente, $\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 prendiamo $w,v,x,y$ come caso base, ora possiamo assumerlo per any $x,y$ esiste una sequenza di valori intermedi $u_i$ tale che $C(u_0) = y$, $C(u_1) = u_0$ e così via fino a $u_n$ dove $C(u_n) = C(u_{n-1})$. Tutti i valori sono distinti.

(9) Per completare l'argomento, dobbiamo dimostrare che esiste necessariamente $u_{n+1}$ che ha le stesse proprietà.

(10) Dalla nostra ipotesi originale, esiste $u_{n+1}$ tale che $C(u_{n+1}) = u_n$. Possiamo ulteriormente supporlo$u_{n+1}$ è distinto da $x$. Altrimenti, l'argomento è già dimostrato.

(11) Perché $C(u_{n+1}) = u_n$ e ciascuno $u_i$ è distinto dagli altri, ne consegue $u_{n+1}$ è distinto da tutti $u_0, u_1, \dots u_n$. Altrimenti,$C(u_{n+1})$ non sarebbe uguale $u_n$. Per completare l'argomento, dobbiamo solo dimostrare che è distinto da$y$ che è il caso dalla nostra ipotesi nel passaggio (1).

Nota: supponi che $u_{n+1} = u_j$ dove $j < u_{n+1}$, poi $C(u_{n+1}) = C(u_j) = u_{j-1}$ ma $C(u_{n+1}) = u_n$ e per ipotesi $u_n \ne u_{j-1}$ quindi abbiamo una contraddizione e possiamo rifiutare l'ipotesi.

Answer 1

Il difetto è l'affermazione

Possiamo supporre che xey non appariranno come valori intermedi. Cioè, per i, ui ≠ x e ui ≠ y. Se x fosse un valore intermedio prima di y, allora y non potrebbe mai essere raggiunto poiché C (x) è una funzione e lo stesso input risulterà nello stesso output. Se y fosse un valore intermedio, allora potremmo terminare la sequenza in quel punto.

Questo è valido solo se stai effettivamente cercando di dimostrare la seguente affermazione:

Supponiamo $y \neq x$ e quello $n$ è il minimo $n \in \mathbb{N}$ st $y = C^n(x)$ (dove $C^n$ significa applicare $C$ $n$volte). Quindi non ci sono ripetizioni nella sequenza$x, C(x), C^2(x), ..., C^n(x)$.

Questa affermazione è sempre vera (infatti, non è nemmeno necessario sapere nulla di $C$per dimostrare che questo è vero). Ma non ti dice assolutamente nulla sull'esistenza (o non esistenza) dei cicli.

Per illustrare questo punto, si consideri semplicemente una "versione semplificata" dove $C : \{0, 1\} \to \{0, 1\}$ è definito da $C(x) = 1 - x$. La dichiarazione di cui sopra vale anche quando si parla di questo$C$, ma chiaramente esiste un file $C$-ciclo.