Eğer bir kişi başındaki şapkayı rastgele bilmeye çalışırsa doğru tahmin yapma şansı yüzde elli olacaktır. Demek hiçbir strateji bulamazsak en kötü ihtimalle yüzde elli kurtulma şansları var.
Şimdi problemin çözümünde kullanacağımız bazı tanımlamaları yapalım.
Gösterim kolaylığı açısından kırmızı şapkayı 1, ve mavı şapkayı da 0 ile göstereceğiz. Böylece herhangi bir şapka dağılımı ikili düzendeki bir rakam dizisiyle eşdeğer olacak. Bu ikili düzendeki şapka dağılımlarını da $D_{i}$ ile göstereceğiz. Buradaki $i$ indeksi ikili düzendeki sayının onluk düzendeki karşılığı olacak.
$i$ birden $N$'e kadar (ilk soruda $N = 3$) olmak üzere mahkumları sıra numaraları ile $m_{i}$ şeklinde göstereceğiz. Sıralamaya sağ basamaktan başlayacağız.
Hamming uzaklığı: İki şapka dağılımı arasındaki mesafeyi $d(D_{i}, D_{j})$ ile göstereceğiz ve bu da kısaca aynı uzunluktaki iki ikili düzendeki sayının farklı rakamlara sahip pozisyonlarının adedi olacak. Örnek olarak $d(000, 111) = 3$ ve $d(011, 110) = 2$ (Yani pozisyonları numaralandırmaya sağdan başlarsak, birinci pozisyondaki rakamlar farklı, ikinci pozisyondaki rakamlar aynı, üçüncü pozisyondaki rakamlar da farklı).
Şimdi Hamming uzaklığı ile biraz oynayalım.
$N$ şapka ile belli bir $D_{i}$ dağılımı için Hamming uzaklığı 1 olan $N$ farklı pozisyon vardır. Bunu görmek için tanım üzerinde düşünmek gerek. Hamming uzaklığı 1 demek sadece bir pozisyondaki rakamlar farklı demek olduğundan ve bu sayılarda $N$ farklı pozisyon olduğundan toplam $N$ farklı sayı yazabiliriz.
Örnek: 5 şapka ile 00000 dağılımına uzaklığı bir olan dağılımlar 00001, 00010, 00100, 01000 ve 10000 saylarıdır.
Bu noktada problemle ilgili bir takım gözlemler yapmaya çalışalım.
G1: Bir mahkum kendi başındaki şapkanın rengini göremediği için onun açısından olası iki dağılım vardır ve bu dağılımlar arasındaki Hamming uzaklığı birdir, çünkü diğer pozisyonlardaki rakamlar eşit olduğundan sadece kendi pozisyonundaki rakamlar farklı olacaktır.
Örnek: 5 şapka için 3. sradaki mahkum sadece beyaz şapkalar görüyorsa olası dağılımlar 00000 veya 00100 olacaktır. Bu durumda da $d(00000, 00100) = 1$ olacaktır.
G2: Belli bir D dağılımı için buna uzaklığı 1 olan dağılımlarda en fazla bir mahkum o anki dağılımın bu D dağılımına olan uzaklığının en fazla 1 olduğunu bilebilir. Her mahkum için şöyle bir yol izleyebiliriz. $i$ numaralı mahkum D dağılımından kendi pozisyonundaki rakamı çıkararak $N-1$ basamaklı bir sayı üretir. Sonra da diğer mahkumların şapkalarına göre kalan dağılımı ikilik düzende yazar. Eğer bu iki dağılım arasındaki mesafe 0 ise sadece kendi şapkası farklı olabileceğinden uzaklık da en fazla 1 olacaktır. Diğer mahkumlar aynı işlemi yaptığında kendi şapkaları hariç uzaklık zaten 1 olduğundan bu mahkumlar açısından uzaklık 1 veya 2 olacağından emin olamayacaklardır.
Örnek: 5 şapka için kararlaştırılmış dağılım 01001 olsun. O anki şapka dağılımı da 11001 olsun. Tabii ki $d(01001, 11001) = 1$. Birinci mahkum problemden kendisini çıkarırsa kararlaştırılmış dağılım 0100 ve o anki dağılım da 1100 olacaktır. $d(0100, 1100) = 1$ olduğundan bu mahkum kendi kafasında kırmızı (1) şapka varsa uzaklığın bir kalacağını ama mavi (0) şapka varsa uzaklığın ikiye çıkacağını bildiğinden emin olamayacaktır. Sadece 5. sıradaki mahkum bu uzaklığın en fazla 1 olduğundan emindir.
Burada şöyle bir notasyon tanımlayalım. $D_{i}/j$, $N$ şapka için verilen bir şapka dağılımı için j pozisyonundaki şapka çıkarıldığında kalan $N-1$ şapkalı dağılım olsun. O zaman $d(D_{i}, D_{k}) <= d(D_{i}/j, D_{k}/j) + 1$
Verilen bir $D_{i}$ şapka dağılımına olan Hamming uzaklıkları 1 olan dağılımlar kümesine $K_{1}{i}$ (1-komşuluğunda olan dağılımlar) kümesi diyelim.
G3: İki şapka dağılımı $D_{i}$ ve $D_{j}$ verilsin. Eğer $d(D_{i}, D_{j}) \ge 3 \implies K^{1}_{i} \cap K^{1}_{j} = \emptyset$. Yani iki dağılım arasındaki mesafe 3 veya daha büyükse bunların direkt komşuluğunda (yani 1-komşuluğunda) ortak dağılım yoktur. Eğer ortak bir dağılım olsaydı bu dağılım verilen iki dağılıma da 1 mesafesinde olduğundan iki dağılımın birbirine uzaklığı da en fazla 2 olacaktı (Haming uzaklığı bir metriktir ve üçgen eşitsizliğinden bu sonuç çıkar).
G4: İki şapka dağılımı $D_{i}$ ve $D_{j}$ verilsin. Eğer $d(D_{i}, D_{j}) = 2 \implies \left\vert K^{1}_{i} \cap K^{1}_{j} \right\vert = 2$. İki dağılım arasında iki pozisyondaki rakamlar farklı olduğundan kesişim kümesinde de 2 eleman vardır.
Örnek: 1010 ve 1111 verilmiş olsun. 1-komşuluğundaki ortak elemanlar $N-2$ adet ortak şapkalara sahip olacak ve bir durumda bir şapkayı birinci durumda ve diğerini ikinci durumdan, ikinci durumda da tam tersi şekilde. Yani 1110 ve 1011.
G5: Bir önceki gözlemdeki durumda en fazla iki mahkum o anki durumun kararlaştırılan durumlara uzaklığının en fazla 1 olduğunu bilecektir. İki mahkum da sadece bir kararlaştırılmış durumu bulabilecektir, diğer durum için kendisi açısından uzaklık en fazla iki olacaktır.
Örnek: 1010 ve 1111 verilmiş olsun. 1-komşuluğundaki ortak elemanlardan 1110 durumuna bakalım. Birinci mahkum ikinci durum için 1-komşuluğunda olduğunu anlayacaktır ama üçüncü mahkum bunu destekleyemeyecektir, fakat üçüncü mahkum da birinci durum için 1-komşuluğunda olduklarını bilecektir. Diğer ortak eleman 1011'de ise birinci mahkum birinci durum için 1-komşuluğunu bilecek, üçüncü mahkum ise ikinci durum için 1-komşuluğunu bilecek.
Şimdi kabaca bir strateji tanımlayalım. Bu aşamada bazı kısımlar hala çözülmemiş kalacak ama problemi başka bir probleme dönüştürmüş olacağız.
Mahkumlar $M$ adet birbirine uzaklıkları 3 (ya da mümkün değilse 2) olan dağılımlar kararlaştırsınlar. Bu dağılımları $Kod_{i}$ şeklinde gösterelim ($1 <= i <= M$). Tahmin zamanı geldiğinde mahkumlar o an gördükleri durumun bu kararlaştırılmış kodlara uzaklıklarını hesaplasın. Eğer bu uzaklıklar her kod için birden büyük olabiliyorsa o mahkum pas geçsin. Eğer bu uzaklık bir kod için en fazla 1 oluyorsa o zaman mahkum sonuç o kod olmayacak şekilde tahminde bulunsun. Bu şekilde o kodda tanımlanmış dağılımda hepsi yanlış cevap verecek fakat buna karşın o kodun 1-komşuluğundaki her dağılım doğru tahmin edilmiş olacak. Bu da toplam olasılığı çok daha fazla artıracaktır. $M$ adet kod dışındaki her dağılım doğru tahmin edildiğinde de olasılık $\frac {2^N - M}{2^N}$ olacaktır.
Bu strateji için çözülmesi gereken sorular:
Şimdi bu sorulara cevap aramaya çalışayım.
1. $N$ mahkumla oynanan oyunda $2^N$ değişik dağılım olacağından ve seçilecek her kod için 1-komşuluğunda $N$ dağılım olacağından $M \ge \frac {2^N} {N+1}$ olacaktır.
2. Kodlar seçilirken her ikili kombinasyon arasındaki Hamming uzaklığının 3 (en kötü ihtimalle 2) olmasına dikkat edilmelidir.
3. Evet. İki kod arasındaki uzaklık 2 ve ortak dağılımlar da iki koda eşit uzaklıkta. İki mahkum da tahminlerinde seçilmiş kodlardan uzaklaşacağına göre iki kodun orta noktasında (ortak dağılımda) buluşacaklardır.
4. Bunu bilmiyorum. Literatüre bakmak lazım. $k$ pozitif bir tamsayı olmak üzere $N=2^k - 1$ şartını sağlayan mahkum sayısı için daha iyi bir çözüm yok sanırım (Ebert's version). Bu durumda da kazanma olasılığı $\frac {2^k - 1}{2^k}$ oluyor.
Son olarak üç mahkum için $Kod_{1} = 000$ ve $Kod_{2} = 111$ tanımlarsak, $d(Kod_{1}, Kod_{2}) = 3$ olduğundan $M=2$ olacak şekilde bütün dağılımları sınıflandırabiliyoruz. Sınıfları aşağıdaki tabloda görebiliriz.
Şimdi de oyuncuların yukarıdaki stratejiye göre her dağılımda verecekleri cevapları tablo halinde görelim.
Şimdi Hamming uzaklığı ile biraz oynayalım.
$N$ şapka ile belli bir $D_{i}$ dağılımı için Hamming uzaklığı 1 olan $N$ farklı pozisyon vardır. Bunu görmek için tanım üzerinde düşünmek gerek. Hamming uzaklığı 1 demek sadece bir pozisyondaki rakamlar farklı demek olduğundan ve bu sayılarda $N$ farklı pozisyon olduğundan toplam $N$ farklı sayı yazabiliriz.
Örnek: 5 şapka ile 00000 dağılımına uzaklığı bir olan dağılımlar 00001, 00010, 00100, 01000 ve 10000 saylarıdır.
Bu noktada problemle ilgili bir takım gözlemler yapmaya çalışalım.
G1: Bir mahkum kendi başındaki şapkanın rengini göremediği için onun açısından olası iki dağılım vardır ve bu dağılımlar arasındaki Hamming uzaklığı birdir, çünkü diğer pozisyonlardaki rakamlar eşit olduğundan sadece kendi pozisyonundaki rakamlar farklı olacaktır.
Örnek: 5 şapka için 3. sradaki mahkum sadece beyaz şapkalar görüyorsa olası dağılımlar 00000 veya 00100 olacaktır. Bu durumda da $d(00000, 00100) = 1$ olacaktır.
G2: Belli bir D dağılımı için buna uzaklığı 1 olan dağılımlarda en fazla bir mahkum o anki dağılımın bu D dağılımına olan uzaklığının en fazla 1 olduğunu bilebilir. Her mahkum için şöyle bir yol izleyebiliriz. $i$ numaralı mahkum D dağılımından kendi pozisyonundaki rakamı çıkararak $N-1$ basamaklı bir sayı üretir. Sonra da diğer mahkumların şapkalarına göre kalan dağılımı ikilik düzende yazar. Eğer bu iki dağılım arasındaki mesafe 0 ise sadece kendi şapkası farklı olabileceğinden uzaklık da en fazla 1 olacaktır. Diğer mahkumlar aynı işlemi yaptığında kendi şapkaları hariç uzaklık zaten 1 olduğundan bu mahkumlar açısından uzaklık 1 veya 2 olacağından emin olamayacaklardır.
Örnek: 5 şapka için kararlaştırılmış dağılım 01001 olsun. O anki şapka dağılımı da 11001 olsun. Tabii ki $d(01001, 11001) = 1$. Birinci mahkum problemden kendisini çıkarırsa kararlaştırılmış dağılım 0100 ve o anki dağılım da 1100 olacaktır. $d(0100, 1100) = 1$ olduğundan bu mahkum kendi kafasında kırmızı (1) şapka varsa uzaklığın bir kalacağını ama mavi (0) şapka varsa uzaklığın ikiye çıkacağını bildiğinden emin olamayacaktır. Sadece 5. sıradaki mahkum bu uzaklığın en fazla 1 olduğundan emindir.
Burada şöyle bir notasyon tanımlayalım. $D_{i}/j$, $N$ şapka için verilen bir şapka dağılımı için j pozisyonundaki şapka çıkarıldığında kalan $N-1$ şapkalı dağılım olsun. O zaman $d(D_{i}, D_{k}) <= d(D_{i}/j, D_{k}/j) + 1$
Verilen bir $D_{i}$ şapka dağılımına olan Hamming uzaklıkları 1 olan dağılımlar kümesine $K_{1}{i}$ (1-komşuluğunda olan dağılımlar) kümesi diyelim.
G3: İki şapka dağılımı $D_{i}$ ve $D_{j}$ verilsin. Eğer $d(D_{i}, D_{j}) \ge 3 \implies K^{1}_{i} \cap K^{1}_{j} = \emptyset$. Yani iki dağılım arasındaki mesafe 3 veya daha büyükse bunların direkt komşuluğunda (yani 1-komşuluğunda) ortak dağılım yoktur. Eğer ortak bir dağılım olsaydı bu dağılım verilen iki dağılıma da 1 mesafesinde olduğundan iki dağılımın birbirine uzaklığı da en fazla 2 olacaktı (Haming uzaklığı bir metriktir ve üçgen eşitsizliğinden bu sonuç çıkar).
G4: İki şapka dağılımı $D_{i}$ ve $D_{j}$ verilsin. Eğer $d(D_{i}, D_{j}) = 2 \implies \left\vert K^{1}_{i} \cap K^{1}_{j} \right\vert = 2$. İki dağılım arasında iki pozisyondaki rakamlar farklı olduğundan kesişim kümesinde de 2 eleman vardır.
Örnek: 1010 ve 1111 verilmiş olsun. 1-komşuluğundaki ortak elemanlar $N-2$ adet ortak şapkalara sahip olacak ve bir durumda bir şapkayı birinci durumda ve diğerini ikinci durumdan, ikinci durumda da tam tersi şekilde. Yani 1110 ve 1011.
G5: Bir önceki gözlemdeki durumda en fazla iki mahkum o anki durumun kararlaştırılan durumlara uzaklığının en fazla 1 olduğunu bilecektir. İki mahkum da sadece bir kararlaştırılmış durumu bulabilecektir, diğer durum için kendisi açısından uzaklık en fazla iki olacaktır.
Örnek: 1010 ve 1111 verilmiş olsun. 1-komşuluğundaki ortak elemanlardan 1110 durumuna bakalım. Birinci mahkum ikinci durum için 1-komşuluğunda olduğunu anlayacaktır ama üçüncü mahkum bunu destekleyemeyecektir, fakat üçüncü mahkum da birinci durum için 1-komşuluğunda olduklarını bilecektir. Diğer ortak eleman 1011'de ise birinci mahkum birinci durum için 1-komşuluğunu bilecek, üçüncü mahkum ise ikinci durum için 1-komşuluğunu bilecek.
Şimdi kabaca bir strateji tanımlayalım. Bu aşamada bazı kısımlar hala çözülmemiş kalacak ama problemi başka bir probleme dönüştürmüş olacağız.
Mahkumlar $M$ adet birbirine uzaklıkları 3 (ya da mümkün değilse 2) olan dağılımlar kararlaştırsınlar. Bu dağılımları $Kod_{i}$ şeklinde gösterelim ($1 <= i <= M$). Tahmin zamanı geldiğinde mahkumlar o an gördükleri durumun bu kararlaştırılmış kodlara uzaklıklarını hesaplasın. Eğer bu uzaklıklar her kod için birden büyük olabiliyorsa o mahkum pas geçsin. Eğer bu uzaklık bir kod için en fazla 1 oluyorsa o zaman mahkum sonuç o kod olmayacak şekilde tahminde bulunsun. Bu şekilde o kodda tanımlanmış dağılımda hepsi yanlış cevap verecek fakat buna karşın o kodun 1-komşuluğundaki her dağılım doğru tahmin edilmiş olacak. Bu da toplam olasılığı çok daha fazla artıracaktır. $M$ adet kod dışındaki her dağılım doğru tahmin edildiğinde de olasılık $\frac {2^N - M}{2^N}$ olacaktır.
Bu strateji için çözülmesi gereken sorular:
- M = ?
- Kodlar nasıl seçilmeli?
- Kodlar arası uzaklık 2 olunca 1-komşuluğunda ortakkk dağılımlar olacak. Bu dağılımlarda birden fazla kişi tahminde bulunacak. Bu tahminler birbirleriyle uyumlu olacak mı?
- Bu stratejiden daha iyi bir strateji var mıdır?
Şimdi bu sorulara cevap aramaya çalışayım.
1. $N$ mahkumla oynanan oyunda $2^N$ değişik dağılım olacağından ve seçilecek her kod için 1-komşuluğunda $N$ dağılım olacağından $M \ge \frac {2^N} {N+1}$ olacaktır.
2. Kodlar seçilirken her ikili kombinasyon arasındaki Hamming uzaklığının 3 (en kötü ihtimalle 2) olmasına dikkat edilmelidir.
3. Evet. İki kod arasındaki uzaklık 2 ve ortak dağılımlar da iki koda eşit uzaklıkta. İki mahkum da tahminlerinde seçilmiş kodlardan uzaklaşacağına göre iki kodun orta noktasında (ortak dağılımda) buluşacaklardır.
4. Bunu bilmiyorum. Literatüre bakmak lazım. $k$ pozitif bir tamsayı olmak üzere $N=2^k - 1$ şartını sağlayan mahkum sayısı için daha iyi bir çözüm yok sanırım (Ebert's version). Bu durumda da kazanma olasılığı $\frac {2^k - 1}{2^k}$ oluyor.
Son olarak üç mahkum için $Kod_{1} = 000$ ve $Kod_{2} = 111$ tanımlarsak, $d(Kod_{1}, Kod_{2}) = 3$ olduğundan $M=2$ olacak şekilde bütün dağılımları sınıflandırabiliyoruz. Sınıfları aşağıdaki tabloda görebiliriz.
| $Kod_{1}$ (000) | $Kod_{2}$ (111) |
| 001 | 110 |
| 010 | 101 |
| 100 | 011 |
Şimdi de oyuncuların yukarıdaki stratejiye göre her dağılımda verecekleri cevapları tablo halinde görelim.
| Dağılım | 1. mahkum | 2. mahkum | 3. mahkum | Sonuç |
| 000 | 1 | 1 | 1 | Yanlış |
| 001 | 1 | Pas | Pas | Doğru |
| 010 | Pas | 1 | Pas | Doğru |
| 011 | 0 | Pas | Pas | Doğru |
| 100 | 1 | Pas | Pas | Doğru |
| 101 | Pas | 0 | Pas | Doğru |
| 110 | Pas | Pas | 0 | Doğru |
| 111 | 0 | 0 | 0 | Yanlış |
Dolayısı ile kazanma şansı $\frac{6}{8} = 0.75$. Yukarıda bulduğumuz formüle de bu sayıları ($M=2, N=3$) yerleştirirsek $\frac {2^N - M}{2^N} = \frac {2^3 - 2}{2^3} = \frac {6}{8} = 0.75$
Çözümde unuttuğum ve yapamadığım, dolayısıyla eksik kalan ve yanlış yerler vardır mutlaka. Bunları tamamlamak ve düzeltmek isteyenler kağıt kalem alıp çalışmaya başlayabilirler..
Hiç yorum yok:
Yorum Gönder