Her zamanki gibi çözüme önce basit gözlemler yaparak başlayalım. Eğer bin şişe değil de sadece bir şişe olsaydı mesela. O zaman çözüm çok kolay. Bir şişenin zehirli olduğunu bildiğimize göre elimizdeki şişe zehirli olmalıdır. Peki iki şişemiz varsa? İki şişe varsa bir mahkum alıyoruz ve bu mahkum şişelerden birini deniyor. Eğer ölürse bu şişe zehirlidir, ölmezse diğer şişe zehirlidir. Üç şişe varsa iş biraz daha zor. Çünkü bir mahkuma bir şişe verirsek ve ölmezse iki şişe arasında seçim yapmak zorunda kalacağız. İki şişe verirsek de bu sefer ölürse iki şişe arasında seçim gerekecek ki, yüzde elli ihtimalle sonuçtan kral hiç de hoşnut kalmayacaktır. Demek ki ölümler sonucunda (ya da hiç ölüm olmazsa) karşımıza çıkan şişe gruplarında tek bir şişe olmalı, yoksa karar veremiyoruz. O zaman iki mahkum alalım. Birine birinci şişeyi ve diğerine de ikinci şişeyi verelim. Birinci şişeyi içen mahkum ölürse birinci şişe, ikinciyi içen ölürse ikinci ve her ikisi de canlı kalırsa da üçüncü şişe zehirlidir.
Dört şişe için çözüme bakarsak yeni bir durumla karşılaşıyoruz. İki mahkuma da birer şişe verirsek denenmemiş iki şişe kalacağından bu çözümü rafa kaldırıyoruz. Demek ki mahkumlardan en az biri en az iki şişe denemeli. Ayrıca iki mahkumun da denediği şişelerde ortak şişe yoksa iki şişe deneyen mahkumun ölmesi durumunda yine çözüme ulaşamıyoruz. Ümitsizliğe kapılmaya gerek yok ama. Birinci mahkuma birinci ve ikinci şişeleri verelim, ikinci mahkuma da ikinci ve üçüncü şişeleri. Sonuçları da aşağıdaki tabloya yerleştirelim.
| Ölen mahkum | Zehirli şişe |
| 1 | 1 |
| 2 | 3 |
| 1 ve 2 | 2 |
| hiç kimse | 4 |
Bu tabloyu başka bir şekilde de yorumlayabiliriz. Kümelerle. Birinci mahkumun içtiği şişeler kümesi ve ikinci mahkumun içtiği şişeler kümesi var. Tabii iki kümenin kesişim kümesi de var (elemanı ikinci şişe olan küme). Bir de tüm şişeler kümesi. Bu kümenin diğer tüm kümelerin birleşiminden farkının da tek elemanı var, o da dördüncü şişe.
Soruya kümeler açısından yaklaştığımızda yapmamız gereken tek şey kaç mahkum kullanırsak kullanalım bütün kesişim kümelerine en fazla bir eleman düşmesini sağlamak. Ayrıca mahkumların denediği şişeler kümesinin dışında kalan kümenin de en fazla bir elemanı olmalı.
Şimdi $N$ tane mahkum için yukarıda bahsedilen birbirinden ayrık kümelerin adedini bulalım.
Bütün şişelerin kümesinin mahkumların denediği bütün şişelerin kümesinden farkı = 1 = $\binom {N}{0}$
Mahkumların tek başlarına denedikleri şişeler kümeleri = $\binom {N}{1}$
Mahkumların ikişer ikişer ortak denedikleri şişerler kümeleri = $\binom {N}{2}$
...
Mahkumların hepsinin ortak denediği şişeler kümesi = $\binom {N}{N}$
Toplama $T$ dersek
$T = \sum_{i=0}^{N}\binom{N}{i}$
Binom teoreminden biliyoruz ki
$(x+y)^n = \sum_{i=0}^{N}\binom{N}{i}x^{n-k}y^k$
$x=1, y=1$ alırsak
$2^N = \sum_{i=0}^{N}\binom{N}{i} = T$
Amacımız her ayrık kümeye sadece bir eleman yerleştirmek olduğundan çözüm yöntemi de basit. $N$ mahkum için $2^N$ kümeyi listeleriz ve sırayla her bir kümenin mahkumlarına sıradaki şişeyi denetiriz. Sonra da ölen mahkumlaraın kesişim kümesinde hangi şişe varsa o şişe zehirlidir sonucuna varırız. Eğer hiçbiri ölmemişse o zaman hiçbir mahkumun denemediği şişe zehirlidir.
Güvercin yuvası ilkesine göre sorunun çözümü için $2^N \ge 1000$ eşitsizliğini sağlamamız lazım. Bu da $N \ge 10 (2^10 = 1024)$ demektir, yani 10 mahkum kullanarak zehirli şişeyi bulabiliriz.
Bütün şişelerin kümesinin mahkumların denediği bütün şişelerin kümesinden farkı = 1 = $\binom {N}{0}$
Mahkumların tek başlarına denedikleri şişeler kümeleri = $\binom {N}{1}$
Mahkumların ikişer ikişer ortak denedikleri şişerler kümeleri = $\binom {N}{2}$
...
Mahkumların hepsinin ortak denediği şişeler kümesi = $\binom {N}{N}$
Toplama $T$ dersek
$T = \sum_{i=0}^{N}\binom{N}{i}$
Binom teoreminden biliyoruz ki
$(x+y)^n = \sum_{i=0}^{N}\binom{N}{i}x^{n-k}y^k$
$x=1, y=1$ alırsak
$2^N = \sum_{i=0}^{N}\binom{N}{i} = T$
Amacımız her ayrık kümeye sadece bir eleman yerleştirmek olduğundan çözüm yöntemi de basit. $N$ mahkum için $2^N$ kümeyi listeleriz ve sırayla her bir kümenin mahkumlarına sıradaki şişeyi denetiriz. Sonra da ölen mahkumlaraın kesişim kümesinde hangi şişe varsa o şişe zehirlidir sonucuna varırız. Eğer hiçbiri ölmemişse o zaman hiçbir mahkumun denemediği şişe zehirlidir.
Güvercin yuvası ilkesine göre sorunun çözümü için $2^N \ge 1000$ eşitsizliğini sağlamamız lazım. Bu da $N \ge 10 (2^10 = 1024)$ demektir, yani 10 mahkum kullanarak zehirli şişeyi bulabiliriz.
Hiç yorum yok:
Yorum Gönder