Kilitli kutu

Bilal, içinde çok değerli belgelerin olduğu bir kutuyu babasına göndermek istemektedir. Bu belgelerin düşmanlarının eline geçmemesi için kutuyu anahtarı sadece kendisinde olan bir kilitle kilitlemek ister. Bilal, kilitin anahtarını kilitlenmemiş bir kutu ile babasına iletmeye çalışması durumunda bunun düşmanların eline geçeceğini bilmektedir. Düşmanları kutuyu ele geçirse bile kiliti kıramayacağını varsayarsak Bilal ve babası nasıl bir yol izlemeli ki babası belgeleri alabilsin?

Not: Kutuya birden fazla kilit takabilecek kadar yer var.

Muz taşımacılığı (Çözüm)

Bu soru için sezgisel bir çözüm vereceğim ve bu çözümün en iyi sonucu verdiğini başka bir yazıya bırakacağım. 

Eğer deve 1000 adet muzu sırtlanıp bütün yolu geçmeye çalışırsa B şehrine geldiğinde hiç muz kalmamış olacaktır, çünkü 1000 km için 1000 adet muz yemesi gerekecek. Ayrıca A şehrinde kalan 2000 muzu almak için de geri dönemeyecek. 

Demek ki A şehrinden B şehrine doğrudan değil etaplar halinde gidilecek. Her etapta belli miktarda muz ara hedefe iletilecek. İlk etaplarda deve geri dönüp taşıyamadığı muzları geri alması gerekeceğinden bu mesafeler birden fazla sefer gidilecek ama son etapta devenin geri dönmesine gerek olmayacaktır. Yani deve son etabın başlangıç noktasında 1000 muz biriktirirse bir daha geri dönmeye gerek olmadan bu muzlar bir kerede hedefe taşınabilir. 

İlk etapta 3000 muzu taşımak için üç kere 1000 adet muzla yola çıkılacak ve iki defa da geri dönülecek. Yani ilk etabın mesafesine $x$ km dersek, deve bu mesafeyi beş kere gidecek ve bu sırada $5x$ adet muz yiyecek. İkinci etabın başlangıcında eğer 2000'den fazla muz birikmişse bu etapta ya yine beş sefer yapılacak ya da fazlalık muzlar burada bırakılmak şeklinde ziyan edilecek. Eğer 2000 muz biriktirilmişse ikinci etapta sadece üç sefer yapmak gerekecek, 1000 muz ileri, geri ve kalan 1000 muz ile tekrar ileri. 

İkinci etap başında 2000 muz kalması için ilk etabın 

$3000 - 5x = 2000 \implies x = \frac {1000}{5} = 200$ km olması lazım.

İkinci etapta üç sefer yapılacak ve aynı mantık kullanılacak. Yani son etap için 1000 muz kalacak şekilde mesafe seçeceğiz. Bu etabın mesafesine de $y$ dersek

$2000 - 3y = 1000 \implies y = \frac {1000}{3} = 333 \frac {1}{3}$ km

Deve kesirli muzlarla yürümediğinden tamsayılı bir çözüm kullanacağız ve sadece 333 km gideceğiz. Bu noktada son etaba başlamadan önce 1001 adet muz kalmış olacak. Deve sadece 1000 muz taşıyabildiğinden son etap için artan muzu bırakıp kalan mesafeyi, yani $1000 - (200 + 333) = 1000 - 533 = 467$ km'yi gidersek B şehrine $1000 - 467 = 533$ muz ulaştırabiliriz. Peki daha iyi bir sonuca ulaşabilir miyiz? Örneğin son etap başında artan bir muzu kurtarmanın yolu var mı? Sorunun soruluşuna dikkat edersek gerçekten de var. Deve yola her kilometreden önce muzu yiyor ve 1000 adet muz taşıyabiliyor. Bu durumda son etaptan önce 1001. muzu yiyerek kalan 1000 muzu bir kilometre daha ileri götürebiliriz. Böylece son etaba 533. km'de değil de 534. km'de başlayabiliriz ve bu da son etap mesafesi $1000 - 534 = 466$ km olacak demektir. Bu şekilde de B şehrine $1000 - 466 = 534$ muz ile ulaşabiliriz. 

Not: Eğer üç gidiş gelişli ara etap olmayan bir çözüm ararsak elde edeceğimiz sonuç beş gidiş gelişli bir etap ve tek gidişli bir ikinci etap çözümüne eşdeğer olacaktır. Bundan da

$3000 - 5x = 1000 \implies x = 400$ km ilk etap mesafesi bulunur. Yani kalan 1000 muz ile son 600 km gidilecektir ve geriye de sadece $1000 - 600 = 400$ muz kalacaktır. Bu da yukarıda bulduğumuz çözümden daha kötü bir cevaptır.

Muz taşımacılığı

A şehrinde bulunan 3000 adet muz bir deve ile B şehrine taşınacak. İki şehir arasında 1000 km mesafe var. Bu deve aynı anda en fazla 1000 tane muz taşıyabiliyor ve gideceği her kilometrenin başında bir adet muz yiyor. B şehrine ulaştırılabilecek maksimum muz sayısı kaçtır?

Tuzak odası (Çözüm)

Her hareketten sonra odanın kontrolsüz dönüşü odanın ve düğmelerin hangi durumda olduğunu bilmemizi engelliyor. Yine de kutsal kitapta yazdığı gibi paniğe kapılmayıp sistemi inceleyelim. 

Yapabileceğimiz hareketler üç tane:

1. Karşılıklı iki duvardaki düğmelere basmak ($T_{1}$)
2. Yanyana iki duvardaki düğmelere basmak ($T_{2}$)
3. Herhangi bir duvardaki tek düğmeye basmak ($T_{3}$)

Hiçbir düğmeye basmamak gibi bir imkanımız olsa da çözüm için bize bir faydası dokunmadığından bu ihtimali şimdiden eledim. Şimdi de odanın içinde bulunabileceği durumlara bakalım. Düğmelerin iki değişik konumunu A (Açık) ve K (Kapalı) şeklinde gösterelim.

1. Durum ($P_{1}$): Karşılıklı duvarlardaki düğmeler aynı ve yanyana duvarlardaki düğmeler farklı konumda.

	A
K		K
	A

2. Durum ($P_{2}$): Yanyana iki duvardaki düğmeler aynı ve diğer duvarlardaki düğmeler farklı konumda.

	A
A		K
	K

3. Durum ($P_{3}$): Üç duvardaki düğmeler aynı ve dördüncü duvardaki düğme farklı konumda.

	A
A		K
	A

Bu durumların aslında benzer durumları simgeleyen isimler olduğunu belirteyim. Yani A'lar yerine K ve K'lar yerine A olan durumlar da aynı durumdur. Oda düğmelerin konumu aynı olacak şekilde dönmüş olsa da aynı durumdur.

Şimdi yukarıda tanımladığımız üç değişik hareketin bu durumları hangi durumlara dönüştürdüğüne bakalım. Bunu göstermek için kullanacağımız notasyon da $T_{n}(P_{k}) = P_{l}$ olacak ve n.hareketin k. durumu l. duruma dönüştürdüğünü gösterecek.

$T_{1}(P_{1}) =$ Çıkış  (Bu hareket sonunda bütün düğmeler aynı konuma geleceğinden odadan çıkılacaktır.)

$T_{1}(P_{2}) = P_{2}$

$T_{1}(P_{3}) = P_{3}$

$T_{2}(P_{1}) = P_{2}$

$T_{2}(P_{2}) = P_{1}$ (Aslında şansımız yaver giderse ve aynı konumda olan iki düğmeye basarsak odadan çıkabiliriz de ama çözümde en kötü ihtimali varsayacağız.)

$T_{2}(P_{3}) = P_{3}$

$T_{3}(P_{1}) = P_{3}$

$T_{3}(P_{2}) = P_{3}$

$T_{3}(P_{3}) = P_{1}$ veya $P_{2}$ (Burada da şansımız yaver giderse odadan çıkabiliriz ama yine en kötü ihtimalle yola devam edeceğiz.)

Demek ki odadan kesin olarak çıkabilmek için $P_{1}$ durumuna ulaşmamız ve bu duruma ulaştığımızı bilmemiz lazım. $P_{1}$ durumuna da ya $P_{2}$ durumundan ya da $P_{3}$ durumundan ulaşabiliyoruz. $P_{2}$ durumuna da ya $P_{1}$ durumundan ya da $P_{3}$ durumundan erişebiliyoruz. Bir başka önemli gözlem de $T_{1}$ dönüşümünün bizi ya odadan çıkardığı ya da durumu değiştirmediği. Bir de $T_{2}$ dönüşümünün $P_{3}$ durumunu değiştirmediğini dikkate alırsak şöyle bir plan yapabiliriz.

Önce hangi durumda olduğumuzu anlamaya çalışalım. Bunu da eleme usulüyle yapabiliriz. Birinci durumda olup olmadığımızı birinci hareketle anlayabiliriz. Birinci durumdaysak eğer odadan çıkarız, değilsek durum değişmez. Çıkamadıysak ikinci durumda olduğumuzu varsayarız ve iki numaralı hareketi yaparız. Eğer ikinci durumda idiysek bu bizi birinci duruma götürür ve şimdi yapacağımız bir numaralı hareket bizi odadan çıkarır. Çıkarmadıysa ikinci durumda değil, üçüncü durumda olduğumuzu anlarız ve üç numaralı hareket ile birinci ya da ikinci duruma geçiş yaparız. Sonra yine önce birinci durumu varsayarak bir numaralı hareketi bu da işe yaramazsa deminki gibi önce ikinci durumdan birinci duruma geçmek için iki numaralı hareketi ve ardından tekrar bir numaralı hareketi yaparak odadan çıkarız. Bu karışık yöntemi bir de tablolarla daha anlaşılır bir şekilde görelim.

Adım	Hareket	Durum (Başlangıç $P_{1}$)	Açıklamalar
1	$T_{1}$	Çıkış	Şansımız varsa hemen çıkabiliriz

Adım	Hareket	Durum (Başlangıç $P_{2}$)	Açıklamalar
1	$T_{1}$	$P_{2}$	Çıkamadığımıza göre birinci durumda değildik
2	$T_{2}$	$P_{1}$
3	$T_{1}$	Çıkış	Demek iki numaralı durumda başlamışız

Adım	Hareket	Durum (Başlangıç $P_{3}$)	Açıklamalar
1	$T_{1}$	$P_{3}$	Çıkamadığımıza göre birinci durumda değildik
2	$T_{2}$	$P_{3}$
3	$T_{1}$	$P_{3}$	Hala çıkamadığımıza göre üç numaralı durumla başladık ve şu an da üç numaralı durumdayız
4	$T_{3}$	$P_{1}$	Bu adımda iki devam yolu var ve önce bir numaralı durumun olduğunu kabul edelim.
5	$T_{1}$	Çıkış	Demek şansa birinci duruma geçmişiz

Adım	Hareket	Durum (Başlangıç $P_{3}$)	Açıklamalar
1	$T_{1}$	$P_{3}$	Çıkamadığımıza göre birinci durumda değildik
2	$T_{2}$	$P_{3}$
3	$T_{1}$	$P_{3}$	Hala çıkamadığımıza göre üç numaralı durumla başladık ve şu anda da üç numaralı durumdayız
4	$T_{3}$	$P_{2}$	Bu adımda iki devam yolu var ve bu sefer iki numaralı durumun olduğunu kabul edelim.
5	$T_{1}$	$P_{2}$	Demek ikinci duruma geçmişiz
6	$T_{2}$	$P_{1}$	O zaman birinci duruma nasıl geçeceğimizi biliyoruz
7	$T_{1}$	Çıkış	Yaşasın özgürlük

Böylece Şinasi hoca yetişemeden odadan çıkmayı başardık. Dikkat edilirse ilk üç tablodaki adımlar son tablodaki adımların başlangıç kısımları. Demek ki son tablodaki yöntem ile genel çıkış yolunu bulmuş oluyoruz ve ispatlamamış olsam da 7 adımdan daha iyi bir çözüm bulamadım.

"Mischief managed."

Tuzak odası

Bilindiği gibi Hogwarts'ta bir sürü koridor öğrenciler için yasaktır ama bu yasakları iplemeyen birileri her zaman vardır. Yine böyle günlerden birinde Hayri Pıtır kendini telefon kulübesi büyüklüğünde bir odanın içinde bulur fakat kapı filan yoktur, sadece birbirinin aynısı dört duvar. Tam çaresizliğe kapılmak üzereyken dört duvarın da ortasında birer delik belirir ve oda konuşmaya başlar:

"Elini sokarsan deliklerin içinde birer düğme bulacaksın ama bu düğmeler basılı mı değil mi anlayamayacaksın. Aynı anda istediğin iki deliğe ellerini sokabilirsin ve düğmelerin birine ya da ikisine de bir kere basabilirsin ama istersen hiçbirine basmadan ellerini deliklerden çıkarabilirsin. Ellerini çıkardıktan sonra eğer bütün düğmeler aynı konuma (hepsi basılı ya da hiçbiri basılı değil) gelirse kendini buraya geldiğin koridorda bulacaksın. Eğer düğmeler aynı konumda değilse, oda kendi etrafında öyle bir dönmeye başlayacak ki durduğunda hangi düğmelere bastığını bilemeyeceksin. Bu arada Şinasi hocaya burada bir öğrenci olduğu haberini verdim, acele etmezsen gelip seni burada yakalayabilir. Acele et!"

Hayri odadan nasıl çıktı? Odadan çıkmak için en fazla kaç denemeye ihtiyaç vardır?

Ziyafet (Çözüm)

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.

Ziyafet

Komşu krallardan biri bir ay sonrası için büyük bir ziyafet vermeye karar vermiş. Bu ziyafet için 1000 şişe şarap siparişi vermiş. Bu ziyafeti engellemek isteyen düşmanları da bir ajan kiralamış ve bu ajan da şişelere zehir koymak için kralın mahzenine girmiş. Tam işine başladığından ise kralın korumaları tarafından yakalanmış ve kralın huzuruna getirilmiş. Tüm sorgulamalara rağmen hangi şişeleri zehirlediği öğrenilememiş. Bunun üzerine kral ajanın idam edilmesine karar vermiş. Tam idam edilirken ajan sadece bir şişeye zehir koyabildiğini ve zehirin etkisini çok yavaş gösterdiğini söylemiş, yani şimdi içen biri ancak ziyafetten bir gün önce ölürmüş. Bütün hazırlıkları kendi elleriyle yapmış olduğu için kral ziyafeti erteletmek yerine zehirli şişeyi bulmayı planlamış. Bu iş içinde zindanlardaki idam mahkumlarını kullanmayı düşünmüş. Zehirli şişeyi zamanında bulabilmek için denemelerde en az kaç mahkum kullanılmalıdır ve nasıl bir yöntemle zehirli şişe kesin olarak bulunabilir? Önemli olan kaç mahkumun ölüp ölmeyeceği değil, yoksa 1000 tane mahkumun her biri bir şişeyi denerdi.