Conjecture de Collatz: Quel est le problème avec cet argument simple pour montrer qu'il n'y a pas de cycles
Je suis tombé sur cet argument lié à la conjecture de Collatz .
Il est clair pour moi que l'argument ne peut être valable. C'est trop simple et si c'était vrai, ce serait largement connu.
J'ai fait de mon mieux pour nettoyer l'argument. Si un point n'est pas clair ou s'il existe un moyen plus simple de faire valoir le même argument, faites-le moi savoir et je serai heureux de le réviser.
Quel est le défaut?
Laisser:
- $C(x)$ être l'opération collatz telle que $C(x) = \dfrac{3x+1}{2^n}$ où $n$ est la puissance la plus élevée de $2$ qui divise $3x+1$.
- $x>1, y\ge 1$ être des entiers distincts et impairs tels que $C(C(C(\dots C(x)\dots) = y$.
- $u_0, u_1, \dots, u_n$ être les résultats intermédiaires entre $x$ et $y$ pour que:
$C(x) = u_n, C(u_n)=C(u_{n-1}), \dots, C(u_1) = u_0, C(u_0) = y$
Prétendre:
Pour deux entiers impairs positifs distincts $x>1, y\ge 1$ où $C(C(C(\dots C(x)\dots) = y$, il n'y a pas de nombres répétés dans la séquence jusqu'à $y$. C'est pour tous$i,j$:
- $u_i = u_j$ iff $i=j$
- $u_i \ne x$
- $u_i \ne y$
Argument:
(1) On peut supposer que $x$ et $y$n'apparaîtra pas comme des valeurs intermédiaires. Autrement dit, pour$i$, $u_i \ne x$ et $u_i \ne y$. Si$x$ étaient une valeur intermédiaire avant $y$, puis $y$ n'a jamais pu être atteint depuis $C(x)$est une fonction et la même entrée donnera la même sortie. Si$y$ étaient une valeur intermédiaire, alors nous pourrions terminer la séquence à ce point.
Remarque: la revendication n'est pas que $y$ ne se répète pas mais qu'il n'y a pas de répétitions jusqu'à $y$. Par exemple, dans le cas où$y=1$, $C(y)=y$. Bien qu'il puisse y avoir des répétitions après$y$, la prétention est qu'il n'y a pas de répétition avant $y$.
(2) Il est clair que $y$ ne peut pas être divisible par $3$ et plus loin que $C(y)=y$ seulement si $y=1$
Clairement, $3 \nmid \dfrac{3x+1}{2^n}$ et $y \ne \dfrac{3y+1}{2^n}$ quand $y \ne 1$
(3) On peut supposer que $C(x) \ne y$. Si$C(x)=y$, alors l'argument est complet puisque $x$ et $y$ sont distincts.
(4) Il existe un entier positif $w > 1$ distinct de $x,y$ où $C(w) = y$
(5) De plus, il existe un nombre infini de $w_i$ où $C(w_i)=y$:
- Laisser $w_{i+1} = 4w_i + 1$
- Clairement, $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}}$
- Clairement, aucun de ces $w_i = x$ puisque nous avons supposé que $C(x) \ne y$ et $C(w_i) = y$ D'après notre hypothèse en (1), aucune de ces $w_i = y$
(6) Supposons que $C(x) \ne w$. Si$C(x)=w$, alors l'argument est complet puisque $x, w, y$ sont distincts.
(7) Il existe un entier positif $v > 1$ distinct de $x, w$ tel que $C(v) = w$. (Distinct de tous$w_i$ ci-dessus depuis $C(w) = y \ne w$)
Remarque: Autres observations:
- Il y a une infinité $v_i$ tel que $C(v_i) = w_i$ pour chaque $w_i$. C'est le même argument que (6).
- Aucun d'eux $v_i = x$ et aucun de ces $v_i = w_i$ et aucun de ces $v_i = y$ depuis $C(y) \ne w$. Quand$y \ne 1$, il est impossible que $C(y) = w$ depuis $C(w) = y$. Quand$y=1$, cela n'est pas possible à partir de l'hypothèse de l'étape (1).
$y = \dfrac{3w_0 + 1}{2^n}$ donc, clairement, $\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 nous prenons $w,v,x,y$ comme cas de base, nous pouvons maintenant supposer que pour tout $x,y$ il existe une séquence de valeurs intermédiaires $u_i$ tel que $C(u_0) = y$, $C(u_1) = u_0$ et ainsi de suite jusqu'à $u_n$ où $C(u_n) = C(u_{n-1})$. Toutes les valeurs sont distinctes.
(9) Pour compléter l'argumentation, il faut montrer qu'il y a forcément $u_{n+1}$ qui a les mêmes propriétés.
(10) D'après notre hypothèse initiale, il existe $u_{n+1}$ tel que $C(u_{n+1}) = u_n$. Nous pouvons en outre supposer que$u_{n+1}$ est distinct de $x$. Sinon, l'argument est déjà prouvé.
(11) Parce que $C(u_{n+1}) = u_n$ et chacun $u_i$ est distinct des autres, il s'ensuit que $u_{n+1}$ est distinct de tout $u_0, u_1, \dots u_n$. Autrement,$C(u_{n+1})$ ne serait pas égal $u_n$. Pour compléter l'argument, il suffit de montrer qu'il est distinct de$y$ ce qui est le cas de notre hypothèse à l'étape (1).
Remarque: supposons que $u_{n+1} = u_j$ où $j < u_{n+1}$, puis $C(u_{n+1}) = C(u_j) = u_{j-1}$ mais $C(u_{n+1}) = u_n$ et par hypothèse $u_n \ne u_{j-1}$ nous avons donc une contradiction et pouvons rejeter l'hypothèse.
Réponses
Le défaut est la déclaration
Nous pouvons supposer que x et y n'apparaîtront pas comme des valeurs intermédiaires. Autrement dit, pour i, ui ≠ x et ui ≠ y. Si x était une valeur intermédiaire avant y, alors y ne pourrait jamais être atteint puisque C (x) est une fonction et la même entrée donnera la même sortie. Si y était une valeur intermédiaire, alors nous pourrions terminer la séquence à ce point.
Ceci n'est valide que si vous essayez réellement de prouver l'affirmation suivante:
Supposer $y \neq x$ et cela $n$ est le moins $n \in \mathbb{N}$ st $y = C^n(x)$ (où $C^n$ signifie appliquer $C$ $n$fois). Ensuite, il n'y a pas de répétition dans la séquence$x, C(x), C^2(x), ..., C^n(x)$.
Cette affirmation est toujours vraie (en fait, on n'a même pas besoin de savoir quoi que ce soit sur $C$pour prouver que c'est vrai). Mais cela ne vous dit absolument rien sur l'existence (ou la non-existence) des cycles.
Pour illustrer ce point, considérons simplement une "version simplifiée" où $C : \{0, 1\} \to \{0, 1\}$ est défini par $C(x) = 1 - x$. La déclaration ci-dessus vaut également lorsque l'on parle de cela$C$, mais il y a clairement un $C$-cycle.