Collatz Varsayımı: Döngü olmadığını göstermek için bu basit argümandaki sorun nedir

Question

Collatz Varsayımı ile ilgili bu argümana rastladım .

Benim için argümanın geçerli olamayacağı açık. Çok basit ve doğru olsaydı, herkesçe bilinirdi.

Tartışmayı temizlemek için elimden geleni yaptım. Herhangi bir nokta net değilse veya aynı tartışmayı yapmanın daha basit bir yolu varsa, bana bildirin ve gözden geçirmekten memnuniyet duyarım.

Kusur nedir?

İzin Vermek:

• $C(x)$ Collatz operasyonu olun ki $C(x) = \dfrac{3x+1}{2^n}$ nerede $n$ en yüksek güçtür $2$ bu böler $3x+1$.
• $x>1, y\ge 1$ farklı, tek tamsayılar olacak ki $C(C(C(\dots C(x)\dots) = y$.
• $u_0, u_1, \dots, u_n$ ara sonuçlar olmak $x$ ve $y$ Böylece:

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

İddia:

Herhangi iki farklı pozitif tek tamsayı için $x>1, y\ge 1$ nerede $C(C(C(\dots C(x)\dots) = y$dizide en fazla tekrarlanan sayı yok $y$. Yani herkes için$i,j$:

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

Argüman:

(1) Bunu varsayabiliriz $x$ ve $y$ara değerler olarak görünmez. Yani$i$, $u_i \ne x$ ve $u_i \ne y$. Eğer$x$ önceden bir ara değerdi $y$, sonra $y$ o zamandan beri asla ulaşılamadı $C(x)$bir fonksiyondur ve aynı girdi aynı çıktıya neden olur. Eğer$y$ bir ara değerdi, o zaman diziyi o noktada bitirebiliriz.

Not: İddia öyle değil $y$ tekrarlamıyor ama şu ana kadar tekrar yok $y$. Örneğin,$y=1$, $C(y)=y$. Sonra tekrarlar olabilir$y$iddia şu ki, daha önce hiç tekrar yok $y$.

(2) Açıktır ki $y$ ile bölünemez $3$ ve dahası $C(y)=y$ Yalnızca $y=1$

Açıkça, $3 \nmid \dfrac{3x+1}{2^n}$ ve $y \ne \dfrac{3y+1}{2^n}$ ne zaman $y \ne 1$

(3) Bunu varsayabiliriz $C(x) \ne y$. Eğer$C(x)=y$, o zaman argüman tamamlandığından beri $x$ ve $y$ farklıdır.

(4) Pozitif bir tam sayı var $w > 1$ farklı $x,y$ nerede $C(w) = y$

(5) Dahası, bu türden sonsuz sayıda $w_i$ nerede $C(w_i)=y$:

• İzin Vermek $w_{i+1} = 4w_i + 1$
• Açıkça, $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}}$
• Açıkça, bunların hiçbiri $w_i = x$ bunu varsaydığımızdan beri $C(x) \ne y$ ve $C(w_i) = y$ (1) 'deki varsayımımıza göre, bunların hiçbiri $w_i = y$

(6) Varsayalım ki $C(x) \ne w$. Eğer$C(x)=w$, o zaman argüman tamamlandığından beri $x, w, y$ farklıdır.

(7) Pozitif bir tam sayı var $v > 1$ farklı $x, w$ öyle ki $C(v) = w$. (Her şeyden farklı$w_i$ o zamandan beri yukarıda $C(w) = y \ne w$)

Not: Diğer gözlemler:

• Sonsuz var $v_i$ öyle ki $C(v_i) = w_i$ her biri için $w_i$. Bu, (6) ile aynı argümandır.
• Bunlardan hiçbiri $v_i = x$ ve bunların hiçbiri $v_i = w_i$ ve bunların hiçbiri $v_i = y$ dan beri $C(y) \ne w$. Ne zaman$y \ne 1$imkansız $C(y) = w$ dan beri $C(w) = y$. Ne zaman$y=1$adım (1) 'deki varsayımdan mümkün değildir.

$y = \dfrac{3w_0 + 1}{2^n}$ çok açıkça, $\dfrac{3\frac{3w_0 + 1}{2^n}+1}{2^m} = \dfrac{9w_0 + 3 + 2^n}{2^{n+m}} \ne w_0$

(8) Eğer alırsak $w,v,x,y$ temel durum olarak, şimdi herhangi bir $x,y$ bir dizi ara değer var $u_i$ öyle ki $C(u_0) = y$, $C(u_1) = u_0$ ve böyle devam eder $u_n$ nerede $C(u_n) = C(u_{n-1})$. Tüm değerler farklıdır.

(9) Tartışmayı tamamlamak için, zorunlu olarak $u_{n+1}$ aynı özelliklere sahip.

(10) İlk varsayımımıza göre, $u_{n+1}$ öyle ki $C(u_{n+1}) = u_n$. Ayrıca şunu varsayabiliriz$u_{n+1}$ farklı $x$. Aksi takdirde, argüman zaten kanıtlanmıştır.

(11) Çünkü $C(u_{n+1}) = u_n$ ve her biri $u_i$ diğerlerinden farklıdır, bunu takip eder $u_{n+1}$ hepsinden farklı $u_0, u_1, \dots u_n$. Aksi takdirde,$C(u_{n+1})$ eşit olmaz $u_n$. Argümanı tamamlamak için, sadece bunun farklı olduğunu göstermemiz gerekiyor$y$ (1) adımındaki varsayımımızdan durum budur.

Not: Varsayalım ki $u_{n+1} = u_j$ nerede $j < u_{n+1}$, sonra $C(u_{n+1}) = C(u_j) = u_{j-1}$ fakat $C(u_{n+1}) = u_n$ ve varsayıma göre $u_n \ne u_{j-1}$ bu yüzden bir çelişkimiz var ve bu varsayımı reddedebiliriz.

Answer 1

Kusur ifadesidir

X ve y'nin ara değerler olarak görünmeyeceğini varsayabiliriz. Yani, i, ui ≠ x ve ui ≠ y için. Eğer x, y'den önce bir ara değer olsaydı, o zaman y'ye asla ulaşılamazdı çünkü C (x) bir fonksiyondur ve aynı girdi aynı çıktıyla sonuçlanacaktır. Eğer y bir ara değer olsaydı, diziyi o noktada bitirebilirdik.

Bu, yalnızca aşağıdaki ifadeyi gerçekten kanıtlamaya çalışıyorsanız geçerlidir:

Varsayalım $y \neq x$ ve şu $n$ en az $n \in \mathbb{N}$ st $y = C^n(x)$ (nerede $C^n$ başvurmak anlamına gelir $C$ $n$zamanlar). O zaman dizide tekrar yok$x, C(x), C^2(x), ..., C^n(x)$.

Bu ifade her zaman doğrudur (aslında, kişinin hakkında hiçbir şey bilmesine bile gerek yoktur. $C$bunun doğru olduğunu kanıtlamak için). Ama size döngülerin varlığı (ya da yokluğu) hakkında kesinlikle hiçbir şey söylemez.

Bu noktayı açıklamak için, "basitleştirilmiş bir versiyon" düşünmeniz yeterlidir. $C : \{0, 1\} \to \{0, 1\}$ tarafından tanımlanır $C(x) = 1 - x$. Yukarıdaki ifade, bunun hakkında konuşurken de geçerlidir.$C$ama açıkça var $C$-döngü.