n kişi aynı anda şapkasının rengini tahmin etmeye çalışıyor. En iyi strateji nedir?

Question

Bir odada $n$ kişi olsun. Her kişinin şapkasına yazı tura atarak siyah ya da beyaz şapka yerleştirelim. Oyun şöyle:

Herkes, diger oyuncularin kafalarindaki sapkalarin rengini gorebiliyor ama kendi kafasindaki sapkanin rengini goremiyor. Hepsi aynı anda şapkasının rengini tahmin etmeye çalışacak. Siyah ya da beyaz, bir de pas deme hakları var. Eğer hiç kimse yanlış cevap vermez ve en az bir kişi doğru cevap verirse her biri matematik dünyası dergisinin yeni sayısını kazansın.  Ama en az bir kişi yanlış cevap verirse hepsi kaybetsin. Tabii matematik dunyasi dergisinin yeni sayisini kazanmayi kim istemez, amaclari kazanmak.

Örneğin 4 kişi var, üçü pas dedi, birisi tahmin etti ve bildi. O zaman hepsi kazanırlar. Ama eğer ikisi tahmin etti, biri bildi ama diğeri yanıldı. O zaman yine kaybediyorlar.

Bu $n$ kişinin oyuna başlamadan önce toplanıp bir strateji belirleme hakları olsun. En iyi srateji nedir?

$Örnek:$ $n=3$ olduğunda en iyi strateji şöyle:

Her oyuncu, diğer iki şapkanın rengi aynıysa o rengin tersini söylesin, farklıysa pas desin. Siyahı $S$, beyazı da $B$ ile gösterirsek:

$BBB$ , kaybederler

$BBS$, kazanırlar

$BSB$, kazanırlar

$SBB$, kazanırlar

$SSB$, kazanırlar

$SBS$, kazanırlar

$BSS$, kazanırlar

$SSS$, kaybederler

Görüldüğü gibi $\frac{3}{4}$ olasılıkla kazanıyorlar. Dileyen, 3 kişili oyun için bundan daha iyi strateji olamayacağını da kanıtlayabilir.

$n$ kişinin en iyi stratejisi nedir?

$Not:$ $n=15$ olduğunda da $\frac{15}{16}$ olasılıkla kazandıran bir strateji de biliniyor-muş.

En iyi strateji hep $\frac{n}{n+1}$ olasılıkla kazandırır mı acaba? Öyleyse kişi sayısı arttıkça kazanma olasılığımız 1'e gider.

Comments

neden akademik ? yöntemler çok ağır sanırım?

---

Öyle, cevabin hic kolay olmadigini biliyorum. Hatta en iyi stratejinin bilindiginden bile emin degilim.

Answer 1

Herkes tek sıra halinde birbirlerinin ensesine bakacak şekilde dizilsin ve herkes önündeki siyah şapkaları saysın. Eğer siyah şapka sayısı tek ise kendisine ilk sorulan kişi 'beyaz' desin. Aksi halde 'siyah' desin.

Sıradan k. kişiye şapkasının rengi sorulsun. Bu kişi önündeki siyah şapka sayısının tek veya çift olma durumuna göre cevap versin. Sonraki soru k. kişinin arkasındaki herhangi birisine sorulursa 'pas' desin. Yok eğer önündeki birisine sorulursa, bu durumda bu kişi k+1. sıradaki adamla yer değiştirsin ve önündeki siyah şapkaları saysın. Eğer k. kişi 'siyah' demişse ve k+1. kişinin önünde tek sayıda siyah şapka varsa, demekki kendi şapkası siyahtır ki tek olmuş. O halde siyah der. Yok eğer k+1. kişinin önünde çift sayıda siyah şapka varsa o halde kendi şapkası beyazdır. Bu durumda 'beyaz' der. Eğer k. kişi 'beyaz' demişse bu durumda k+1. kişi ona göre cevap verir.

Sonraki soru k. kişinin arkasından birisine gelirse bu kişi yine 'pas' desin. Yok eğer k+1. kişinin önündeki herhangi birisine sorulursa, bu kişi k+2. sırada ise yerinde sabit kalsın ve önündeki siyah şapka sayısına göre ve k+1. kişinin cevabına göre yanıtlasın. Eğer k+2. sırada değilse bu durumda k+2. sıradaki adamla yer değiştirsin ve önündeki siyah şapkaları saydıktan sonra cevaplasın.

Bütün bu n kişi bu algoritmayı takip etsin.

Böylece k. kişinin cevabı eğer yanlış ise herkes elenir. Eğer doğru ise bu durumda k. kişinin önündeki herkesin cevabı doğru olur. Bu durum bize istenilen olasılığın n/(n+1) olduğunu söyler.

Comments

Atladiginiz nokta, hepsi ayni anda sapkasinin rengini tahmin etmeye calisiyor. Kisilerin sapkalari numarali degil.

---

Eğer herkes aynı anda ve sadece kendi şapkasının rengini tahmin ederse; bu oran her halükarda 1/2 olur. Bir stratejiye gerek kalmaz. Ayrıca şapkalar numaralı değil guruptaki herkes kaç tane siyah şapka olduğunu sayıyor. Ellerindeki tek bilgi bu. Dolayısıyla matematiksel bir algoritma geliştirmelisiniz. Benim verdiğim stratejideki oran her türlü n/(n+1) 'dir. Bunu size her türlü kanıtlayabilirim.

---

Hayir, sorunun icinde verdigim 3 kisilik ornekte herkes ayni anda kendi sapkalarinin rengini tahmin ediyor ve kazanma olasiliklari hic de 1/2 degil. 3/4. Ayrica 15 kisili oyunda da herkes 'ayni anda' kendi sapkasini tahmin ediyir ve kazanma olasiliklari 15/16. 

Sizin verdiginiz cevap, baska bir sorunun cevabi. Once oyunu degistiriyorsunuz, sonra cevapliyorsunuz ama bu benim sordugum sorunun cevabi degil.

---

O zaman sizin istediğiniz kimse kimsenin verdiği cevapla ilgilenmeyecek. Bu durumda benim size şimdilik verecek bir çözümüm yok. Ama bu işin içinde nasıl çıkarlar derseniz eğer, bu adamlar her şekilde probleme saldırmaya çalışır. Tek sıra halinde de dizilirler. Yuvarlak da dizilirler. Ama dediğim gibi birbirlerinin cevaplarından bağımsız olarak düşünmemizi istiyorsanız, sizie şimdilik bir çözüm veremem.

---

Tabii ki herhangi bir sekilde dizilmekte ozgurler, zaten herkes kendisi haric herkesin sapkasini gorebiliyor.

Sadece birinin tahmini, digerininkini etkileyemez cunku herkes ayni anda tahmin etmeli. Ama bu durumda da verdigim ornekteki gibi stratejiler gelistirilebilir. Baska cozum onerileriniz olursa beklerim.