Şapka problemi

Şapka problemi
Bu problem Amerika’da bayağı heyecan yaratmış.

Ali NESİN


Problem Amerika’nın en saygıdeğer gazetelerinden biri olarak kabul edilen The New York Times’ta uzun bir yazıya konu olmuş. Bu yazının ilk kısmı da The New York Times’ta yayımlanan o yazıdan kaynaklanmıştır.

'Şapka problemi 'adıyla bilinen bu problem şöyle:

Bir odaya n kişi girecek. Odada bu kişilerin başlarına, yazı tura atarak ya beyaz ya da siyah şapka konacak. Yani herkesin başında yüzde elli olasılıkla beyaz şapka olacak, yüzde elli olasılıkla siyah şapka. Herkes başkasının başındaki şapkanın rengini görecek, ama kimse kendi başındaki şapkanın rengini göremeyecek... Oyuncular aynı anda ya kafalarındaki şapkanın rengi konusunda bir tahminde bulunacaklar ya da pas geçecekler. Eğer hiçbiri yanılmazsa (pas geçen hiç yanılmaz) ve aralarından en az biri doğru yanıt verirse her oyuncu 1 milyon dolar alacak. Yoksa herbiri hava alacak.

Örneğin biri dışında hepsi pas geçerse ve o pas geçmeyen (camgöbeği ya da fıstıki gibi herhangi bir tahminde değil!) siyah ya da beyaz tahmininde bulunursa, yüzde 50 olasılıkla her oyuncu 1 milyon dolar alacak, yüzde elli olasılıkla kimse para kazanamayacak.

Eğer iki kişi pas geçmeyip tahminde bulunursa, o zaman yüzde 25 olasılıkla oyuncular parayı kazanacaklar (1 milyon doları cebe indirmek için tahminde bulunan iki kişinin de doğru tahminde bulunması gerekiyor.) Demek ki sadece bir kişinin pas geçmeyip tahminde bulunduğu strateji iki kişinin tahminde bulunduğu stratejiden daha iyi, hatta iki kat daha iyi.

Herkes pas geçerse, kimse doğru tahminde bulunmadığından, kimse para kazanamayacak...

Bu n kişi odaya girmeden önce toplanıp en iyi strateji hakkında kafa yoruyorlar. En iyi stratejilerinin (varsa) en az % 50 olduğunu gördük. Yüzde elliden daha iyi bir strateji var mı?

Amerika’nın birçok ünlü matematikçisi, (ki birçoğu Amerikalı değildir) siz bu yazıyı okuduğunuz sırada belki de, bu konu üzerinde kafa yoruyor.

Oyunun kodlar teorisiyle ilgisi var, yani bilgisayarlarla, şifrelemeyle, bilgi yollamayla, yani çağımızla... Matematik kimileyin de bir işe yarar!

Birçok matematikçi, problemi ilk duyduğunda, en iyi stratejinin yukarda açıkladığım yüzde elli parayı kazandıran strateji olduğunu düşünüyormuş. Ama daha sonra daha iyi stratejilerin varlığını kavrıyorlarmış.

Problemi ilk kez Kaliforniya Üniversitesi’nden Dr. Todd Ebert doktorasını yazarken bulmuş. Soruyu öğrencilerine sormuş. Bir sabah uyandığında, internet’te herkesin bu problemle uğraştığını görmüş...

Yine Kaliforniya üniversitesinden Prof. Berlekamp n = 3 olduğunda, yüzde 75 kazandıran bir stratejinin olduğunu bulmuş. Biz de bulalım.

Şöyle düşünelim. Üç şapkanın üçünün de aynı renk olma olasılığı 1/4’tür, çünkü 1/8 olasılıkla üç şapka beyaz, 1/8 olasılıkla üç şapka siyah olacaktır. Dolayısıyla üç şapkanın renk dağılımının 2-1 olma olasılığı 3/4’tür. Demek ki, karşısındaki iki şapkanın aynı renkte olduğunu görenler aksi tahminde bulunurlarsa, yani iki siyah şapka gören beyaz, iki beyaz şapka gören siyah derse ve diğerleri pas geçerse, 3/4 olasılıkla doğru tahminde bulunulacaktır.

Bunu şöyle de gösterebiliriz. Oyunculara 1, 2, 3 diyelim ve bu stratejiyle oynanan oyunun akışına bakalım:  

        Eğer n = 15 ise, 15/16 olasılıkla kazandıran bir strateji bulunmuş.

Oyuncu sayısı arttıkça, bilinen bir stratejinin kazanma olasılığı artıyor, hatta n sonsuza gittiğinde bu bilinen stratejinin olasılığı 1’e yakınsıyormuş.

Biz Türkler bu oyunu biraz değiştirelim. Oyuncular - hep birlikte değil de - teker teker tahminde bulunsunlar. Bu oyunda en iyi strateji var mıdır, varsa bu en iyi stratejinin başarı şansı yüzde kaçtır?

Yukardaki gibi düşüneceğiz. Kişi sayısına n diyelim. Herkese siyah şapka gelme olasılığı 1/2n’dir, dolayısıyla en az bir ki- şiye beyaz şapka gelme olasılığı 1 - 1/2n’dir. Eğer en az bir kişiye beyaz şapka gelirse, oyunun -birazdan açıklayacağım stratejiyle- kazanılacağını iddia ediyorum.

Strateji şöyle: Oyuncular sıraya dizilsinler: 1, 2, ..., n ve bu sırayla tahminde bulunsunlar. Her oyuncu, kendisinden sonra gelen oyunculardan herhangi birinin başında beyaz şapka görmüyorsa (yani kendisinden sonra gelen bütün oyuncuların şapkaları siyahsa), "beyaz" tahmininde bulunsun, eğer görüyorsa pas geçsin. Yani beyaz şapka görüldükçe pas geçilecek, görülmüyorsa "beyaz" denilecek... İlk yanıt verenden sonraki oyuncular pas geçsinler...

Örneğin, 1 numaralı oyuncu eğer hiçkimsede beyaz şapka görmüyorsa, yani herkeste siyah şapka görüyorsa "beyaz" der (daha sonrakiler pas geçer), eğer en az bir kişide beyaz şapka görüyorsa pas geçer (ve sıra ikinci oyuncuya geçer.)

Birinci oyuncu pas geçmişse, o zaman en az bir kişide beyaz şapka var demektir. En sonuncu beyaz şapka sahibi, -daha önce tahminde bulunulmamışsa- kendisinden sonra beyaz şapka görmediğinden tahminde bulunacak (daha öncekiler pas geçmiş olmalılar, daha sonrakiler de pas geçecekler) ve oyun kazanılacak.

Üç oyuncuyla neler olduğuna bakalım. Şapka dağılımlarını BBB, BBS,... gibi gösterelim. Örneğin BSB, birinci ve üçüncü oyuncularda beyaz, ikinci oyuncuda siyah şapka olduğunu gösteriyor.

Görüldüğü gibi 7/8 olasılıkla oyun kazanılıyor.

Genel olarak oyunda n kişi varsa, oyun 1 - 1/2n olasılıkla kazanılır.

Daha iyi bir strateji de olamaz, çünkü, birinci kişi, tahminde bulunduğunda, en az 1/2n olasılıkla oyun kaybedilecektir, demek ki yukarıda açıklamaya çalıştığım stratejiden daha iyi bir stratejide, birinci oyuncu hep pas geçmelidir. Birinci oyuncu hep pas geçtiğinde de bir sonraki oyuncuya hiçbir ipucu vermeyecektir, dolayısıyla ikinci oyuncuyla birinci oyuncu arasında bir fark kalmayacaktır, ve ikinci oyuncu da pas geçmek zorunda kalacaktır... Bu böyle devam eder.

Öne Çıkanlar