Legenda Menara Hanoi

Menara Hanoi, sebuah permainan matematis sekaligus teka-teki yang ditemukan oleh Eduard Lucas, ahli matematika Perancis pada tahun 1883. Permainan ini terdiri dari tiga tiang dan sejumlah cakram dengan ukuran berbeda-beda yang bisa dimasukkan ke tiang mana saja. Permainan dimulai dengan cakram-cakram yang tertumpuk rapi berurutan berdasarkan ukurannya dalam salah satu tiang, cakram terkecil diletakkan teratas, sehingga membentuk kerucut. Kemudian cakram-cakram itu dipindahkan ke tiang kedua dengan bantuan tiang ketiga dengan aturan sebagai berikut:

• Hanya satu cakram yang boleh dipindahkan dalam satu waktu.
• Setiap perpindahan berupa pengambilan cakram teratas dari satu tiang dan memasukkannya ke tiang lain, di atas cakram lain yang mungkin sudah ada di tiang tersebut.
• Tidak boleh meletakkan cakram di atas cakram lain yang lebih kecil.

Permainan ini bersumber pada sebuah legenda tentang candi Indian yang berisi ruang besar dengan tiga tiang yang dikelilingi 64 buah cakram emas. Seorang Brahmana mencoba melaksanakan tugas dari peramal dengan mengikuti aturan main yang telah ditetapkan. Apabila teka-teki ini dapat diselesaikan maka dunia akan kiamat! Entah, legenda ini benar-benar ada atau hanya khayalan seorang Lucas. Yang pasti ini sangat berguna bagi ilmu pengetahuan.

Kita tidak perlu terfokus pada legenda itu, kita akan mencoba menghitung berapa waktu yang dibutuhkan untuk menyelesaikan teka-teki ini. Waktu yang dibutuhkan untuk menyelesaikan algoritma rekursif ini, digunakan teknik perhitungan kompleksitas dengan relasi rekurens. Berikut penjelasannya:

Algoritma
If n=1 then
Write (‘Pindahkanpiringandari’,A,’ke’,B)
Else
Hanoi(n-1,A,C,B)
Writeln(‘Pindahkanpiringandari’,A,’ke’,B)
Hanoi(n-1,C,B,A)
Endif
end

Setelah kita mengetahui algotritma itu dapat diambil relasi rekurens sebegai berikut:

Relasi Rekurens:

T(n) = 1 , n = 1;

T(n) = 2T(n-1) + 1 , n > 1

Jadi,

T(n) = 1+ 2T(n-1)

= 1 + 2(1 + 2T (n-2) ) = 1+ 2 + 2² T(n-2)

= 1 + 2+ 2² +(1+2T(n-3)) = 1+ 2 +2² + 2³T(n-2)

=…

= (1 + 2 + 2² + 2³ + …+ 2^n-2) + 2^n-1 T(1)

= 1 + 2 + 2² + 2³ + …+ 2^n-1.1

= 2ⁿ-1

Jika T(n) adalah waktu untuk menyelesaikan algoritma menara Hanoi ini sebanyak n piringan dan untuk memindahkan satu piringan adalah 1 detik, maka dapat dipastikan bahwa waktu untuk menyelesaikan 64 piringan adalah:

2⁶⁴ – 1 =10.446.744.073.709.551.615 detik atau kira-kira setara dengan 600 miliyar tahun.

Dapat disimpulkan bahwa legenda itu benar adanya, dunia tidak akan bertahan selama itu, dan dunia akan kiamat!!