Ay: Eylül 2013

Hanoi Kulesi ve Tekrar Bağıntıları

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.