Dugaan Collatz: Apa masalah dengan argumen sederhana ini yang menunjukkan tidak ada siklus

Aug 18 2020

Saya menemukan argumen ini terkait dengan Dugaan Collatz .

Jelas bagi saya bahwa argumen tersebut tidak valid. Itu terlalu sederhana dan jika itu benar, itu akan diketahui secara luas.

Saya telah melakukan yang terbaik untuk membersihkan argumen tersebut. Jika ada poin yang tidak jelas atau jika ada cara yang lebih sederhana untuk membuat argumen yang sama, beri tahu saya dan saya akan dengan senang hati merevisi.

Apa kekurangannya?

Membiarkan:

  • $C(x)$ menjadi operasi collatz seperti itu $C(x) = \dfrac{3x+1}{2^n}$ dimana $n$ adalah kekuatan tertinggi $2$ yang membagi $3x+1$.
  • $x>1, y\ge 1$ menjadi berbeda, bilangan bulat ganjil seperti itu $C(C(C(\dots C(x)\dots) = y$.
  • $u_0, u_1, \dots, u_n$ menjadi hasil antara $x$ dan $y$ yang seperti itu:

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

Klaim:

Untuk dua bilangan bulat ganjil positif yang berbeda $x>1, y\ge 1$ dimana $C(C(C(\dots C(x)\dots) = y$, tidak ada nomor yang berulang dalam urutan hingga $y$. Itu untuk semua$i,j$:

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

Argumen:

(1) Kita dapat berasumsi demikian $x$ dan $y$tidak akan muncul sebagai nilai perantara. Artinya, untuk$i$, $u_i \ne x$ dan $u_i \ne y$. Jika$x$ adalah nilai menengah sebelumnya $y$, kemudian $y$ tidak pernah bisa dihubungi sejak itu $C(x)$adalah fungsi dan masukan yang sama akan menghasilkan keluaran yang sama. Jika$y$ adalah nilai perantara, maka kita bisa mengakhiri urutan pada saat itu.

Catatan: Klaimnya bukan itu $y$ tidak berulang tetapi tidak ada pengulangan hingga $y$. Misalnya dalam kasus dimana$y=1$, $C(y)=y$. Meskipun mungkin ada pengulangan setelahnya$y$, klaimnya adalah bahwa tidak ada pengulangan sebelumnya $y$.

(2) Jelas itu $y$ tidak bisa habis dibagi $3$ dan selanjutnya $C(y)=y$ hanya jika $y=1$

Jelas, $3 \nmid \dfrac{3x+1}{2^n}$ dan $y \ne \dfrac{3y+1}{2^n}$ kapan $y \ne 1$

(3) Kita dapat berasumsi demikian $C(x) \ne y$. Jika$C(x)=y$, maka argumennya selesai sejak $x$ dan $y$ berbeda.

(4) Ada bilangan bulat positif $w > 1$ berbeda dari $x,y$ dimana $C(w) = y$

(5) Selanjutnya, ada jumlah yang tidak terbatas $w_i$ dimana $C(w_i)=y$:

  • Membiarkan $w_{i+1} = 4w_i + 1$
  • Jelas, $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}}$
  • Jelas, tidak satupun dari ini $w_i = x$ sejak kami berasumsi itu $C(x) \ne y$ dan $C(w_i) = y$ Dari asumsi kami di (1), tidak satupun dari ini $w_i = y$

(6) Asumsikan bahwa $C(x) \ne w$. Jika$C(x)=w$, maka argumennya selesai sejak $x, w, y$ berbeda.

(7) Ada bilangan bulat positif $v > 1$ berbeda dari $x, w$ seperti yang $C(v) = w$. (Berbeda dari semua$w_i$ di atas sejak $C(w) = y \ne w$)

Catatan: Pengamatan lain:

  • Ada yang tak terbatas $v_i$ seperti yang $C(v_i) = w_i$ untuk setiap $w_i$. Ini adalah argumen yang sama dengan (6).
  • Tak ada satupun $v_i = x$ dan tidak satupun dari ini $v_i = w_i$ dan tidak satupun dari ini $v_i = y$ sejak $C(y) \ne w$. Kapan$y \ne 1$, tidak mungkin itu $C(y) = w$ sejak $C(w) = y$. Kapan$y=1$, tidak mungkin dari asumsi pada langkah (1).

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

(8) Jika kita ambil $w,v,x,y$ sebagai kasus dasar, sekarang kita dapat mengasumsikannya untuk semua $x,y$ ada urutan nilai antara $u_i$ seperti yang $C(u_0) = y$, $C(u_1) = u_0$ dan seterusnya sampai $u_n$ dimana $C(u_n) = C(u_{n-1})$. Semua nilai berbeda.

(9) Untuk melengkapi argumen, kita perlu menunjukkan bahwa memang ada $u_{n+1}$ yang memiliki sifat yang sama.

(10) Dari asumsi awal kami, ada $u_{n+1}$ seperti yang $C(u_{n+1}) = u_n$. Kami selanjutnya dapat berasumsi bahwa$u_{n+1}$ berbeda dari $x$. Kalau tidak, dalilnya sudah terbukti.

(11) Karena $C(u_{n+1}) = u_n$ dan masing-masing $u_i$ berbeda dari yang lain, mengikuti itu $u_{n+1}$ berbeda dari semua $u_0, u_1, \dots u_n$. Jika tidak,$C(u_{n+1})$ tidak akan sama $u_n$. Untuk melengkapi argumen, kita hanya perlu menunjukkan bahwa argumen itu berbeda$y$ yang merupakan kasus dari asumsi kami pada langkah (1).

Catatan: Asumsikan bahwa $u_{n+1} = u_j$ dimana $j < u_{n+1}$, kemudian $C(u_{n+1}) = C(u_j) = u_{j-1}$ tapi $C(u_{n+1}) = u_n$ dan dengan asumsi $u_n \ne u_{j-1}$ jadi kami memiliki kontradiksi dan dapat menolak asumsi tersebut.

Jawaban

8 DoctorWho Aug 19 2020 at 05:05

Cacatnya adalah pernyataannya

Kita dapat mengasumsikan bahwa x dan y tidak akan muncul sebagai nilai antara. Artinya, untuk i, ui ≠ x dan ui ≠ y. Jika x adalah nilai antara sebelum y, maka y tidak akan pernah bisa dicapai karena C (x) adalah sebuah fungsi dan masukan yang sama akan menghasilkan keluaran yang sama. Jika y adalah nilai perantara, maka kita bisa mengakhiri urutan pada titik itu.

Ini hanya valid jika Anda benar-benar mencoba membuktikan pernyataan berikut:

Seharusnya $y \neq x$ dan itu $n$ paling sedikit $n \in \mathbb{N}$ st $y = C^n(x)$ (dimana $C^n$ berarti melamar $C$ $n$waktu). Maka tidak ada pengulangan dalam urutan tersebut$x, C(x), C^2(x), ..., C^n(x)$.

Pernyataan ini selalu benar (pada kenyataannya, seseorang bahkan tidak perlu tahu apa-apa $C$untuk membuktikan bahwa ini benar). Tetapi ini sama sekali tidak memberi tahu Anda tentang keberadaan (atau tidak adanya) siklus.

Untuk mengilustrasikan hal ini, cukup pertimbangkan "versi sederhana" di mana $C : \{0, 1\} \to \{0, 1\}$ didefinisikan oleh $C(x) = 1 - x$. Pernyataan di atas juga berlaku ketika membicarakan hal ini$C$, tapi jelas ada a $C$-sepeda.