Anasayfa » MAKALE » Hanoi Kulesi Problemi

Hanoi Kulesi Problemi

Hanoi Kulesi problemi, 1883’te Fransız matematikçi Edouard Lucas tarafından bulundu ve oyuncak olarak satılmaya başlandı. Şekilde 8 diskten yapılmış bir kule ve iki boş çubuk görülmektedir. Her keresinde bir diski hareket ettirmek ve bir diski asla kendisinden küçük bir disk üzerine koymamak şartıyla kuledeki diskleri boş iki çubuğa en az kaç hamlede aktarabilirsiniz? Problemi önce 2, 3 ve 4 gibi az sayıda diskle çözmeye çalışıp bir formül geliştirebilir misiniz?

kule1

Çözüm: Kulede n sayıda disk varsa, en az 2n-1 hamle gereklidir. Böylece 3 disk 7, 4 disk 15, 5 disk ise 31… hamlede nakledilebilir. 8 disk için 255 hamle gereklidir; 28- 1=256-1=255 Hindistan’daki Benares kentinde bir tapınakta bulunan “Brahma Kulesi”,”- Hanoi Kulesi”nin benzeridir. Brahma Kulesi’nde 64 altın disk vardır ve rahipler, nesillerdir bu diskleri boş iki çubuğa aktarmakla meşguldürler. (Bu 64 altın disk için) gerekli hamle sayısı, 264-1’dir. Bu ise 2 x 1018e yakın 20 basamaklı bir sayıdır. (Yaklaşık 1.84467441 × 1019) Rahipler, gece gündüz çalışıp her saniyede bir disk aktarsalar bile; işi bitirmek bile milyarlarca yıl alacaktır. Söz konusu sayı, asal değildir; fakat, n = 89 veya 107 veya 127 olarak alınırsa asal sayılar elde edilebilir. Bunlara “Mersenne sayıları” denmektedir. Lucas, ilk Mersenne sayısı olan 2127-1’i bulmuştu. (170,141,183,460,469,231,731,687,3 03,715,884,105,727) Ondan sonra 12 Mersenne sayısı daha bulundu. Bunların en büyüğü, 1971’de IBM Araştırma merkezi bilgisayarlarınca bulunan Mersenne sayısıdır: 219937-1. (219937-1) Bu, 6002 basamaklı bir sayıdır. kule2Üç diskli Hanoi Kulesi’nde disklere A, B ve C dersek, disklerin hareket sırası, ABA CABA, dört diskli (A,B,C,D) Hanoi Kulesi’nde disklerin hareket sırası, ABA CABA DABA CABA (15)’tir. Soldaki küpte küpün koordinatlarını A, B ve C diye aldığımızda, ABA CABA yolu, sağdaki 4 boyutlu küpte (4 boyutlu hiperküp) koordinatları A, B, C ve D olarak ele alındığında ABA CABA DABA CABA yolları, noktalı çizgilerle gösterilmiştir. Bunlara “Hamilton yolları” denmektedir. Ünlü İrlandalı matematikçi Hamilton, 1850’de “İcosa Oyunu” adı altında bir oniki yüzlünün (dodecahedron) bütün köşelerini dolaşıp başlanan noktaya dönmeyi bulmuştu. Bu oyun, bütün Avrupa’ya yayıldı. Hamilton, bu keşfinden yalnızca 25 sterlin kazanmıştı. Oyunu satanlar ise milyonlar kazandı.

#HanoiKulesi, #EdouardLucas, #BrahmaKulesi, #MersenneSayıları