Bu tür sorulara ısınmak için bazen daha basit bir versiyonla başlamak işe yarar diye düşündüm ve üç kapıyla başladım.
[table id=12 /]
Yukarıdaki tabloda sütunlar kapıları göstermekte. Satırlar da günleri. Eğer bir kapının arkasında verilen günde bir kedi olabilirse o kare bir kara kediyle gösterilmiştir. Eğer o kapının arkasında kedi olma şansı yoksa kırmızı çarpı işaretiyle gösterilmiştir. Yeşil işaret ise o gün açtığımız kapıyı gösteriyor.
Üç kapılı oyunda ilk gün 2. kapıyı açıyoruz. Eğer arkada kedi varsa oyun bitiyor. Yoksa kapıyı kapatıyoruz ve kedi kenar kapıların birinde olduğundan gece bu kenar kapıyı terk edip orta kapıya geliyor. Bu nedenle ikinci gün kedi kenar kapıların arkasında olamaz. Ertesi gün yeniden 2. kapıyı açıyoruz ve kediyi buluyoruz.
Şimdi aynı soruyu 4 kapı için çözmeye çalışalım. Aslında buradan sonraki çözümleri bir arkadaştan öğrendim ve sonuçları anlamaya çalışıp bir tablo haline getirdim sadece.
[table id=13 /]
Kapıları 2-3-3-2 sırasına göre açtığımızda görüldüğü gibi 4. günde kedinin arkasında olabileceği son kapıyı da bulmuş oluyoruz. İkinci kapıdan başlayıp sondan ikinci kapıya kadar gittik ve sondan ikinci kapıyı iki kere açtık. Bu yöntemi bir de 5 kapı için deneyelim, bakalım bulduğumuz düzen işe yarıyor mu?
[table id=14 /]
Şansımızı bir de 6 kapı için deneyelim.
[table id=15 /]
Ve son olarak da 7 kapı için problemin çözümünü de bu tabloda görelim.
[table id=16 /]
Peki bu çözüm neden işe yarıyor?
Kedi her gün ya bir sağa ya da bir sola hareket etmek zorunda. Gün numarası her gün bir artarken, kedinin saklandığı kapının numarası ya bir artacak ya da bir azalacak. Dolayısıyle gün ve kapı değişiminin toplamı her gün ya 0 ya da iki olacak. Buradan da şu sonucu çıkarabiliriz:
Eğer kedi ilk gün tek numaralı bir kapının arkasındaysa, oyun boyunca arkasında olduğu kapı numarasıyla gün numarasının toplamı bir çift sayı olacaktır. Aynı şekilde ilk gün çift sayılı bir kapının arkasındaysa bu toplam hep tek olacaktır.
İlk gün 2 numaralı kapıyla başlayıp hep yukarı doğru gidersek biz de her gün tek sayılı bir toplam üretiriz. Varsayalım kedi de çift sayılı bir kapının arkasında başladı. O zaman her gün o da tek sayılı bir toplam üretecek. İkimizin sayısı arasındaki fark her zaman çift olacak ve bu fark aramızdaki kapı sayısı kadar olacak. İkinci kapıdan başlayınca birinci kapıyı atladık ama bu varsayımımıza göre kedinin burada olamayacağını düşündük. Evet, kedi burada olabilir ama o sorunu daha sonra çözeceğiz. Kapı numaralarını artırarak gittiğimizde kediyi sağa doğru sıkıştırmış oluyoruz. N-2 gün sonra sondan ikinci kapıya ulaşırız. Artık bizden iki kapı uzak bir yer kalmadı. Kedi bu kapının arkasında olmalı, tabii ki kedi de oyuna çift sayılı bir kapının arkasında başladıysa. Eğer sondan ikinci kapıda kediyi bulamadıysak varsayımımız yanlış demektir ama oyunun sadece yarısı bitti henüz.Demek ki kedi tek sayılı bir kapının arkasında başlamış. Bu noktada kedinin yapamadığı ama bizim yapabileceğimiz bir hamle yardımıyla kendi toplamımızı çifte çevirecek hamleyi yapıyoruz, yani son açtığımız kapıyı tekrar açıyoruz. Bu hamle ayrıca kedinin bir gün önce son kapının arkasında olma durumunu da hallediyor. Eğer son kapının arkasında idiyse şimdi tekrar açtığımız kapının arkasında olmalı. Bundan sonra kediyi sola doğru sıkıştırdık demektir ve toplamlarımız da senkronize olmuş durumda, ikimiz de çift toplamlardayız ve kedinin kapısıyla bulunduğumuz yer arasında hep ikinin katları kadar fark olacak ve bu fark her gün ya 2 azalacak (kedi bize doğru kapı değiştirirse) ya da aynı kalacak (kedi de bizim gibi sola doğru kaçarsa). Bu şekilde eninde sonunda kediyi 2 numaralı kapının arkasında yakalayacağız.
Bu şekilde N kapı için kediyi 2N-4 adımda kesin olarak bulabiliyoruz. Bu çözümün optimum çözüm olup olmadığını bilmiyorum ama öyle olduğunu sanıyorum. İspatı bilen ya da bulan bana haber verirse sevinirim.