Bir Zeka Oyunu: Hanoi Kuleleri

En popüler Zeka Oyunlarından biri olarak bilinen Hanoi Kuleleri bulmacası nedir, nasıl çözersiniz? Acaba kesin bir çözüm yöntemi bulunabilir mi? Kaç hamle gerektirir? Tümevarım gibi teknikler ile bu soruların cevabını bulalım!

Önünüzde üç direk ve ortası delik, farklı çap uzunluklarına sahip üç disk olduğunu hayal edin. Bu diskler çapı en uzun olan en altta kalacak ve yukarı doğru çap uzunluğu azalacak şekilde bir tane direkte dizilmiş olsun (aşağıdaki ilk görselde görüleceği üzere).

Bu düzeneğin üzerinde bir oyun oynayalım. Oyundaki amacımız bu diskleri aynı dizilimde olacak şekilde başka bir direğe dizmek olsun: örneğin, direk 1'den direk 3'e bütün diskleri geçirmek. Lakin, bir kurallarımız var: Oyun boyunca direklerden en üstteki diski hareket ettirebiliriz ve hiçbir zaman bir disk kendisinden küçük disklerin üzerine gelemez.

Sorumuz şu şekilde: Kaç hamlede bunu başarabiliriz?

Hemen denemeye başlayalım… Anlatım kolaylığı adına diskleri küçükten büyüğe sırasıyla Disk A, Disk B ve Disk C olarak isimlendirelim (yani başlangıçta diskler -1. direkte- en üstte Disk A, ortada Disk B ve en altta Disk C olacak şekilde sıralanmıştır).

1. İlk hamlemizde mecburen Disk A’yı bir yere taşımamız gerekecektir, bu yüzden 3. direğe taşıyalım.
2. İkinci olarak Disk B’yi 2. direğe taşımak zorundayız çünkü Disk A’yı başka bir yere hareket ettirmemiz bize gereksiz hamle yaptıracağından mantıksız olur ve Disk B’yi de sadece taşıyabileceğimiz yer Direk 2'dir.
3. Büyük resmi incelersek, bütün diskleri 3. direğe taşımak adına eninde sonunda ilk Disk C’yi 3. direğe koymamız gerekli! O zaman bunu yapabilmek adına, Disk A’yı 2. direkteki Disk B’nin üstüne almalıyız, öyle yapalım.
4. Disk C’yi sonunda 3. direğe koyma şansını yakaladık, o zaman ne duruyoruz?
5. Bu defa amacımız artık Disk B’yi 3. direğe koymak olduğundan hemen Disk A’yı Disk B’nin üzerinden alarak 1. direğe koyalım.
6. Disk B’yi 3. direğe (Disk C’nin üzerine) alalım.
7. Ve son olarak Disk A’yı 3. direğe alıp oyunu başarıyla tamamlayalım!

Kısacası, bütün hamleler şu şekilde oldu:

Bu oyunu 7 hamlede bitirmeyi başardık. Bir matematikçi edasıyla düşünerek şu soruyu sormamak elde değil: 4 disk olsaydı kaç hamlede bitirmeyi garantileyebilirdik? Ya da 5? Peki ya n?

Öncelikle bir gözlem yapalım. n=2 için 3 hamlede tamamlanacağı barizdir. n=3 hamle için de 7 hamlede tamamlanabilir oyun. Bu durumda acaba n=k olursa 2ᵏ-1 durumda tamamlanır mı diye bir soru geliyor akıllara… Kanıtlamaya çalışalım o zaman, kim bilir belki doğru bir formüldür.

n disk için “tümevarım” diye isimlendirilen kanıt metodunu kullanmak bizim için çok rahat olacaktır. Bu metod başlı başına apayrı bir makalede anlatılacak bir konudur fakat kısaca açıklayalım. Bu metodu tıpkı domino devirmeye benzetebilirsiniz. Sırayla dizilmiş sonsuz dominonun bir tanesi devrilirse hepsinin devrileceğini kanıtlamak için iki aşama gereklidir: İlk dominonun devrildiğini göstermek ve herhangi bir domino devrilirse ondan sonrakinin de devrileceğini göstermek. Tümevarım ile kanıtta da iki tane ana adım vardır: başlangıç adımı ve tümevarım adımı. Başlangıç adımında iddianın belirli bir sayı için sağladığı gösterilir. Tümevarım adımında ise herhangi bir sayı için sağlandığı varsayılır ve ondan sonraki sayının da bu durumda bu iddiayı sağladığı gösterilir. Bu iki aşama birleşince de başlangıç sayısından itibaren her sayıda (genellikle her tam sayıda olur bu) iddia sağlanmış olur, tıpkı dominolardaki gibi!

Başlangıç adımı ile başlayalım. n=1 için 2¹-1 hamlede yapılabilir ve bu bizim iddiamızı sağlıyor.

Sırada tümevarım adımı var. n=k için 2ᵏ-1 hamlede yapıldığını varsayalım ve n = k+1 durumunda 2ᵏ⁺¹-1 hamlede yapılabileceğini kanıtlayalım.

n=k+1 durumunu inceleyelim. n=3 durumunda yaptığımız gibi, bütün diskleri 3. direğe getirmek adına ilk başta en büyük diski 3. direğe getirmemiz gerekli ve aslında bunun için de diğer n-1 diski 2. direğe getirmemiz gerektiği barizdir. O zaman en büyük disk dışındaki k diski (yani n-1 diski) 2. direğe getirelim. Bunun için varsayımımızdan dolayı 2ᵏ-1 hamle gerekli. Sonra yapmayı hedeflediğimiz gibi en büyük diski 3. direğe getirelim (burada 1 hamle daha yaptık). En son olarak da 2. direkteki k diski 3. direğe taşıyalım. Bunun için, yeniden, varsaydığımız üzere 2ᵏ-1 hamle gerekecektir. Dolayısıyla (2ᵏ-1)+1+(2ᵏ-1)=2 x (2ᵏ-1)+1=2ᵏ⁺¹-2+1=2ᵏ⁺¹-1 hamlede oyunu tamamladık! Kanıtımız tamamlandı! Demek ki n disk olması durumunda 2ⁿ-1 hamlede oyunu tamamlayabildiğimizi kanıtladık!

Peki acaba bu yapabileceğimizin en iyisi mi? Bir diğer deyişle, en az 2ⁿ-1 hamle ile mi yapılabilir yoksa daha az hamle ile yapma şansımız var mıdır? Bunun çözümü için kendi başınıza uğraşmanızı tavsiye ederim. Çözüm tümevarım ile kanıta çok benzer bir biçimde elde ediliyor fakat “indirgeme tekniği” isimli bir teknik ile elde ediliyor. Bu teknik ile ilgili yayınlanacak bir diğer yazımızı inceleyip orada sorunun çözümünü bulabilirsiniz!

Makale boyunca bahsettiğimiz bu oyun aslında en popüler zeka bulmacalarından biri olarak bilinen “Hanoi Kuleleri” isimli bulmacadır. Anlayacağınız, üzerinde yapılmış bir sürü araştırmayı farklı kaynaklarda da inceleyebilirsiniz :) Görüşmek üzere!

Kaynakça:

1. Maya Organic Handcrafted Tower of Hanoi Wooden Puzzle — Brahma, Multicolour. 29 July 2018, www.amazon.in/Maya-Organic-Handcrafted-Wooden-Puzzle/dp/B07G19MVYG. Accessed 22 May 2020.
2. Spivak, Michael. Calculus. Cambridge University Press, 2018.