Mengapa Problem 3n + 1 Berbeda dari Problem 5n + 1

Anda mungkin masih penasaran dengan Problem 3n + 1 dan Problem 5n + 1: mengapa mereka berbeda. Pada Problem 3n + 1, dimulai dari bilangan asli n berapapun, barisan bilangan yang diperoleh akan berakhir di bilangan 1. Pada Problem 5n + 1, ada barisan yang berakhir di bilangan 1, misalnya 3, 16, 8, 4, 2, 1; ada juga barisan yang siklik, misalnya 13, 66, 33, 166, 83, 416, 208, 104, 52, 26, 13; dan banyak barisan yang divergen (menuju tak terhingga), misalnya 9, 46, 23, 116, 58, 29, 146, 73, 366, 183, … (sila teruskan sendiri).

Nah, walau belum ada yang bisa membuktikan secara rigor bahwa barisan bilangan yang dihasilkan pada Problem 3n + 1 selalu berakhir di bilangan 1, berikut adalah penjelasan heuristik dari David Speyer, yang sekaligus menjelaskan perilaku barisan bilangan pada Problem 5n + 1 — dan secara umum pada problem Ln + 1, dengan L bilangan ganjil.

Idenya adalah mengamati perubahan dari satu bilangan nk ke bilangan berikutnya nk+1: apakah cenderung membesar atau mengecil. Sebagai contoh, jika suatu bilangan n mempunyai peluang ½ untuk bertambah menjadi n + 3 dan peluang ½ untuk berkurang menjadi n − 1; maka — menurut teori peluang — bilangan tersebut cenderung bertambah menjadi n + 1, ya kan?

Pada problem Ln + 1, dengan L ganjil, setelah kita mendapatkan suatu bilangan ganjil, maka bilangan berikutnya pasti genap. Yang menjadi pertanyaan adalah bilangan berikutnya lagi, setelah bilangan genap itu. Untuk itu, mari kita amati pergerakan dari suatu bilangan ganjil ke bilangan ganjil berikutnya, melalui setidaknya satu bilangan genap (sebagai contoh, pada Problem 5n + 1, dari 9 ke 23 melalui 46, dan dari 23 ke 29 melalui 116 dan 58).

Secara heuristik, dari suatu bilangan ganjil nk, kita akan mendapatkan bilangan ganjil nk+1 = (Lnk + 1)/2 dengan peluang ½, atau nk+1 = (Lnk + 1)/4 dengan peluang ¼, atau nk+1 = (Lnk + 1)/8 dengan peluang 1/8, dan seterusnya. Untuk mengetahui apakah nk+1 lebih besar atau lebih kecil daripada nk, tinjau xk := ln nk. Maka, sebagai hampiran, kita mempunyai xk+1 ≈ xk + ln L − ln 2 dengan peluang ½, atau xk+1 ≈ xk + ln L − 2·ln 2 dengan peluang ¼, atau xk+1 ≈ xk + ln L − 3·ln 2 dengan peluang 1/8, dan seterusnya. Jadi, perkiraan besar perubahan dari xk ke xk+1 adalah:

prob collatz

Nah, sekarang terlihat bahwa untuk L = 3, perubahannya negatif, sedangkan untuk L = 5, perubahannya positif. Jadi kita tidak terkejut mendapati barisan bilangan yang divergen menuju tak terhingga pada Problem 5n + 1. Sebaliknya, kita juga bisa memahami mengapa barisan bilangan pada Problem 3n + 1 cenderung mengecil, dan pada akhirnya berhenti di bilangan 1. (Namun, hitung-hitungan di atas hanya merupakan argumen heuristik, bukan bukti formal. Hingga saat ini, bukti formal untuk Problem 3n + 1 belum ditemukan.)

*

Bandung, 25-07-2016

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s