Üç Şapka Problemi

11392876_10153957892304488_8019999625728746946_n

Aşağıdaki yazı Brian Benson ve Yang Wang tarafından yazılan “The Three Hat Problem” başlıklı makalenin Türkçe’ye çevrilmiş özetidir. Makalenin orjinali

http://arxiv.org/abs/0710.2685

 adresinden bulunabilir.

Kanıtları okumadan önce soruları öncelikle kendi başınıza çözmeye çalışmanızı tavsiye ederim. 

 

Üç oyuncunun her birine birer şapka takılır. Her bir şapkanın üzerinde pozitif bir tam sayı yazılıdır. Hiç bir oyuncu kendi şapkasını göremez fakat diğerlerininkini görebilir. Şapkaların üzerindeki sayılardan birinin diğer ikisinin toplamı olduğu oyuncular tarafından biliniyordur. Sırayla her bir oyuncu kendi şapkasını bulmaya çalışır. Oyuncularn şapkalarında yazan sayıları yanlış bilme hakları yoktur. Her bir oyuncu kesin emin olmadıkça pas deme hakkına sahiptir. Her bir oyuncu ilk haklarında pas derse sıralama tekrar başa döner ve ilk tahmin yapan oyuncu tekrar tahmin yapar. Oyun, oyunculardan birinin şapkasını doğru tahmin etmesiyle sona erer. Bu senaryoya uygun popüler örneklerden biri aşağıdaki gibidir:


A Oyuncusu: Pas

B Oyuncusu: Pas

C Oyuncusu: Pas

A Oyuncusu: Benim Saym 50

Diğer sayılar kaçtır?

 


Ayrıca bu senaryonun daha karmaşık bir versiyonu da oldukça ilginçtir:

A Oyuncusu: Pas

B Oyuncusu: Pas

C Oyuncusu: Pas

A Oyuncusu: Pas

B Oyuncusu: Pas

C Oyuncusu: Pas

A Oyuncusu: Pas

B Oyuncusu: Pas

C Oyuncusu: Benim saym 60.

Diğer sayılar kaçtır?

Üç şapka probleminin en çok kullanılan versiyonu sayıların a,b,halinde
olanıdır. Bu durumda iki soru karşımıza çıkar:

(a) Oyuncular sayılarını bulabilecekler mi?
(b) Eğer bulabilirlerse bunu nasıl yapacaklar?

Bildiğimiz kadarıyla yukarıda anlatılan iki bulmaca MIT Tecnology Review
dergisinde Donald Aucamp tarafından sorulmuştur. 1. bulmacanın cevabı: B
oyuncusu: 20 ve C Oyuncusu: 30 dur. Cevabın neden bu iki sayı olduğunu görmek için biraz gözlem yapmak zorundayız. İlk turda A oyuncusu kendi şapkasının 50 veya 10 olduğunu anlar fakat doğru cevabın hangisi olduğunu bilemez. Aynı şekilde B ve C oyuncuları da kendi şapkalarını bilemezler. Fakat ikinci turda A Oyuncusu şöyle düşünür: Eğer benim şapkamda 10 yazıyorsa o zaman C oyuncusu kendi sayısının 10 veya 30 olduğunu tahmin edecektir. Eğer C oyuncusunun da şapkasında 10 yazsaydı o zaman B oyuncusu kendi şapkasında 20 yazdığını rahatlıkla anlayabilirdi. Fakat anlayamadı. O zaman C oyuncusu kendi şapkasında 30 yazdığını hemen anlardı. Fakat anlayamadı. Demek ki benim şapkamda 50 yazıyor.

Bu tür bir mantıkla diğer çözümleri de bulabiliriz. Birinci bulmaca için sadece tek bir çözüm var: [50, 20, 30]. Özel bir konuşmamızda Aucamp bana ikinci bulmacanın çözümünü kimsenin kendisine göndermediğini söylemişti. Birazdan anlatacağımız çözüm yöntemine göre ikinci bulmacanın tam sekiz çözümü var:

[253560][352560][421860][184260][105060],

[501060][441660][16 ,4460]

Şimdi üç şapka problemi için bir strateji bulmaya çalışacağız. Her zaman oyuncuların kazandığı stratejiye geçerli strateji diyeceğiz. Bir başka deyişle oyuncular hiç bir turda tahmin yapmak zorunda kalmayacak. Oyuncuların en az turda kazanmasını sağlayan geçerli stratejiye optimal strateji diyeceğiz

Tanımlardan görüleceği üzere her optimal strateji geçerli stratejidir fakat her geçerli strateji optimal değildir. Teoride optimal stratejinin olmaması da olasıdır. Yani bir başka deyişle bir strateji bazı düzenlemelere göre en iyi strateji olabilir fakat bütün düzenelemeler için en iyi strateji olmayabilir. Üç şapka problemi için optimal strateji vardır. Birazdan optimal stratejinin ne olduğunu ve neden optimal olduğunu göstereceğiz. Stratejimiz pozitif tam sayı girdileri olan vektör zincirlerini indirgeyerek gitmek olacak. Bu yazı b oyunca sıralamanın A, B, C şeklinde gittiğini varsayacağız. Ayrıca bu sıralama oyun bitene kadar böyle devam edecek. A, B, C oyuncularının taktığı şapkaların üzerlerinde yazn sayılar a, b, c olsun. Biz bu sayıları [a, b, c ] vektörü şeklinde göstereceğiz. Bu vektöre üç şapka düzenlemesi ya da kısaca düzenleme diyeceğiz.

H kümesi a, b, c nin tam sayı olduğu ve bunların en büyüğünün diğer ikisinin toplamı olduğu bütün  s =[a, b, c ] üçlülerinin kümesi olsun. H kümesi üç şapka probleminin olası bütün düzenlemelerini temsil eder.

σ H → H fonksiyonunu şöyle tanımlayacağız: s = [a, b, c  H için eğer iki girdi aynı ise σ (s ) = s olsun. Eğer bütün girdiler farklı ise σ en büyük girdiyi diğer iki girdinin farkıyla değiştirsin. Mesela bu tanıma göre σ ([3, 10, 7]) = [3, 4, 7] ve σ([3, 3, 6]) = [3, 3, 6] çıkar. H de girdilerinin ikisi aynı olan ya da denk olarak σ(s) = s olan elemanlara taban düzenleme diyeceğiz. Taban düzenlemelerde diğer iki oyuncunun şapkalarının sayısının aynı olduğunu gören oyuncunun kolaylıkla kendi şapkasında yazan sayıyı bilebileceği çok açık bir şekilde anlaşılıyor. Ayrıca ek olarak, oyuncu kendi stratejisine uymak adına kendi şapkasındaki sayıyı bilse bile hemen söylemeyebilir.

Üç şapka problemi için stratejimiz her bir oyuncu için bir düzeneleme zinciri
kurmayı içeriyor. Her s H için σn(s)  düzenlemesini bir taban düzeneleme
yapan en küçük n ≥ 0 için

s, σ(s), …, σ n(s)

dizisine bir düzenleme zinciri denir. Mesela s = [3, 10, 7] için düzenleme zinciri:

[3, 10, 7], [3, 4, 7], [3, 4, 1], [3, 2, 1], [1, 2, 1]

olur. Düzenleme zincirinin terimlerini en sondan en başa doğru tekrar dizdiğimizde oluşan yeni zincire s nin düzenleme zinciri denir. Mesela yukarıdaki s = [3, 10, 7] örneğine göre [3, 10, 7] nin düzenleme zinciri:

[1, 2, 1], [3, 2, 1], [3, 4, 1], [3, 4, 7], [3, 10, 7]

olur. Verilmiş bir düzenlemede eğer bir oyuncunun şapkasının üzerinde yazan sayı diğer iki oyuncunun şapkasının üzerinde yazan sayıların toplamına eşitse o oyuncuya işaretlenmiş oyuncu diyeceğiz. Örneğin  [3, 10, 7] düzenlemesinde B oyuncusu işaretlenmiş oyuncudur.

s = [a,b,c ] düzenlemesi için sA = [b+c,b,c], sB = [a,a+c,c], sC = [a,b,a+b]
olsun. sA,sB,sC sırasıyla A,B,C oyuncuları için çalışan düzenlemelerdir. Her
bir oyuncu kendilerine denk gelen çalışan düzenlemlerinin düzenleme zincirini
yazar. Her bir zincirin sadece en son teriminin farklı olması çok önemlidir. İki
küçük sayıya sahip oyuncuların düzenleme zincirinde fazladan bir düzenleme
daha vardır.

Oyun başladığında oyuncular kendi düzenleme zincirlerindeki ilk düzenlemeye bakarlar ve aşağıdaki yöntemi izlerler:

Her bir turda sırası gelen oyuncu kendi düzenleme zincirindeki sırası gelen
düzenlemeye bakar. Eğer bir oyuncunun zincirinde tek bir düzenleme kalmışsa o oyuncu kendi sayısının diğer iki oyuncunun toplamı olduğunu anlar ve kendi sayısını söyler, oyunu bitirir. Eğer zincirde birden fazla düzenleme varsa pas der. Daha sonra bütün oyuncular kendi düzenlemelerini incelerler. İşaretlenmiş oyuncunun sırası geldiğinde ve pas dediğinde ve kendi düzenlemesini elediğinde diğer oyuncularda aynı düzenlemeyi kendi listelerinden
silerler. Oyun bir oyuncunun kendi sayısını söylemesiyle sona erer. Aşağıdaki
oyun, stratejimizi anlamak için ideal örneklerden biridir:

Oyun 1.  A,B,C oyuncuları için sayılar sırasıyla 60, 36, 24 olsun. Bu durumda çalışan düzenlemeler

sA = [60, 36, 24], sB = [60, 84, 24], sC = [60, 36, 96]

olur. Düzeneleme zincirleri ise:

A Oyuncusu: [12, 12, 24], [12, 36, 24], [60, 36, 24]
B Oyuncusu: [12, 12, 24], [12, 36, 24], [60, 36, 24], [60, 84, 24]
C Oyuncusu: [12, 12, 24], [12, 36, 24], [60, 36, 24], [60, 36, 96]

Oynunun başlangıcında her bir oyuncunun önündeki ilk düzenleme [12, 12, 24]
olmaktadır. A,B,C Oyuncuları ilk turda pas demek zorunda kalacaktır. Fakat
C oyuncusu ilk tura göre işaretlenmiş oyuncu olduğundan ve pas dediğinden
bütün oyuncular [12, 12, 24] düzenlemesini sileceklerdir. Yeni düzenlemeler şu
şekilde olacaktır:

A Oyuncusu: [12, 36, 24], [60, 36, 24]
B Oyuncusu: [12, 36, 24], [60, 36, 24], [60, 84, 24]
C Oyuncusu: [12, 36, 24], [60, 36, 24], [60, 36, 96]

Bu durumda bütün oyuncular için sıradaki düzenleme [12, 36, 24] olmuştur. A
oyuncusu pas diyecektir. B oyuncusu pas diyecektir.Fakat B oyuncusu işaretli
oyuncu olduğu için ve pas dediği için bütün oyuncular [12, 36, 24] düzenlemesini silecektir. Yeni düzenlemeler şu şekilde olacaktır:

A Oyuncusu: [60, 36, 24]
B Oyuncusu: [60, 36, 24], [60, 84, 24]
C Oyuncusu: [60, 36, 24], [60, 36, 96]

Oyuna göre sıra C oyuncusundadır ve pas diyecektir. Sıra tekrar A oyuncusuna geldiğinde A oyuncusu elinde tek bir düzenleme kaldığından kendi sayısının diğer iki sayının toplamı olan 60 olduğunu anlayacaktır. Oyuncular oyunu kazanır.

Şimdi yukarıda anlattığımız stratejinin neden optimal strateji olduğunu kanıtlayacağız. Kanıta başlamadan önce ufak bir gözlem yapmamız gerekiyor.

ebob(a, b) = ebob(b, c) = ebob(a, c) olduğundan oyuncular gördükleri
iki sayıyı her zaman o sayıların en büyük ortak bölenlerine bölebilirler ve çıkan sonuçlarla hesaplarını yapabilirler. Bu gözlem sayesinde oyundaki üç sayının birbirleriyle aralarında asal olduklarını varsayabiliriz. Sayıların aralarında asal olduğu durumlarda sadece üç tane taban düzenlemesi vardır:

[1, 1, 2], [2, 1, 1], [1, 2, 1]

Sav 1. Üç şapka problemi için oyuncuların kullandığı geçerli strateji hangisi
olursa olsun şapkasındaki sayıyı bilen ilk oyuncu şapkasında diğer iki sayının
toplamı yazan oyuncudur.

Kanıt. Üç şapka oyununda ilk turda bir oyuncunun şapkasında yazan sayıyı
bildiğini varsayalım. Böyle bir durumun olabilmesi için her üç oyuncunun da
sadece taban düzenlemesine sahip olması gerekir. Başka hiç bir şekilde oyuncular ilk turda şapkalarında yazan sayıyı bilemezler. Mesela [1, 2, 1] taban düzenlemesinde A oyuncusu sayısını bilemez fakat B oyuncusu kendi şapkasında 2 yazdığını rahatlıkla bilebilir. Şimdi savımızda yazan önermemizin yanlış olduğunu varsayalım. Yani a, b, c düzenlemesine sahip bir oyunda şapkasını bilen ilk oyuncunun n > 0 turunda
iki sayının toplamına sahip olmayan oyunculardan biri olduğunu varsayalım. Genelliği kaybetmeden C oyuncusunun şapkasında diğer iki oyuncunun şapkalarında yazan sayıların toplamı yazmadığını varsayabiliriz. O zaman c =| ab | olur. Fakat eğer bu doğruysa C oyuncusu kendi sayısının c = a+ b şeklinde olmadığını n. turda anlardı. Bu, eğer C oyuncusunun şapkasında yazan sayının c = a + b toplamına eşit olsaydı oyunun daha k < n turunda başka bir oyuncu tarafından bitirilmiş olacağına denktir. Bu sebepten oyuncuların kullandığı strateji sayesinde [a, b, a + b] düzenlemesindeki oyunu C oyuncusu dışnda bir başka oyuncu k < n turda bitirir. Bu oyuncunun sahip olduğu sayı diğer iki oyuncunun toplamı değildir.

Yukarıda anlattığımız bu argümanı tekrar kullanabiliriz. Oyuncular bu stratejiyi kullanırlarsa taban düzenlemesiz olan oyun tek bir turda şapkasındaki sayı diğer iki sayının toplamı olmayan oyuncu tarafından bitirilir sonucuna ulaşırız. Bu da bir çelişkidir.

Teorem 1. Düzenleme zinciri stratejisi üç şapka problemi için optimal stratejidir.

Kanıt. [a,b,c] düzenlemesine sahip olan üç şapka probleminde, düzenleme
zinciri stratejisini kullandığımızda, oyunu bitirebilmek için gereken tur miktarını r([a,b,c]) ile gösterelim. Bu oyunu bir başka strateji kullanarak daha az turda bitiremeyeceğimizi kanıtlayacağız.

Oyuncuların bir başka strateji kullandıklarını ve sözkonusu strateji için gereken tur miktarının f([a,b,c]) olduğunu varsayalım. Hedefimiz

f([a,b,c]) r([a,b,c])

olduğunu göstermek olacak. Genelliği kaybetmeden a,b,c sayılarının aralarında asal olduklarını kabul edebiliriz. Düzenleme zinciri stratejisinin optimalliğini max(a,b,c) üzerinde tümevarım yaparak kanıtlayacağız.

max(a,b,c) = 2 için taban durumu geçerlidir. Bu durumda düzeneleme zincirinin optimal olduğu çok açıktır. Yani f([a,b,c]) ≥ r([a,b,c]) olur.
max(a,b,c) < M durumunda f([a,b,c]) ≥ r([a,b,c]) olduğunu varsayalım. Şimdi max(a,b,c) = M olduğunda  f([a,b,c]) ≥ r([a,b,c]) olduğunu kanıtlayacağız.

a = b + c ve b > c yani a = M durumunu inceleyeceğiz. Diğer durumlar için benzer yöntem yapılabileceğinden diğer durumların kanıtını okura bırakıyoruz. Sav 1 e göre A oyuncusu strateji ne olursa olsun kendi şapkasını bilen ilk oyuncu olacaktır. Bunu aklımızda tutarak A oyuncusu şapkasında yazan sayıyı söylemeden önce neler olduğunu inceleyeceğiz. Eğer duruma A oyuncusunun bakış açısıyla bakarsak A oyuncusunun şapkasında yazn sayı a = b + c ya da a = b c olacaktır. Hangi stratejiyi uygularsa uygulasın a = b c olma ihtimalini eleyemeden kendi şapkasında yazan sayının diğer iki sayının toplamı olduğunu anlayamayacaktır. Herhangi bir stratejide şapkasındaki sayıyı ilk bilen oyuncu şapkasında diğer iki şapkada yazan sayıların toplamı yazan oyuncu olduğundan A oyuncuusu eğer kendi şapkasında yazan sayı a = bc olursa n. turda şapkasını ilk açıklayan oyuncunun B oyuncusu olduğunu bilecektir ve n = f([b c,b,c]) olacaktır. Fakat n. turda B
oyuncusu pas demiştir. B oyuncusundan sonra C oyuncusu da pas demiştir. Çünkü her iki oyuncunun şapkasında diğer iki şapkanın üstünde yazanların toplamı yazmıyordur. Buradan

f([a,b,c]) 2 + f([b c,b,c])

sonucuna ulaşıyoruz. Yukarıdaki eşitsizliği eşitlük olarak alamıyoruz çünkü stratejimizin henüz optimal olup olmadığını bilmiyoruz. Tümevarım varsayımına göre

max (b c, b, c ) = b < a = M olduğundan

f ([b c, b, c ]) r ([b c, b, c ]) ve f ([a, b, c ]) 2 + r ([b c, b, c ])

olur. r ([a, b, c ]) = 2 + r ([b c, b, c ]) olduğunu göstereceğiz. Bu eşitlik çok rahatlıkla      [b c, b, c ] ve [a, b, c ] düzenlemelerinin zincirlerine bakarak görülebilir. Her üç oyuncu için düzenleme zincirlerine göre bir önceki oyuncunun zinciri bir düzenleme farkla diğer oyuncunun zincirinin bir alt zinciridir. r ([b c, b, c ]). turda B oyuncusu işaretlidir ve pas diyecektir. Yani bütün oyuncular zincirlerinden [b c, b, c ] durumunu
sileceklerdir. Bu durumda ise A oyuncusunun zincirinde tek bir düzenleme kalacaktır. O düzenleme ise [a, b, c ] dir. C oyuncusu pas dedikten sonra A oyuncusu zincir stratejisini kullanarak kendi şapkasında yazan sayının diğer iki şapkanın toplamı olduğunu söyleyebilecektrir. Yani

f ([a, b, c ]) 2 + r ([b c, b, c ]) = r ([a, b, c ])

çıkar. Bu da Zincir stratejisinin optimalliğini gösterir.

Okur üç şapka problemi için optimal olmayan bir strateji olup olmadığını
merak ediyor olabilir. Bu sorunun cevab evettir. Bu stratjilerden bir tanesi
ise şöyledir:

Her bir oyuncu gördükleri sayılaran en büyük olanını akıllarında tutarlar.
A, B, C oyuncularının gördükleri en büyük sayılara nA, nB, ndiyelim. Başka bir oyuncu kendi sayısın söylemediği sürece A oyuncusu nA. tura kadar kendi şapkasnda yazan numarayı söylemek için pas der. nA turda ise kendi sayısının diğer iki sayının toplamı olduğunu söyler. Ayn yöntemi B ve C oyuncuları da uygular. Bu strateji açk bir şekilde geçerli bir stratejidir ama optimal değildir.

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.


*