Konjektur Collatz : Semua Nombor akan Jadi 1. Betul Ke?

Konjektur Collatz: Mudah Difahami, Sukar dibuktikan

Jom kita main satu permainan. Cara permainannya mudah sahaja:

1. Pilih satu nombor n
2. Jika n adalah nombor genap, n dibahagi 2
3. Jika n adalah nombor ganjil, n didarab 3 kemudian tambah 1 bererti (3n+1)
4. Ulang semula proses 2 atau 3 kepada hasil nombor yang diperoleh.

Sebagai contoh, kita pilih nombor 12 .

12 adalah nombor genap, jadi 12 dibahagi 2 menjadi 6 .

12\div2=6 6 adalah nombor genap, jadi 6 dibahagi 2 menjadi 3 .

6\div2=3 3 adalah nombor ganjil, jadi 3 didarab 3 dan tambah 1 menjadi 10.

3×3+1=10 10 adalah nombor genap, jadi 10 dibahagi 2 menjadi 5.

10\div2=5 5 adalah nombor ganjil, jadi 5 di darab 3 dan tambah 1 menjadi 16 .

5\times3+1=16 16 adalah nombor genap, jadi 16 dibahagi 2 menjadi 8 .

16\div2=8 8 adalah nombor genap, jadi 8 dibahagi 2 menjadi 44.

8\div2=4 4 adalah nombor genap, jadi 4 dibahagi 2 menjadi 2.

4\div2=2 2 adalah nombor genap, jadi 2 dibahagi 2 menjadi 1 .

2\div2=1 1 adalah nombor ganjil. jadi 1 didarab 3 dan tambah 1 menjadi 4 .

1\times3+1=4

Jika kita teruskan proses ini, 4 akan menjadi 2 kemudiannya menjadi 1 dan ia akan berulang pada 4, 2, 1 dan seterusnya. Ini bermaksud permainan ini akan tamat pada nombor 1 .

Maka

12\rightarrow6 \rightarrow 3 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1

Bermaksud 12 akan menjadi kepada 1

Ok, apa kata kita cuba nombor lain pula. Katakan kita pilih nombor 7 .

Jika kita buat proses jujukan tadi, kita akan dapat hasil seperti berikut:

7 \rightarrow 22 \rightarrow 11 \rightarrow 34 \rightarrow 17 \rightarrow 52 \rightarrow 26 \rightarrow 13 \rightarrow 40 \rightarrow 20 \rightarrow 10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1

Jadi 7 pun akan menjadi 1 .

Anda boleh pilih apa-apa nombor, dan cuba buat proses ini, pasti akhirnya nombor tersebut akan menumpu menjadi 1.

Masalah ini dikenali sebagai Konjektur Collatz (Collatz Conjecture) ataupun Terkaan Collatz.

Konjektur Collatz (Terkaan Collatz)

Penyataan Masalah

Jika \boldsymbol{n} adalah positif integer, nombor berikutnya diperolehi melalui proses berikut:

\boldsymbol{n}\div2 jika \boldsymbol{n}= genap

3 \boldsymbol{n}+1 jika \boldsymbol {n}= ganjil

Proses ini diulang sehingga mencapai 1.

Terkaan Collatz (Konjektur)

Bagi sebarang integer positif \boldsymbol{n} yang dipilih, semuanya akan menjadi 1.

Persoalannya, benarkah SEMUA nombor yang dipilih akan menjadi 1?

Sebelum kita pergi lebih jauh, kita berkenalan dulu dengan orang yang bertanggungjawab memperkenalkan masalah ini, iaitu Lothar Collatz

Lothar Collatz

Lothar Collatz adalah seorang ahli matematik Jerman. Beliau lahir pada 6 Julai 1910 di Arnsberg, Westphalia.

Nama Konjektur Collatz diambil sempena nama beliau, apabila beliau memperkenalkan masalah ini pada tahun 1937, dua tahun selepas beliau menerima kedoktoran.

Masalah yang belum dapat diselesaikan

“Adakah SEMUA nombor integer positif yang melalui proses jujukan Collatz ini akan menjadi 1″

Masalah ini adalah masih belum dapat dibuktikan sehingga hari ini. Walaupun ahli matematik telah mencuba jujukan ini kepada nombor sebesar 500 digit dan memang nombor-nombor tersebut menjadi 1. Tetapi wujudkah nombor yang tidak akan menjadi 1?

Konjektur Collatz adalah satu masalah yang disifatkan oleh ahli matematik sebagai masalah matematik yang paling susah untuk dibuktikan. Semua berpendapat, pengetahuan sedia ada tentang matematik masih belum cukup untuk membuktikan konjektur ini.

Ada yang berpendapat, Konjektur ini tidak akan diselesaikan di zaman ini kerana kita masih belum bersedia.

Walaupun Konjektur Collatz ini susah untuk dibuktikan, tetapi untuk memahami masalah ini tidaklah terlalu sukar. Jadi Collatz adalah masalah yang mudah difahami, tetapi sangat susah untuk dibuktikan.

Pokok Collatz (Collatz Tree)

Antara teknik yang biasa digunakan oleh ahli matematik untuk membuktikan suatu terkaan adalah dengan mengenalpasti corak (pattern) sesuatu masalah. Adakah masalah tersebut mempunyai suatu corak yang berulang-ulang? Jika ya, mungkin pembuktian boleh dihasilkan daripada corak tersebut.

Jadi, dalam usaha ahli matematik menyelesaikan masalah ini melalui corak, maka terhasillah apa yang dikenali sebagai pokok Collatz. Pokok Collatz adalah sebuah graf yang menunjukkan laluan untuk ‘setiap’ nombor sebelum ia menjadi 1. Ada nombor yang laluan singkat sebelum menjadi 1 dan ada yang panjang. Sebagaimana contoh di atas, nombor 12 hanya memerlukan 10 langkah sebelum menjadi 1, tapi bagi nombor 7, ia memerlukan 17 langkah sebelum menjadi 1.

Jika diperhatikan, laluan bagi 7 dan 12 akan menjadi 10 dan seterusnya proses akan menjadi 1. (gunakan mode lanscape untuk paparan penuh)

\begin{aligned} 7 \rightarrow 22 \rightarrow 11 \rightarrow 34 \rightarrow 17 \rightarrow 52 \rightarrow 26 \rightarrow 13 \rightarrow 40 \rightarrow 20 \rightarrow &10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1 \\ &\downarrow \\ 12\rightarrow6 \rightarrow 3 \rightarrow &10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1\end{aligned}

Maka laluan bagi 7 boleh di sambung pada laluan 12 kerana kedua-duanya akan menjadi 10 dan seterusnya menjadi 1. Ini membentuk pokok Collatz. (gunakan mode lanscape untuk paparan penuh)

\begin{aligned} 7 \rightarrow 22 \rightarrow 11 \rightarrow 34 \rightarrow 17 \rightarrow 52 \rightarrow 26 \rightarrow 13 \rightarrow 40 \rightarrow &20 \\ &\downarrow \\ 12\rightarrow6 \rightarrow 3 \rightarrow &10 \rightarrow 5 \rightarrow 16 \rightarrow 8 \rightarrow 4 \rightarrow 2 \rightarrow 1\end{aligned}

Kemudian, anda boleh menyambung pokok ini dengan laluan-laluan bagi nombor yang lain dan anda akan dapati banyak laluan-laluan yang boleh disambung. Ini adalah contoh pokok Collatz yang dihasilkan, anda juga boleh hasilkan pokok Collatz anda sendiri.

Hampir dibuktikan

Pada tahun 2019, seorang ahli matematik terkenal yang juga pemenang Field Medals 2006, Terence Tao telah menerbitkan ‘bukti’ bahawa Konjektur Collatz adalah benar bagi ‘kebanyakan’ nombor (pautan pembuktian beliau). Walaupun pembuktian beliau bukanlah pembuktian yang menyeluruh, tapi ia adalah satu pencapaian yang besar dalam masalah Konjektur Collatz.

Walaupun Konjektur Collatz merupakan masalah popular dalam bidang matematik, namun pembuktiannya tidak mempunyai aplikasi. Namun begitu, banyak penerokaan baharu yang wujud disebabkan oleh Konjektur Collatz ini. Mungkin tidak berguna walaupun dibuktikan, tetapi perjalan membuktikannya membuka ruang kepada terbinanya idea baharu matematik.

Jadi, kalau tak ada apa-apa nak dibuat dimasa lapang, bolehlah cuba buat pokok Collatz. Mana tahu, tiba-tiba dapat ilham untuk selesaikannya. Boleh penulis tumpang bangga.

Video Penerangan Tentang Konjektur Collatz

Rujukan:

1. https://www.quantamagazine.org/mathematician-terence-tao-and-the-collatz-conjecture-20191211/
2. https://www.quantamagazine.org/why-mathematicians-still-cant-solve-the-collatz-conjecture-20200922/
3. https://en.wikipedia.org/wiki/Collatz_conjecture
4. https://arxiv.org/abs/1909.03562