Hanoi Kuleleri{Çözüldü}

[senior]

Bir plaka üzerine üstüste dizilmiş(büyük en altta) N tane farklı büyüklükteki dairesel levha var. Bunun yanında iki tane boş plaka daha var. Bu boş plakaları kullanarak,
    -  Her hamlemizde sadece bir levhanın yerini değiştirerek (Mesela 1.plakadan 2.plakaya)
    -  Hiçbir zaman büyük levha küçük levhanın üstüne gelmeyecek şekilde
bütün levhaları son plakaya taşımaya çalışıyoruz. Minimum kaç hamle yapmamız gerekir?

Ör: Eğer A ve B diye iki levhamız olsa idi (B > A olsun).

İlk durum:             Hamle 1:           Hamle 2:           Hamle 3:
     A                                                                                       A
     B                      B     A                      A      B                        B
    __   __   __      __   __   __       __   __   __        __   __   __

gibi 3 hamle yapacaktık.

[yasarfaith]

ispat konusunda net bir bilgim yok ama minimum hamle sayısı 2ⁿ-1 dir.

[Lokman Gökçe]

2ⁿ - 1 doğru cevaptır. Bunu tümevrımla kolayca kanıtlayabiliriz.

n = 1 için herşey açıktır. ispatlanacak bir şey yoktur.
n = 2 için Güneş kardeşim doğruluğunu göstermiş.
n = k için 2^k - 1 olduğunu Yaşar Fatih hocam tahmin etmiş. Bunun doğruluğunu kabul edelim.

Şimdi n = k + 1 için ispata geçelim. 1. kuleye dizilmiş olan k + 1 tane halkadan (ya da levhadan) en üstten aşağı doğru k tane halkayı 2. kuleye taşıyalım. Kabulümüzden dolayı 2^k - 1 hamlede bu işlemi yapabiliriz. Şimdi 1. kulede kalan en geniş halkayı 3. kuleye taşıyalım. (+1 hamle). Son işlemimizde de 2. kuledeki k tane halkayı 3. kuleye taşıyalım. bunu da 2^k - 1 hamlede yaparız ve problem tamamlanır.

 Toplam = (2^k - 1) + 1 + (2^k - 1) = 2^k+1 - 1

olur. Tümevarım gereğince iddiamız her n pozitif tamsayısı için doğrudur.

NOT: başka çözüm yolları da vardır. mesela uygun bir indirgemeli dizi kurularak da aynı sonuca ulaşılabilir.

[senior]

Tebrikler Ben de diğer çözümü paylaşayım.
N tane levha için gereken hamle sayısı H(N) olsun. Lokman Hocamızın anlattığı gibi strateji
 1) N-1 levhayı 2.plakaya taşı                       --> H(N-1) hamle
 2) 1.plakada kalan levhayı 3.plakaya taşı    --> 1 hamle
 3) 2.plakadaki N-1 levhayı 3.plakaya taşı    --> H(N-1) hamle

Yani elimizdeki bağıntı H(N) = 2H(N-1) + 1 = 2( 2H(N-2) + 1) + 1 = 4H(N-2) + (1 + 2) = 4( 2H(N-3) + 1 ) + (1+2) = 8H(N-3) + (1+2+4)
= ... = 2^kH(N-k) + (1+2+...+2^k-1); H(1) = 1 olduğunu biliyoruz. O zaman N = k+1 diyelim ve yerine koyalım.
H(N) = 2^N-1H(1) + (1+2+...+2^N-2) = 2^N-1 + (2^N-1-1) = 2^N-1

[Lokman Gökçe]

Güneş kardeşim, yüksek müsaadenle zarif çözümüne küçücük bir ekleme yapayım

H(n) = 2H(n-1) + 1 bağıntısı doğrusal olup homojen indirgemeli dizi haline getirilip karakteristik denklem çözülerek de aynı netice elde ediliyor.