• facebook ta işe başlamak için çözmeniz beklenen sorulardan biriymiş.

    soru şöyle : elinizde birbirine özdeş iki yumurta var. 100 katlı bir binadasınız. yumurtaların kırılmadan maksimum hangi kattan atılabileceğini en az denemede çözmeniz gerekiyor.

    daha basit anlatmak gerekirse sizden istenilen şunu söylemeniz :

    bu yumurtalar en fazla x kattan düştüğünde sağlam kalabilir. x+1'inci kattan düştüğünde kırılırlar.

    bunu en az kaç denemede bulabilirsiniz.

    not : yumurtalar bildiklerimizden daha dayanıklı yumurtalar. yani 10. kattan düştüklerinde kırılmama olasılıkları var. biz de zaten onların dayanıklılığını ölçüyoruz.

    not2: sadece 2 yumurtamız var. bunlar kırılınca daha fazla deneme yapamıyoruz.

    not 3: biraz ipucu vereyim. eğer 1 yumurtamız olsaydı önce 1. kattan denerdik. kırılmazsa 2. kattan atar denerdik. böyle böyle 100 denemede 100 katlı bina için sonucu bulurduk.

    not4: cevap ciddi matematik ve mantık bilgisi gerektiriyor. tek başına bulan bana göre cidden sağlam bir zekaya sahip.

    not5 (edit) : bir yumurta atılıp kırılmazsa tekrar kullanılabilir. (belirtmeyince anlaşılmıyormuş)

    beğendiyseniz şunlar da ilginizi çekebilir :

    (bkz: iki general problemi)
    (bkz: iki zarf problemi)
    (bkz: iki kurşun problemi)
    (bkz: iki zar problemi)
  • (bkz: taşak)
  • çözümü çok kolay olan problem.
  • cevabı n(n+1)/2 >= 100 olan basit soru. yani 14. kat
  • facebook mutfağa eleman alımlarını bu şekilde gerçekleştiriyormuş. seneye de zaten facebook felan hep paralı olacak. ayrıca o konuda yumurtaya ben de çok kırgınım.
  • devrin fena değiştiğini bizlere gösteren problem.

    bizim gençliğimizde böyle sik sik problemleri hep mit'in falan sorduğu söylenirdi. bu problemi çözen mit'e giriyor, mulakatında şöyle şöyle sormuşlar diye efsaneler dolanırdı.

    sonra internet falan yaygınlaştı da adamlar kurtuldu lan bu mal muhabbetten. gerçekten zamanında böyle sorularla alıyorlarsa da kurtuldular cins cins soru bulmaktan, akp'liysen gel yoksa git şimdi mis gibi, kafa rahat, şu soruyu sorarken adam yorulur amk.

    şimdi facebook, twitter falan bu sorularla eleman alıyor geyikleri dönüyor. yaşlandığımı hatırladım yine ibneler.
  • şurda detaylı çözümü verilmiş olan problem.
  • ilk yumurta ile büyük skalayı, ikincisi ile küçük skalayı optimize etme işidir.

    trunc(100/x)+(x-2)'in minimum olduğu sonucu bulmalıyız.

    x = 10 için y = 18, x = 11 için y = 18, x = 12 için y = 16, x = 13 için y = 18

    yanıt 12'dir.

    diyelim ki yumurta 99. kattan atıldığında sağlam kalıyor, 100. kattan atıldığında kırılıyor.

    ilk yumurtayı her 10 kattan atsak, 10, 20 ... 90'a kadar kırılmaz iken 100'de kırılır. 10 deneme etti. 2. yumurtayı 8. atışında sonucu bulursun, toplam 18.

    ilk yumurtayı her 5 kattan atsak, 5, 10, 15 ... 95te kırılmaz iken 100'de kırılır. 20 deneme oldu şimdiden.

    her 12 kattan atsak 8.de kırılmayacaktır. 3 tane daha atarak bulruz etti 11.

    her 13 kattan atsak 7.de kırılmayacak ve üzerine 7 tane daha gerekecek etti 14.
  • (bkz: binary search)
  • kırılmayan yumurtayı yeniden atabileceğimiz için ilk atışı 50. kattan atmak yerine 33. kattan atmak daha mantıklı.
    33'ten atıldığında kırılırsa 1'den başlayarak 32 kat daha deneriz ve en fazla 33 denemede buluruz.
    33'ten kırılmazsa 65'ten deneriz, kırılırsa 34'ten başlayıp yine tek tek çıkarız ve en fazla 33 denemede buluruz.
    65'ten kırılmazsa 83'ten deneriz, kırılırsa 66'dan başlayarak tek tek deneriz ve en fazla 19 denemede buluruz. (yukarı katlardaysa denemeler giderek daha azalır)
    dolayısıyla en fazla 33 denemede sonuca ulaşırız...

    edit: biraz daha düşündüm de: sanırım daha doğrusu 10. kattan başlamak. 10'da kırılırsa 1'den başlayıp 9 kata kadar çıkıp en fazla 10 denemede sonuca ulaşırız. kırılmazsa 20'den atarız, kırılırsa 11'den başlayıp en fazla 11 denemede sonuca ulaşırız, bu şekilde 99. katta bile olsa en fazla 18 denemede sonuca ulaşıyoruz...

    edit 2: en doğru çözümü sanırım buldum. 10. kat yerine 14'ten başlarsak ve her kırılmadığında yaptığımız denemeyi düşerek bir eksik denersek (yani kırılmadığı sürece deneyeceğimiz katlar: 14, 27, 39, 50, 60, 69, 77, 84, 90, 95, 99) sonuca en fazla 14 denemede ulaşabiliyoruz. (benden bu kadar)
hesabın var mı? giriş yap