Ay: Ocak 2018

Soru

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.

Soru

Soruyu ilk gördüğümde mantıkçıların sorduğu ilk iki sorunun ne kadar gereksiz olduğunu düşündüm. Örneğin her mantıkçı hücresindeki elma sayısını kullanarak “Hücremde şu kadar elma mı var?” şeklinde sorsa, hepsinin cevabı evet olacak ve üç mantıkçı da toplam elma sayısını hemen bilecekti.

Bu şark kurnazlığı çözümünü engellemek için ilk iki soru verilmiş. Her hücrede farklı sayıda elma olması gerektiğinden toplam en az 1+2+3 = 6 ve en fazla da 7+8+9=24 olabilir. Ayrıca soruların cevaplarından toplamın çift ve asal olmadığını biliyoruz. 6 ve 24 arasındaki çift ve asal sayıları sildiğimizde geriye sadece 9, 15 ve 21 toplamları kalır. Herkes soruları ve cevapları duyduğundan üç mantıkçı da iki soru sonunda olasılıkları bu üç duruma indirmiş olacaktır.

Üçüncü mantıkçı tek bir evet hayır sorusuyla bu üç durumu birden çözemeyecektir ama soruya göre buna ihtiyacı da yoktur. Cevabı hangi mantıkçı bulursa bulsun, hepsi kurtulacak. Üçüncü hücrede 5 elma olduğuna göre üçüncü mantıkçı açısından olası elma dağılımlarına bakalım.

9 = 1 + 3 + 5     
21 = 7 + 9 + 5  
15 = 1 + 9 + 5
15 = 2 + 8 + 5
15 = 3 + 7 + 5
15 = 4 + 6 + 5

Varsayalım ilk iki mantıkçı bir şekilde toplamın 9 ya da 21 olduğunu biliyor (yani toplam 15 değil). Bu durumda sadece iki durum mümkün. Ya mantıkçıların hücrelerinde 1 ve 3 elma var, ya da 7 ve 9 elma. Eğer mantıkçıların birinin hücresinde 1 elma varsa o mantıkçı toplamın 21 olamayacağını hemen bilir çünkü bir hücrede en fazla 9 elma olabilir ve 21 – 1 = 20 elmayı iki hücreye dağıtamayız. Dolayısıyla 1 elmalı mantıkçı toplamın 9 olacağını bilecektir. 3 Elmalı mantıkçı da toplamın 9 olduğunu bilir çünkü 21 olsaydı diğer iki hücreye 18 elma kalacaktı ama her hücrede farklı sayıda elma olmak zorunda olduğundan bu dağılım mümkün olmayacak. Diğer şekilde de eğer toplam 21 ise 9 elmalı hücredeki mantıkçı diğer hücrelerde en az bir elma olacağından toplamın 9 olamayacağını anlayacak ve doğru toplam olan 21’i bulacak. 7 elmalı hücredeki mantıkçı da 9 olamayacağını bilir, çünkü her hücrede farklı sayıda elma olmak zorunda ve bu durumda toplam en az 7+2+1=10 > 9 olabilir.

İlk iki mantıkçıya bu yardımı yapmanın en kolay yolu heralde doğrudan “Toplam elma sayısı 15 mi?” diye sormak olur. Eğer cevap evet ise herkes toplamı biliyordur, değilse birinci ve ikinci mantıkçı bir önceki paragraftaki gibi düşünerek çözümü bulacaktır.

Üçüncü mantıkçının şöyle bir soru sorduğu duruma bakalım:

“Diğer iki hücredeki elmaların toplamı 10 mu?”

Bu soru dolaylı olarak toplamın 15 olup olmadığını sorsa da diğer iki mantıkçıya aynı bilginin gittiğini sanmıyorum. Bu kanıya ilk iki sorunun çok daha kolay olabileceği ama mantıkçıların böyle bir çabasının olmadığı noktasından çıkarak ulaştım, yani çok iyi mantıkçılarla yanılıyor da olabilirim.

Bundan başka merak ettiğim bir şey de acaba üçüncü mantıkçının toplamı kendi başına bulabileceği bir soru var mıdır?

Örneğin, “aklımda 0 ya da 6 sayısını tutuyorum ve bu tuttuğum sayı ile toplam elma sayısının toplamı 15’ten fazla mı?”. Eğer toplam 21 ise cevap her zaman evettir. Eğer 9 ise hayır. “Bilmiyorum” derse ya da cevap veremezse toplam 15’tir. Bu tür soruların problemin soruluş şekline göre yasak olup olmadığından emin değilim ama yine de böyle bir imkandan da bahsetmek istedim. Yani probleme göre cevabı evet ya da hayır olan bir soru sorulabilir ve burada kasıtlı olarak cevabının “bilmiyorum” olabileceği bir soru soruyoruz.