Two Egg Problem - İki Yumurta Problemi

Önce problemin tanımını yapalım:

n katlı bir binadayız , iki adet yumurtamız var . Yumurtalar x. katın altındaki katlardan atınca kırılmıyor, x ve üzeri katlardan atılınca kırılıyor. Kırılmadığı sürece yumurtayı tekrar tekrar kullanabilirsiniz. Minimum kaç atışta yumurtanın kırılmaya başladığı katı bulursunuz?

Akla gelen ilk çözümler:

• 1. kattan başlarız ilk nerede kırıldıysa x odur.

 En iyi Durum: İlk katta kırıldıysa tek atışla bulduk.
 En kötü Durum: En üst katta kırılıyorsa n -1 atışta bulduk.

•  İlk yumurtayı orta kattan atarız.

kırıldıysa : 2. yumurtayı ilk kattan atmaya başlarız, taki kırılana kadar
kırılmadıysa : n/2 ile n. katlar arasında kırılıyor. Bu katların ortasından atış yapıyoruz( 3* n / 4). Böyle devam ediyoruz.(Binary search mantığı).
En kötü Durum: yumurtanın n/2-1 katta kırılması. (Benim de aklıma gelen çözüm bu olmuştu)

Gelelim ideal çözüme bunu direk bir örnekle açıklayacağım. Diyelim ki binamız 100 katlı iddiamız 14 atışta ben nerede kırıldığını bulurum. Nasıl mı?

14. kattan atalım. İlk atış hakkımı kullandım. Kaldı 13.

Kırıldı: 1 den 13 e kadar tek tek deniyoruz.

Kırılmadı: İlk 14 katta kırılmıyor. 1 atış yaptık , 13 atış hakkımız kaldı . 14 + 13 = 27 .

27. kattan atalım. Kaldı 12.

Kırıldı: 15 ten 26. kata tek tek deniyoruz.

Kırılmadı: İlk 27 katta kırılmıyor. 2 atış yaptık , 12 hakkımız kaldı. 27+12=39.(14+13+12)

39. kattan atalım: Kaldı 11

Kırıldı: 28 den 38. kata tek tek deniyoruz.

Kırılmadı: İlk 39 katta kırılmıyor. 39+11=50.(14+13+12+11)

.
.
.

(14+13+12+11+...+4 = 99)39. kattan atalım: Kaldı 3
Kırıldı : (14+13+12+11+...+5+1 = 96)96. kattan 98. kata tek tek deniyoruz.
Kırılmadı: İlk 99 katta kırılmıyor. 100. kattan atıyoruz. Kırılacaktır.

n katlı bina için q atış garantiler ise

q+(q-1)+(q-2)+.....1 =  q*(q+1)/2 >= n olması gerekir.

Güzel çözüm değil mi ? Tabi bu problemde yumurta sayısı da değiştirilebilir, strateji aynı.