6 diskli bir hanoi kulemiz olsun. bir çocuk oyunun kurallarına uygun hamleler yapıyor. oyunun herhangi bi anında gözlemleyebileceğimiz kaç değişik durum vardır?



oyunla ilgili kısa bilgi:
3 tane çubuk vardır. ortalarında çubuklara takılmalarını sağlayan delikler olan birbirinden farklı boyutta diskler vardır. diskler ya boş bir çubuğa takılır ya da kendinden büyük bir diskin üstüne takılır. amaç başlangıçta sırayla dizilmiş tüm diskleri yine sıralı olarak boş çubuklardan birine taşımaktır.

Alıntı:

---

gereksizyorumcu'den alıntı

oyunun herhangi bi anında gözlemleyebileceğimiz kaç değişik durum vardır?

---

bu kısmı anlamadım toplam 63 hamle yapılıcak oyunu bitirmek için herbir hamle için o anda kaç değişik seçenek var gibi anlıyorum ve bu haliyle pekiyi bir soru olmuyo neden ben böyle anlıyorum:)?
bi örnek yada açıklama versenizde aydınlansak iyi olacak gibi...

hocam kusura bakmayın biraz muğlak bi anlatım olmuş. aslında 7. sınıf bi arkadaşımızın sorusundan hareketle başka bi soru soracaktım (10 kişi 6 koltuğa kaç şekilde oturur diye sormuştu) ama bu soruyu ön alıştırma olarak yazdım. o arada da sorunun anlatımı kötü olmuş, hemen açıklayayım;

çocuk 63 hamlede bu işi yapabileceğini bilmiyo tek bildiği kurallara uygun şekilde diskleri bi çubuktan başka çubuğa aktarmak yani asla küçüklerin üstüne büyük disk koymuyor. biz de atıyorum elimizde fotoğraf makinesi çekiyoruz. disklerin yerleşimiyle ilgili en fazla kaç değişik resim elde edebiliriz?

bu ön alıştırma ise demekki hanoi2, hanoi3, hanoi4 bunlarda yakında vizyona girecek
soruyu netleştirmek adına son bir şey söyleyelim;
bu oyunu çocuk minimum 63 hamlede bitirir siz ise oyunun kurallarına sadık kalmak şartıyla ve yapılan bir hamleyi 2. kez tekrarlamamak şartıyla (en küçük diski sürekli üç çubuk arasında sonsuza kadar gezdirip oyunu kurallarına göre oynadığımız halde bitirmeyebiliriz)veya fotoğraf çekmek gibi aynı resmi 2. kez görmek istemiyoruz bu oyunu 6 disk ile maxsimum kaç hamle oynayabiliriz bumudur sorumuz?
şunuda ekleyeyim başlangıçtaki solda duran altı diskin üzerindeki küçük diski orta çubuğa koymak ile sağ çubuğa koymak ayrı ayrı sayılacak doğrumudur?

demek istediğim kaç değişik gözlem yapabiliriz. çocuk tabiki sınırsız sayıda hamle yapabilir ama bu hamleler sonucunda oluşacak durum sayısı sınırlıdır.
Soruyu iyi ifade edemediğimden ve belki de zor olduğunun düşünülmesinden henüz çözülmedi yoksa bildiğiniz üniversite sınavı ayarında. Hanoi2 ve olsa hanoi3 biraz zor olabilir :)

Alıntı:

---

gereksizyorumcu'den alıntı

6 diskli bir hanoi kulemiz olsun. bir çocuk oyunun kurallarına uygun hamleler yapıyor. oyunun herhangi bi anında gözlemleyebileceğimiz kaç değişik durum vardır?

---

Minimum 63 hamlede oyunun bitebiliyor olması bize ilk başta 63 değişik durumun yada gözlemin -herneyse- olabileceği fikrini çağrıştırıyor. Ancak maksimum hamle sayısı sınırsız yani sonsuz olduğundan bu durumda sonsuz değişik durumun olduğu yanılgısı yaratır.
---sıralı olarak diskler büyükten küçüğe A-B-C-D-E-F olarak adlandırılacak olursa çözüm koşulları;
-Herhangi bir çubukta A diski istisnasız olarak en tabanda bulunması gereken disktir.
-Herhangi bir çubukta F diski ya tek başına yada en tepede bulunması gereken disktir.
-Disklerin çubuklarda ardışık sıralı dizilmesi şart değildir. ( yani bir çubukta en altta B diski onun üstünde D ve onunda üzerinde F diski bulunabilir)
Bu koşullar altında sayısal verilere dayalı çözüm üretmek için yeterli vaktim olursa bunu paylaşırım. saygılar.

cevap: 729
çözüm: çubuklar X,Y VE Z olarak adlandıralım. Herhangi bir gözlemde çubuklarda bulunacak disk adetleri tablo halinde aşağıya çıkarılmıştır. parantez içerisindeki sayılar bu durumun kaç farklı kombine hali olduğunu gösterir.

X Y Z
6 0 0 (1)
0 6 0 (1)
0 0 6 (1)

5 1 0 (6)
4 2 0 (15)
3 3 0 (20)
2 4 0 (15)
1 5 0 (6)

5 0 1 (6)
4 0 2 (15)
3 0 3 (20)
2 0 4 (15)
1 0 5 (6)

0 5 1 (6)
0 4 2 (15)
0 3 3 (20)
0 2 4 (15)
0 1 5 (6)

4 1 1 (30)
3 2 1 (60)
3 1 2 (60)
2 1 3 (60)
2 2 2 (90)
2 3 1 (60)
1 1 4 (30)
1 2 3 (60)
1 3 2 (60)
1 4 1 (30)

parantez içerisindeki tüm durumların toplamı 729 dur.

evet hocam cevap 729 elinize sağlık ama 729 ilginç bi sayı değil mi sizce de?

Alıntı:

---

gereksizyorumcu'den alıntı

evet hocam cevap 729 elinize sağlık ama 729 ilginç bi sayı değil mi sizce de?

---

Evet ilginç. ramanujan olsa bu sayı hakkında hemen bir fikir verirdi :) benim aklıma sadece 6!+9 veya 9³ geliyor.

neyse zaten bu soru alıştırmaydı
her halka için 3 tane ihtimal vardır. 3^6=729 durum.
diyelimki bir çubuğa 4 halka denk geldi bunların çubuktaki sıralanışı tek şekilde bellidir. kısaca tüm durumların sayısı 729 olur.

bir iki kelime de bu 729 durumun hepsinin kurallar dahilindeki hamlelerle elde edilebileceğine dair söylenmeli, onu da uğraşanlara bırakalım.

akşam yeni hanoi sorumuzu yazıp ona uğraşırız artık.

Alıntı:

---

gereksizyorumcu'den alıntı

bir iki kelime de bu 729 durumun hepsinin kurallar dahilindeki hamlelerle elde edilebileceğine dair söylenmeli, onu da uğraşanlara bırakalım.

---

uğraşanlara yardımcı olabilecek bir öneri olarak
tümevarımla gösterilebilir sanırım 3ⁿ durum olduğundan hareketle
n=1 için doğru 3¹ durum kurallara uygun yapılıyor
n=k için doğru olsun kurallara uygun yapıldığını farzadelim
n=k+1 için 3^k+1 doğru olduğunu gösteriyoruz
k diskle 3^k durum oluyordu o halde k diskin hepsinden büyük bir disk her durum için 3çubuğun altına konulursa 3^k.3 farklı durum daha elde edilir bununda kurallara uygun olarak yapılabileceğini yine tümevarımla n=1için 2.bir diskin her çubukta gezdirilebileceğinden hareketle gösterilebilir

bu soruda ygs ayarında demiştiniz yukarıda ama başlık hanoi olunca öğrencilerimizin gözü korktu herhalde ama hatanın büyüğü sizde ne olurdu soruyu 6 elemanlı bir kümeden 3 elemanlı bir kümeye kaç fonksiyon tanımlayabiliriz diye sorsaydınız :)