Sultan’ın Sınavı

333px-WLA_vanda_The_Seven_Sages_of_the_Bamboo_Grove

Aşağıdaki yazı Tanya Khovanova’nın “A Line of Sages” yazısının Türkçe’ye çevrilmiş halidir. İlgilinenler http://www.tanyakhovanova.com/publications/ALineOfWizards.pdf adresinden orijinal metne ulaşabilirler.

Yıllardan beri aşağıdaki bulmaca en sevdiğim bulmacadır:
Sultanın biri sarayında bulunan 100 tane bilge adamına ölümcül bir sınav yapmaya karar verir. 100 bilgenin tek sıra halinde arka arkaya dizilmelerini ister. Sultan, bilge adamların gözlerini bağlar ve her birinin kafasına siyah veya beyaz şapka geçirir. Daha sonra gözlerini açıp sırayla her bilge adama kafasında duran şapkanın rengini sorar. Sorunun cevabını  yanlış veren bilgeyi idam eder, sorunun cevabını doğru veren bilgenin hayatını bağışlar. Her bir bilge kendisinden önceki bilgelerin cevabını duyabilir fakat konuşmak yasaktır. Her bir bilge kendisinden önce gelen bütün bilgelerin şapkalarını görebilir. Bu sayede en sonda duran bilge kendisinden önce duran bütün bilgelerin şapkalarını görebilmektedir. Sultan şapka reng ni sormaya en sonda duran bilgeden başlayacaktır. Sultan, bu sınavın kurallarını bilge adamlarına 1 gün önceden verir. Bilge adamlar idam edilecek kişileri minimuma indirebilmek için nasıl bir strateji izlemek zorundadır?
Bulmacann çözümünü aşağı da bulabilirsiniz fakat yazıyı okumaya devam etmeden önce bulmacanın çözümünü bulmaya çalışmanızı tavsiye ederim. Ayrıca bu yazıda yukarıdaki bulmaca dışında başka bulmacalar da bulacaksınız. Aynı tavsiye onlar için de geçerlidir.
Bulmacamıza geri dönecek olursak, bilge adamların birbirleriyle iletişim kurması yasaklanmış durumda. Yani hiçbir şekilde öksüremezler, hapşıramazlar ya da önlerindekini dürtemezler. Ses tonlarını değiştirmeleri bile yasaklanmış durumdadır. Sadece “Siyah” ya da “Beyaz” deme hakları vardır. Bir çok insan bilge adamların yarısının öleceğini bekler. Aslında eğer tamamen rastgele bir şekilde tahmin yaparlarsa gerçekten de bilge adamların yarısı ölür. Bu bulmacanın çözümünde şaşırtıcı bir şekilde aslında sadece bir kişinin hayatını tam anlamıyla riske atacağını göreceğiz. En arkada duran bilge kendisi dışında bütün şapkaları göreceğinden kendinden sonra gelen bilgelere şapkalarının rengini anlamalarını sağlayan bir işaret verir. En arkadaki bilge bütün siyah şapkaları sayar. Eğer siyah şapka sayısı çift ise kendi şapkasının beyaz olduğunu söyler. Siyah şapka sayısı tek ise kendi şapkasının beyaz olduğunu söyler. Burada kendi şapkasının siyah veya beyaz olması önemli değildir. En arkadaki bilge sırasını savdıktan sonra ondan sonra gelen bilge yine siyah şapkaları sayar. Eğer tek sayıda siyah şapka varsa kendisinin siyah şapkası olduğunu anlar ve siyah der. Eğer siyah şapka sayısı çift ise kendisinin şapkasının beyaz olduğunu anlar ve beyaz der. Böylece en arkadaki bilge haricinde bütün bilgeler kendi şapkalarını bulabilir.

Bir sonraki doğal soru:  Eğer daha fazla renk olsaydı stratejimiz nasıl olurdu?
İki renkli ve üç renkli problemler, 23. Rusya Matematik Olimpiyatlarında 1997 yılında sorulmuştur.

Bilgelerin sınav başlamadan hangi renklerde şapkalar takacağını bildiklerini varsayacağız. Aslında böyle bir varsayımda bulunmak zorunda değiliz. N tane rengin listelendiğini ve bu listenin bilindiğini ve bizim şapkalarımızın bu listedeki renklerden oluştuğunu varsayabiliriz. Ayrıca bilgelerin şapkaların rengini herhangi bir uzaklıktan seçebildiğini de varsaymak zorundayız. “Şaşırtıcı bir şekilde şapkaların renk sayısının artması hayatını riske atan bilgelerin sayısını değiştirmez. Stratejimiz şöyle oluşur:

Her bir renge bir sayı veriririz. En arkadaki bilge kendinden sonra gelen bütün şapkalara bakar ve şapkalara verilmiş olan sayıları toplar. Sayıları topladıktan sonra kendi sayısının bulduğu toplamın   modulo N de çıkan sonucu olduğunu söyler.

Bu bulmaca hata düzeltme kodlarına dayanır. Verilmiş her a sayısına

a + b = 10 k

olacak şekilde bir b rakamı verdiğimizi varsayalım. Bu sayede 10 a bölünebilen
bu toplamın aktarımında b rakamı okunamaz hale geldiğinde ya da bozulduğunda yeniden düzeltilebilir bir hale getirmiş oluruz. Benzer bir şekilde sondaki bilge adam kendisinin şapkası dışında bütün şapkaları gördükten sonra ve bütün şapkaların toplamını modulo N olarak hesapladıktan sonra kendi giydiği şapkayı da hesaplayabilir. Böylece bütün diğer bilge adamlar da aynı yolu kullanarak kendi şapkalarını bulabilirler.

Yakın bir zamanda yukarıda bahsettiğim bulmacanın değişik bir türünü Konstantin Knop ve Alexander Shapovalov’dan öğrendim.

Sultanın biri 100 tane bilge adamına ölümcül bir sınav yapmaya karar verir. Bilgeleri tek sıra halinde arka arkaya dizer. Sultanın her biri farklı renkte olan 101 tane şapkası vardır ve bilge adamlar bu renklerin hangi renkler olduğunu bilir. Sultan bir şapka hariç bütün şapkaları bilge adamlarına giydirir ve her bir bilgeye kendi başında bulunan şapkanın rengini sorar. Bilgeler birbirlerinin şapkasını görebilir ve önlerinde duran bilgenin cevabını duyabilirler fakat birbirleriyle konuşmaları yasaktır. Ayrıca daha önce söylenmiş bir rengi söylemeleri yasaklanmıştır. Kendi şapkasını yanlış bilen bilge idam edilecek, doğru bilen bilgenin ise hayatı bağışlanacaktır. Sultan şapka renklerini sormaya en sondan başlayacaktır. Sınavın kuralları bilge adamlara bir gün önceden verilir. Bilge adamlar idam edilecek kişi sayısını en aza indirebilmek için nasıl bir strateji izlemelidir?

Bulmacayı ilk kez okuyan okura bir önceki bulmaca ile bu bulmaca, şapka renklerinin fazla olmasının dışında, farksız gelebilir. En arkadaki bilge diğerlerinin şapkalarını toplar ve modulo 101 de söyler ve sırası gelen her bir bilge aynı yolu izler. Fakat burada gözden kaçan bir ayrıntı vardır. Bulmacaya göre bilge adamların daha önce söylenmiş bir rengi söylemesi yasaktır. Örneğin bilgelerden biri şapkasının renginin kırmızı olduğunu söylerse bundan böyle ondan sonra gelen hiçbir bilge şapkasının rengi kırmızı olsa bile şapkasının renginin kırmızı olduğunu söyleyemez.

Şimdi daha önceki yöntemimizin bu bulmacaya uyarlayıp uyarlayamayacağımızı araştıracağız. En arkadaki bilge bütün renkleri toplayıp modulo 101 de söyler.  99 /101 olasılıkla söylediği renk önünde duran bilgelerden birinin şapkasının rengidir. Yani sırada bulanan birinin şapkasının renginin daha önceden söylendiği neredeyse garantilenmiş durumdadır. Bütün diğer bilgeler aynı şekilde hesaplarını yapar ve şapkalarının rengini söyler. Sıra daha önce rengi söylenen bilgeye gelir fakat bilge kendi rengini bilmesine rağmen o rengi söylemesi yasaklanmıştır.

Şimdi bir an için sultanın göründüğü kadar acımasız olmadığını ve sultanın söylenen rengin tekrar söylenince sadece rengi tekrar eden kişiyi öldürdüğünü varsayalım. Bu durumda rengi daha önce söylenmiş olan bilge kendi rengini doğru söyler, kendini feda eder ve diğerlerini kurtarır. Fakat bizim sultanımız oldukça acımasız biri. Sultan eğer renk tekrarı olursa herkesi öldüreceğini kurallara koymayı ihmal etmez. Sıradaki bilge adamlardan birinin şapkası son sırada bulanan bilgenin söylediği renk ise o şapkaya sahip bilgenin doğruyu söyleyip, renk tekrarı yapıp herkesi kurban etmekten daha iyi bir yolu var mıdır? Son sıradaki bilgenin söylediği renkte şapkaya sahip olan bilge eğer
söylenmemiş bir renk söylerse bu sefer bütün stratejiyi bozar ve önündeki bilgeleri riske atar.

Problemin yazarları aşağıdaki çözümü öneriyorlar: Son sıradaki bilgenin söylediği renk şapkaya sahip olan talihsiz bilge kendi rengi yerine ilk sıradaki bilgenin şapkasının rengini söyler. Sırada olan diğer bilgeler son sıradaki bilge dışındaki birinin en önde duran bilgenin şapkasının rengini söylediğinde o kişinin renk tekrarı yapmamak için söylediğini anlar ve hesaplarını değiştirmeden doğru tahmin yapmaya devam ederler. Bu durumda en talihsiz olan ilk sırada duran bilgedir. Çünkü onun rengi daha önce söylenmiştir ve ondan sonra kimse olmadığından yanlış tahmin yapmaya mahkumdur. Bu çözümde en fazla 3 kişi hayatını kaybeder. İlk olarak son sırada duran bilge hayatını riske atar. Daha sonra son sıradaki bilgenin söylediği renkte şapkaya sahip olan bilge hayatını kaybeder, son olarak ise ilk sırada duran bilge hayatını kaybeder. 3 kişinin hayatını riske atmasına rağmen aslında sadece bir kahraman vardır. Son sırada duran bilgenin kendi şapkasını bilme olasılığı %50 dir. Fakat son sıradaki bilge bu şansını kullanmaz ve diğerlerini kurtarmak için hayatını feda eder. Diğer iki kişi her ne olursa olsun zaten öleceklerdir.

Yukarıda bahsettiğimiz problem Mart 2013’te kasabalar turnuvasında çıkmıştır. Problemi iki zorluk derecesine ayırmışlar. Birinci derecede “bilgelerin yarısından çoğunu kurtarmanın bir yolu var mıdır?” diye sorulmuş ki biz bunu bulmayı başardık. İkinici soruda ise “Sadece tek bir bilgenin hayatını riske attığı bir strateji bulunabilir mi?” diye sorulmuş. Şu ana kadar anlattığımız çözüm dışında aslında anlatmadığımız bir kısım daha var. Aslında sadece bir bilge dışında diğerlerini kurtarabilen bir çözüm daha var. Fakat biz daha iyi bir çözüm varken neden bu çözümü anlattık? Birinci olarak anlattığımız çözüm oldukça güzel bir çözüm. İkinci olarak ise anlattığımız çözüm sultanın 102 ya da daha fazla farklı renkte şapkası olması durumunu genelliyor.

Şimdi tekrar bulmacamıza geri döneceğiz ve bir kişi dışında bütün bilgeleri kurtaracağız. Hayatını feda etmesi gereken elbette son sıradaki bilge olacak. Çünkü onun kurtulması için elimizdeki bilgiler yetersiz kalıyor. Eğer bir kişi dışında diğerlerini kurtarmak istiyorsak son sırada duran bilge ya kafasındaki şapkayı bilmek zorunda ya da dışarıda kalan şapkanın rengini söylemek zorundadır.
Elde ettiğimiz sonuçlara göre problemimiz sayılar teorisi ve modulo sayılarla ilgili değil. Problemimiz tamamen permütasyonlarla ilgili. Son sırada duran bilge adamın arkasında duran hayali bir bilge adamın olduğunu ve bu hayali bilge adamın dışarıda kalan şapkayı kafasına taktığını varsayabiliriz.
Her bir renge bir sayı vererek 101 uzunluğunda bir permütasyon fonksiyonu oluşturabiliriz.
Bu durumda hayali olmayan son sırada duran bilge adam diğerlerini kurtarmak için nasıl bir yol izlemelidir?

Son sırada duran bilge adam görmediği iki renkten birini seçer. Son sırada duran bilge adam sırasını savdıktan sonra diğerleri rahatlıkla kendi şapkalarını bilebilir. Çünkü ilk olarak her bir bilge kendisinden önceki bilgelerin şapkalarını görebilir. Böylece şapkasını tahmin etmek için 2 seçeneğe düşer. Bu 2 seçeneklerden biri zaten bilgenin kafasındaki şapkadır. Diğeri ise son sıradaki bilge adamın cevabına göre değişir. Eğer bilge adam doğru tahminde bulunursa ondan sonra gelen bilge adam 2 . seçenek olarak dışarıda kalan şapkayı seçer. Kendisinden önce gelen bilge adamın cevabı doğru olduğu için dışarıda kalan şapkanın hangi renk oduğunu kolaylıkla bulur ve böylece kendini kurtarır. Eğer son sıradaki bilge adam yanlış cevap verirse ondan sonra gelen bilge yine dışarıda kalan şapkayı anlar ve kendi şapkasını kolaylıkla bulabilir.

 

Boğaç Karçıka

Bilkent Üniversitesi Eğitim Bilimleri Enstitüsü Yüksek Lisans Öğrencisi

İlk yorum yapan olun

Bir yanıt bırakın

E-posta hesabınız yayımlanmayacak.


*