Hanoi Kuleleri kendi başınıza güzel vakit geçirebileceğiniz zevkli bir oyundur. Üç çubuk ve büyükten küçüğe sıralanmış halkalardan oluşan oyunun kuralları şöyle: başta bir çubukta bulunan halkaları, her adımda sadece en üstten halka alarak ve bir halkanın üzerine kendinden büyük bir halka koymayarak tüm parçaları başka bir çubuğa taşımak istiyoruz.
10 halkadan oluşan bir Hanoi Kuleleri oyununu en az kaç hamlede bitirebilirsiniz?
Cevaplarınızı [email protected] adresine yollayabilirsiniz.
Cevap:
1 halkalı Hanoi Kuleleri oyunu (tabii ki) tek hamlede bitirilebilir. Bunu a(1)=1 olarak gösterelim. Eğer n halkalı bir oyunu a(n) hamlede bitiriyorsak, n+1 halkalı oyun için şöyle bir strateji izleyebiliriz: n halkayı kulelerden birine toplayalım (a(n) hamlede), en alttaki büyük halkayı diğer kuleye alalım (1 hamle), başta bir yere topladığımız n halkayı en büyük halkanın üzerine toplayalım (a(n) hamle). Bu strateji (eğer n halkalı oyunu biliyorsak) n+1 halkalı oyunu 2a(n)+1 hamlede bitirmemizi sağlıyor. a(1)=1 eşitliğini de göz önünde bulundurarak a(2)=3, a(3)=7, a(4)=15 olarak hesaplayabiliriz. Genel olarak a(n)=2n-1olduğunu tümevarımla kolaylıkla gösterebiliriz.
Dolayısıyla 10 halkalı oyun a(10)=210-1=1023 hamlede çözülebilir.
