Hanoi Kulesi ve Tekrar Bağıntıları

Rings 4 Minutes

Selam. İyi bir matematik bölümünde geçirilecek dört yılın insana yapacağı katkılar saymakla bitmez. Bu katkılardan biri de insanın Vietnam‘ın başkenti olan Hanoi ve Hanoi kulesinden haberdar olmasıdır sanırım. Fazla uzatmadan bir matematik bölümünde Vietnam, Hanoi ve kulenin ne işi olduğunu açıklayalım.

Her şey Fransız matematikçi Édouard Lucas‘ın ortaya bir problem atmasıyla başladı. İfadesi gayet basit olan problem şöyle: önünüzde 3 tane çubuk ve bu çubuklara dizilebilen, her biri değişik boyutta diskler var. Başlangıç durumunda bütün diskler bir çubukta, en büyük disk en alta gelecek şekilde büyükten küçüğe doğru sıralanmış durumdalar. Aynen Wikipedia’daki “Tower of Hanoi” başlığından alınmış aşağıdaki resimdeki gibi:

Başlangıç Durumu.
Başlangıç Durumu

Oyunun amacı bütün diskleri bir diğer çubuğa, yine aynı sırada (yani en büyük en altta olacak şekilde büyükten küçüğe) taşımak. Yalnız bunu yaparken şu kurallara uyulacak:

Kural 1) Her bir hamlede sadece bir disk taşınabilir.

Kural 2) Her bir hamle, bir çubuktaki en üstte bulunan diski alıp, diğer çubukta en üste yerleştirmekten ibarettir.

Kural 3) Hiçbir disk kendisinden daha küçük olan bir diskin üzerine yerleştirilemez.

Bu kurallara göre, n tane diski bir çubuktan diğerine taşımak için en az kaç hamle gereklidir? Küçük sayılar için bu soruya cevap vermek güç değil, örneğin üç diski taşımak için yedi hamle gerekiyor. Yine Wikipedia’daki aynı başlıktan alınan aşağıdaki gösterimde de dört diskin taşınması gösteriliyor

3 diskin taşınması
4 diskin taşınması

Bu soruya cevap vermenin bir yolu tekrar bağıntılarını kullanmak. Bir veya daha fazla başlangıç terimi bilindiği takdirde, herhangi bir terimi kendisinden önce gelen terimler cinsinden ifade ederek bir sayı dizisi oluşturan denklemlere tekrar bağıntıları diyoruz.  Örneğin ünlü Fibonacci dizisi

F_n = F_{n-1} + F_{n-2}, F_0 = 0 ve F_1 = 1

şeklindeki tekrar bağıntısı ile tanımlanıyor.

Gelelim sorduğumuz sorunun tekrar bağıntılarıyla çözümüne. Elimizde n tane disk olduğu durumda yapmamız gereken en az hamle sayısını a_n ile gösterelim. Şimdi bu hamle sayısını n-1 tane diski taşımak için gereken hamle sayısı cinsinden, yani a_{n-1} cinsinden ifade edeceğiz.

İşe öncelikle en üstteki n-1 tane diski bir diğer çubuğa taşımakla başlayalım. Bunun için a_{n-1} tane hamle gerekli. Daha sonra da en altta kalan en buyuk diski boş olan çubuğa aktarmamız gerekiyor. Bunun için de bir tane hamle yapmak lazım. Son olarak da, diğer çubukta duran n-1 tane diski, en buyuk diskin üzerine taşımamız için bir a_{n-1} hamle daha yapmamız gerek. Etti mi size 2a_{n-1} +1 hamle! Yani kısacası, elimizde a_{n} = 2a_{n-1} + 1 gibi bir tekrar denklemi var. Bu denklemin başlangıç koşulu da, elimizde hiç disk yoksa hiç hamle yapmayacağımız için, a_{0} = 0 olur.

Gelelim bu denklemin çözümüne. Bu denklemin çözümü ile kast edilen, a_{n} için verilen ifadedeki a_{n-i} terimlerinden kurtulup, sadece n cinsinden bir denklem elde etmek. Simdi bu denklemi kurcalayıp, her terimi bir önceki terim cinsinden ifade ederek yazalım:

a_{n} = 2a_{n-1} + 1

ifadesinde a_{n-1} yerine 2a_{n-2} + 1 yazarak

a_{n} = 2(2a_{n-2} + 1) + 1 = 4a_{n-2} + 3

ifadesini, aynı işlemi tekrar ederek de

a_{n} = 8a_{n-3} + 7

denklemini elde ediyoruz. Buradan yola çıkarak, i adımında denklemin

a_{n} = 2^{i}a_{n-i} + 2^{i}-1

olduğunu görebiliriz. Son olarak, bu denklemde i = n yazar ve a_{0}‘in sıfıra eşit olduğunu hatırlarsak, denklemin çözümünün

a_{n} = 2^{n}-1

olduğunu buluruz. Yani, üç tane diski taşımak için 2^{3} - 1= 7, dört tane diski taşımak için 2^{4} - 1 = 15 tane hamle yapmak lazım. Bu sayının gerçekten de denklemin çözümü olduğunu matematiksel tümevarım ile de doğrulamak lazım, ancak bunu yapmak için tümevarımdan da bahsetmek gerektiği için bu kısma su an girmiyorum.

Efsaneye göre, bir grup Brahma rahibi Hindistan’daki antik bir tapınakta, eski bir kehanetin emirleri doğrultusunda 64 tane diski eski zamanlardan bu yana bir kolondan diğerine taşımaktalarmış. Kehanete göre de, rahipler bütün diskleri taşıyınca dünyanın sonu gelecekmiş. İnsan dünyanın sonunun geleceğini bile bile neden bu işlemi devam ettirir bilemem ama, eğer rahiplerin her saniyede bir disk taşıyabildiklerini kabul etsek bile, bu işin tamamlanması için 2^{64}-1 saniye gerekmekte – yani henüz dünyanın sonu için endişelenmeye gerek yok.

Peki, bir parti verdiğimizi ve partiye gelen herkesin diğer konuklarla sadece ve sadece bir kere el sıkıştığını kabul edelim. Konuk sayısının n olduğu durumda toplam kaç tane el sıkışması gerçekleşir?

Not: Aradan geçen zaman fazla olunca insan en basit matematik problemlerinin bile ifadesini unutabiliyor. Bu durum benim de başıma Hanoi Kulesi probleminin kurallarını eksik hatırlamam ve sonucunda insanları boş yere uğraştırmamla sonuçlandı. Bunun üzerine de bu yazıyı yazmaya karar verdim. Arada bu ünlü problemleri hatırlamakta fayda var sanırım.

Bilinmeyen adlı kullanıcının avatarı

Can Hatipoglu tarafından yayınlandı

Matematikçi.

Yayımlanmış

“Hanoi Kulesi ve Tekrar Bağıntıları” için 3 yorum

  1. Geri bildirim: Matematiksel Tümevarım İlkesi | Rings and Things

  2. Hocam internette hanoi kuleleri hakkınındaki yazıyı okudum. suan öğrencilerimle beraber bu oyunun projesini yapacağım. internette özellikle yabancı sitelerde hanoi kulelerinin çözümünden bir ağç diyagramı oluşturup , sierpenski üçgeniyle bağlantısı olduğunu göstermişler.fakat ben diagramları anlamadım. yardımcı olurmusunuz.
    http://www.cut-the-knot.org/triangle/Hanoi.shtml

    Cevapla

  3. Merhaba. Herhangibir bulmaca dusunelim, ornegin Hanoi Kuleleri problemi. Bu bulmacaya eslik eden bir cizge (graph) su sekilde elde ediliyor: cizgenin noktalari bulmacanin durumlarindan olusuyor. Eger bir durum, bulmacanin kurallarinca izin verilen bir hamleyle bir baska durumdan elde edilebiliyorsa bu iki duruma karsilik gelen noktalar birbiriyle baglanarak kenarlar elde ediliyor. Bu noktalari ucgensel olarak dizersek de mevzubahis cizge ortaya cikiyor.

    Tekrar baglantilarini kullanarak buldugumuz cozum bize oyunun en az kac hamlede cozulecegini soyluyor. Ancak bu yontem bize oyunu kazanmak icin hangi hamleleri yapmamiz gerektigini soylemiyor. Bu baglamda, bu cizgelerin bence en buyuk ozelligi bize bulmacayi nasil cozecegimizi gostermeleri.

    Hanoi kulesi ornegi ozelinden devam edersek, eger 3 diskli ornege karsilik gelen cizgeye bakarsak, tepe noktasindaki (1, 1, 1) pozisyonu oyunun baslangic durumu olarak kabul edilirse bizim amacimiz en alt koselerdeki (2, 2, 2) veya (3, 3, 3) noktalarina ulasmak. Bunu da cizgenin kenarlarla birlestirilmis noktalarini takip ederek yapabiliriz. 3 disk icin gereken en az hamle sayisinin 7 oldugunu hatirlarsak, cizgenin tepe noktasindan baslayip sol veya sag kenar boyunca hareket ederek 7 hamlede istenen (2, 2, 2) veya (3, 3, 3) noktalarina ulasildigi gorulebilir.

    Paylastiginiz yazida bahsi gecen bir yorum da n disk icin cizilen cizgenin n – 1 disk icin cizilen cizgenin uc kopyasini icerdigi ve bu kopyalarin “uclarinin” da birer kenarla birbirine baglandigi. Bu durum da tekrar bagintilari kullanilarak verilen cozumden gorulebilir: n disk durumunu cozmek icin once n – 1 disk durumunu inceliyoruz. Peki neden uc tane kopya? Tekrar bagintilariyla verilen cozumde gordugumuz gibi problemi cozerken en buyuk diski bir kenara koyup kalan n – 1 tane disk ile ugrastigimizi dusunuyoruz. En buyuk diski koyabilecegimiz uc tane secenegimiz (uc tane cubuk) oldugu icin de uc kopya ortaya cikiyor.

    Su anda soyleyebileceklerim bu kadar, eger daha fazla yardimci olabilirsem bana blog’daki iletisim kutusunu kullanarak ulasabilirsiniz, elimden geldigince yardim etmeye calisirim.

    Cevapla

Yorum bırakın