Reklam Alanı

Hırsız ve Kasa

Bu soru 06 Ağustos 2009 tarihinde ZekiAdam tarafından gönderildi

Hırsızımız şifreli bir kasa çalar. Kasanın her hanesi 1’den 8’e kadar değişen 3 haneli bir şifresi vardır. Şifre mekanizması bozulduğu için şifrenin 2 basamağı doğru tutturulduğunda kasa açılmaktadır ( şifre 456 ise 416 veya 457 ile de kasa açılacaktır). Şifre ne olursa olsun hırsızımızın kasayı açmasını garanti edecek minimum şifre deneme sayısı nedir?

Facebook'ta Paylaş

2 votes, average: 3,00 out of 52 votes, average: 3,00 out of 52 votes, average: 3,00 out of 52 votes, average: 3,00 out of 52 votes, average: 3,00 out of 5 (2 Üye oyladı, Ortalama puan: 3,00)
Bu soruya puan verebilmek için üye olmalısınız.
Loading...

Etiketler: , , , , , , , , , ,


“Hırsız ve Kasa” için 28 Yorum

  1. ahmetekin dedi ki:

    81 diye düşündüm ama emin değilim

  2. yuckfou dedi ki:

    Soruyu (yanılmıyosam eski bir ımo sorusuydu) buraya aktaran kişi olarak bikaç uyarı yapmak istiyorum;

    -hırsız sadece ilk 2 hanesini alıp oraya gelecek 8*8=64 sayıyı denerse zaten kasayı açar demekki cevap 64 ten büyük değil.

    -sadece bir sayı yazıp bırakırsanız o sayı doğru bile olsa bir mantığı olmaz burada önemli olan o sayının nasıl bulunduğu ve ondan küçük sayıda deneme yapıldığında kasanın açılmasının garanti olmayacağının nasıl gösterildiğidir.

  3. onurkurban dedi ki:

    şifrenin rakamları birbirinden farklı mı? yoksa “111” gibi aynı sayı olabiliyor mu?..

  4. sahin dedi ki:

    18 dir.

    Meraklilari icin;

    simdi kasamisin sifresi uclu sifre olup herhangi iki dogru 1 ile 8 arasindaki dogru rakamlardan olusan ikili sayi kasamizi actigina gore; asagidaki denemeler yapilabilir;

    1,2,1
    1,2,2
    1,2,3
    1,2,4
    1,2,5
    1,2,6
    1,2,7
    1,2,8

    diyelim bunlardan hic biri kazamizi acamadi; buradan sonuc su olcakatir her hangibir (1,x) yada (2,x) de kasamizi acmamaktadir. Dolayisiyla bir sonraki denememiz 3’den baslamalidir, bu durumda;

    3,4,3
    3,4,4
    3,4,5
    3,4,6
    3,4,7
    3,4,8

    eger bu kombinasyonda acmiyor ise; cikan su sonuc olur. herhangibir (3,x) ve (4,x) sayi ikiliside kasamizi acmaz. Dolayisiyle bir sonraki deneme 5, 6, 7, 8 sayilarindan olusmali. ve bundan sonra denememizi asagidaki kombinasyonlardan olusmali.

    5,6,5
    5,6,6
    5,6,7
    5,6,8

    eger bu kombinasyonlardan hehangibir acmaz ise, (5,x) ve (6,x) ikilileride acmaz ve geriye kalan (7,8) kasayi acacaktir.

    Toplam maximum deneme 18 olur.

    Not: soru minimum deneme sayisini soruyor; isin ogrusu minimum denem 1 olabilir eger sansli iseniz, ilk denemede bulabilirsiniz. Halbuki, soru, maksimum kac denemede kasayi acilabilinecegini sormasi gerekir.

    • yuckfou dedi ki:

      Sanırım soruyu yanlış anlayarak bir çözüm yapmışsın.
      burada kasanın şifresinin 435 olduğunu varsayalım
      bu durumda hırsızımız kasayı;
      135,235,335,435,535,635,735,835
      415,425,445,455,465,475,485
      431,432,433,434,436,437,438
      denemelerinden hangisini yaparsa yapsın açabilir
      ama 345 denediğinde kasa açılmaz çünkü sadece 1 rakam kendi yerindedir ve dolayısıyla sadece 1 tane doğru hane tutturmuştur.(bir nevi milli piyangoda teselli ikramiyesi kazanma mantığı)

      eğer soruyu bu şekilde anlayıp yukardaki çözümü yapmışsan
      yazdığın şifre kombinasyonuyla birçok şifre için kasanın açılmayacağı açıktır örneğin kasanın şifresi 833 , 615 , 476 ne bileyim daha birçoğu en az 100 tane daha bulunur sanıyorum


      min. sayıdan kasıt açılmayı garanti edecek min. deneme mikatrıdır, kasa tabiki ilk denemede açılabilir ama bu deneme açılmasını garanti edemez. kasa tabiki 64 denemede kesin açılır ama bu da bunu sağlatabilen min. deneme sayısı değildir.

      ayrıca cevabın 18 den büyük olduğunu da söyleyebilirim.

    • yuckfou dedi ki:

      Ufak bir not daha düşmek istiyorum.
      abc gibi bir şifre denendiğinde genel bütünden eleyebileceğimiz max şifre sayısı 22 dir.
      hiç bir kesişim oluşturmadan deneyeceğimiz şifre kombinasyonlarını oluştursak bile ( ki bu imkansızdır) toplam 512 şifre kombinasyonu olabileceğinden tüm bu şifreleri örtebilmek için
      [|512/22|]+1 = 24 tane şifreden oluşan bir deneme listesi oluşturmamız gereklidir.

      • sahin dedi ki:

        Yuckfou, saolasin kardes; elestirin dogrultusunda, soruyu bir kez daha gozden gecirdim ve sana hak verdim. benim yaklasimim tamemen 3 kombinasyon uzerine, halbukuki, seninde belirttigin gibi, sadece kombinasyon degil, bulundugu yerde onemli.

        benim hatali yorumuma dayanan, hatali cozumu dikkate alan arkadaslardan ozur… ve ileri surdugum cozumu geri aliyorum.

      • sahin dedi ki:

        Yuckfou, bu arada burada ileri surdugun mantik pek gecerli degil gibi. Tabii mantigini dogru anladiysam; her seyden once, diyorsun ki, 24 deneme listesi olusturabiliriz cunku, eger denen sifre kasayi acmaz ise, genel elebilecegimiz sifre sayisi 22 dir. Bu biraz mantikli degil, cunku eger denen sifre duserse, onun dogru olmasi durumunda acabilecegi kombinasyonlari da acmaz gibi bir sonuca ulasiyorsun ki bu yanlis. Ornegin, 435 deneme listemizde ve diyelim acmadi bu durumda, 438 de acmamasi lazim cunku 438, 435’in ikili acanlari listesinde. Halbuki sifre 435’in acmamasi, 438’in acmaycagi anlamina gelmez; ornegin sifre pekala 538 olabilir ve bunun 438 li kombinasyonu onu acabilir. Ve bu durum olusturabilecek herhangibir deneme listesi icin de gecerlidir.

        Diger bir deyisle, nasil gruplandirma yaprsak yapalim, elde edecegimiz 24 adetlik deneme listesi, belirttigin metotla cozumu garanti etmez.

        NOT: ayrica 22 tanelik liste, ancak sifre bilindiginde olusturabilir. Dolayisiyla, bu acanlar gurubunu olusturulmasi, sifresinin bilinmesine kosuluna gore yapilmakta. Halbuki sifreyi bilmiyoruz.

        • yuckfou dedi ki:

          Burada ben çözüm değil sadece bir tespit yaptım cevap 24 tür demedim :)
          cevabın 23 olamayacağını gösterdim.
          hırsızımın her şifreyi açabilecek bir deneme listesi hazırladığını varsayalım. bu listedeki her deneme ile hırsızımız genel şifre havuzundan 22 tane şifreyi içeren kasayı açabilir ve önceden hiç çakıştırmasa bile 512 tane şifrelik tüm kümeyi kapatabilmesi için en az 24 tane eleman içeren bir deneme listesi oluşturmasının gerekli olduğunu söyledim, evet 24 olması gereklidir ama yeterli değildir.
          aradığımız sayı gerekli ve yeterli olan sayı. yani cevap 36 ise hiçkimse 35 tane elemanlı bir deneme listesiyle 512 şifrenin tamamını açamamalı, ve 36 tane elemanlı ve 512 şifrenin tamamını açabilen bir deneme listesinin var olması gerekir gibi…

        • yuckfou dedi ki:

          Kısaca soruda istenen genel olarak 2 şey;
          1.şifre ne olursa olsun açabilen k elemanlı bir şifre listesi
          2.k elemandan az eleman içeren her şifre deneme listesi için kasanın açılamadığı bazı şifrelerin bulunduğunun gösterilmesi.
          ———
          bu 2 şıktan ilkini biraz uğraşıp bulabileceğini düşünüyorum 2. için bi yorum yapamayacağım o da senin bu tür soularla daha önceden ne kadar karşılaştığına bağlı gibi sanki ama biraz zor diyebilirim. uğraşacağını düşündüğüm için şimdilik çözümü yazmıycam. kolay gelsin

  5. emrea dedi ki:

    Sayı 3 haneli olduğuna her basamak için 1-8 arası sayılardan bir grup sayı seçilir denenir. daha sonra bu grupların tümleyeni seçilir ve denenir ise mutlaka çözüm bulunur. çünkü ilk durumda bulamadığımızı varsayarsak sayılar yyd,ydy,dyy,yyy olabilir. 2. aşamada bu sayıların tümleyenlerini kullandığımız için en az 2 doğru sayıdan oluşan bir sıralama yakalanmış olur.

    o halde seçeceğimiz sayı gruplarında bulunan sayı adetlerinin çarpımlarının toplamı minimum olmalı. (acayip bir cümle oldu!). bunun için gruptaki sayı adetleri 1-7-1 (tümleyeni 7-1-7) seçilmeli. bu durumda ilk aşamada 7 deneme ikinci aşamada 49 deneme yapılır. toplam maksimum 56 deneme ile bulunur.

    1. soruda yürüttüğüm mantığı bile bu kadar zor izah edebildim. 2. için düşüncelerimi hiç ifade edemem :)

    • yuckfou dedi ki:

      Bu soru yanılmıyosam 1970 li yıllardan bir uluslararası matematik olimpiyatı için önerilen sorulardan. belki de çıkmış bir soru, araştırmadığım için kesin bişey söyleyemiyorum

      şimdi sorunun standart çözümünü ( neyse bu standart o da ilginç bi kavram :) ) bilen birisi olarak öncelikle mantığının çözümüyle büyük bi ilişkisi olmadığını ve cevabın 56 olmadığını söylemeliyim ama bu demek değil ki düşüncen yanlış. şimdi soruya hiç bu açıdan bakmadığım için bişey diyemiyorum ama senin bir grubun tümleyenini alma ve biri açmıyosa diğeri açıyodur yaklaşımının büyük ihtimalle soruyu çözebileceğini düşünüyorum. bana bikaç gün müsade edersen ben de bu mantıkla düşünüp soruyu çözmeye çalışcam inş. çözebiliriz,
      senin de cevabının yanlış olduğundan hareketle düşünmeye devam etmeni bekliyorum.

    • yuckfou dedi ki:

      Biraz üstünde düşündüm şimdi bu mantığın sorunun çözümüyle aslında ilişkisi de var denebilir ,bişeyler üretemezsek çözümü yazdığımda ilişkisi var mı yok mu yorumlarız.
      ama en azından her kasayı açan şifre listesini oluşturmada bu mantıktan gizli de olsa faydalanıyo diyebilirim.

  6. sahin dedi ki:

    Evet, arkadaslar, ben bu soruda nedense zorlandim. Cunku minimum olma kosulunu tam tespit edebilmis oldugum konusundan emin degilim. Ancak asagida detayini verdigim bir mantikla, minimum 56 dir diyebiliyorum. (Ki asagidaki ileri surdugum mantik ne derece, saglam henuz emin degilim)

    Sifremiz XYZ olsun ve A da her hangibir sayi olsun; burada, kasayi acacak ikili durumlar sunlardir: (A,Y,Z) veya (X,A,Z) veya (X,Y,A) dir. Yani, sifre sayilarindan bir tanesinin dogru olmama kosulu altinda, 3 degisik sayi gurubu kasayi acabilir. Bize denseki, size X,Y,Z,A farkli sayilarini veriyoruz, sifre sayilari farkli olma kosulu altinda, minimum deneme sayisi nedir? bu durumda, minimum deneme sayisi, 4!. Ancak sifremizin, herhangi iki sayisinin ayni olma ihtimali oldugundan, XXX, YYY, ZZZ, AAA kombinasyonlarinda denemeye sokmamiz gerekir; dolayisiyla 4 lu sayi gurubu icin toplam minimum deneme sayisi 28 dir.

    Peki elimizde 8 adet sayi var; durum ne olur? Bu durumda, 8 sayiyi, 4’lu iki gruba boleriz; ve her grup icinde olasi kombinasyonlari olusturuz. Peki bu 4 lu gruplar kasayi acmaya yeterlimir? evet yeterlidir. Diyelim Grup A ‘da su sayilar olsun {1,2,3,4} ve Group B’de geri kalanlari olsun {5,6,7,8} Simdi, Sifrenin ilk sayisi ya grup A’dandir yada Grup B’den; Ikincisi Ya grup A’dandir yada Grup B’den ucuncusu de ayni sekilde ya grup A’dandir yada Grup B’den. Diger bir deyisle, sifre sayilarindan en az iki tanesi ya grup A’dandir; ya da grup B’dendir. Dolayisiyla, bu sekilde olusturulacak deneme listesi, yeterlidir ve yukarida da belirttigim sekli ile, 4 lu sayi grubunda, en az 28 deneme yapmamiz gerektiginden; iki grubun (grup A’nin ve Grup B’nin) minimum deneme sayilarinin toplami kadar bir deneme yapmamiz -ki 56 deneme-, kasayi acmayi garantileyecektir.

    • yuckfou dedi ki:

      emrea’nın yorumuna da yazdığım gibi sayıları 2 ye ayırıp o 2 grup üzerinden bir deneme listesi oluşturmak bana çok hoş göründü. gerçeten ikinizin de yaklaşımı oldukça güzel
      56 elemanlı bir küme bulmanı bazı gereksiz durumları eleyememiş olmandan kaynaklandığını düşünüyorum. yoksa bu açıkladığın yöntemle minimum eleman sayısına sahip bir şifre deneme listesi oluşturulabilir.
      sadece bunun minimum olduğu gösterilemez ( komik oldu ama)
      demek istediğim önce olamayacağı bir sayı belirleyip sonra da bunun 1 fazla elemanlı durumu için her şifreyi açabilen bir deneme listesi oluşturulurken bu yolu kullanmak çok efektif.
      sorunun tabiri caizse kazıklığından dolayı aşağıya çözümünü yazmayı uygun gördüm

    • yuckfou dedi ki:

      Sorunun çözmünden de görüleceği gibi zorlanman gayet normal çünkü bu soru extra zor soru sınıfına giriyor diyebiliriz, belki de bu sitede şu ana kadar aktarılmış en zor soru olabilir. bana ne kadar itibar edersin bilemiyorum ama deneyimlerime dayanarak konuyla ne kadar ilgili olursa olsun bu soruyla ilk defa karşılaşan herkesin çözümde zorlanacağını söyleyebilirim.

  7. yuckfou dedi ki:

    1. öncelikle deneme litemizin eleman sayısının ne olamayacağını gösterelim
    varsayalım ki listemizde 31 eleman olsun (30,29,28 durumları bunun altkümesidir doğal olarak)
    bu durumda kümemizdeki şifrelerin 1. hanesine bakalım
    burada öyle bir a sayısı vardır ki bu a sayısı ile başlayan en fazla 3 eleman kümemizde bulunmalıdır. (güvercin yuvası p.)
    genelliği bozmadan a yı 1 kabul edelim

    şimdi bu 1xy şekilli şifrelere bakalım , 1<=x<=8 için bu şifreleri 8 e ayrıdığımızda öyle 5 tanesi bulunabilirki deneme listemizle kesişimi yoktur.
    yeniden genelliği bozmadan bunların x=1,2,3,4,5 olduğunu varsayabiliriz.
    bu 11y,12y,13y,14y,15y şekilli 40 şifreye baktığımızda
    en fazla 15 tanesinin deneme listemizde 1 ile başlayan elemanlar tarafından açılabilir ( kümemizde en faz 3 tane 1 ile başlayan eleman var)
    bu 40 şifreden geriye kalan 25 tanesi kümemizde 1 ile başlamayan şifreler tarafından açılmalıdır. 31-25 = 6 olduğundan
    deneme listemizde ortadaki hanesi 6,7,8 olan (a6y,a7y,a8y , a ve y 1 ile 8 arasında sayılar)
    en fazla 6 eleman vardır.
    bu 6,7,8 den en az 1 tanesi vardırki kümemiz en fazla 2 elemanı içerir.
    yeniden genelliği bozmadan bunun 6 olduğunu varsayalım.
    bu durumda a6y şekilli 64 değişik şifreye bakalım
    kümemizin 2 tane bu şekilli elemanı olduğundan bu elemanlar en fazla bu 64 şifreden 30 unu açabilir. geriye kalan 34 tane ortasında a6y şekilli şifrenin kümemizdeki ortasında 6 bulunmayan elemanlar tarafından açılması gerekir ki bu da ancak kümemizin 34 farklı ortasında 6 bulunmayan elelmanı olmasıyla mümkündür ki kümemizin 31 elelmanlı olmasıyla çelişkidir. yani kümemiz 31 ve daha az sayıda elelman içeremez.
    —————————————–

    2.şimdi 32 elemanlı bir şifre deneme listesi oluşturmaya çalışalım
    bu listeyi oluştururken emrea ve şahin arkadaşlarımızın belirttiği mantığı kullandım.
    8 tane sayımızı 4 er elemanlı 2 gruba ayıralım örneğin tekler ve çiftler
    {1,3,5,7} ve {2,4,6,8}
    oluşabilecek 512 şifreden her biri için bu kümelerden biri şifrede bulunan 2 sayılardan 2 sini içerir. yani her bir küme için oluşabilecek 2 lileri yazdığımızda tüm şifreleri açabiliriz.

    şimdi ilk kümeyi ele alalım
    4 elemandan 3 tanesini seçip tüm dizilimleri yazalım
    genelliği bozmadan 1,3,5 i seçelim ve 135 – 153 – 315 – 351 – 513 – 531 şekilli 6 şifreyi kümemize yazalım şimdi 7 leri kullanarak kalan kombinasyonları kapamaya çalışalım ama burada izleyeceğimiz yol 7 içeren şifrelerde diğerlerinin 2 şer geçmesini sağlatmak olsun ( 7 nin 1 kere muhakak geçtiğini düşünüp fazladan saymaları engellemek için bunu yazpıyoruz, eğer 7 geçmeseydi üstte yazdığımız 6 şifre zaten açardı)
    711-171-117-733-373-337-755-575-557-777 gibi yazılabilecek 10 şifreyi de yazdığımızda
    oluşturduğumuz toplam 16 şifrelik deneme listesi içinde {1,3,5,7} kümesinden 2 elemanı bulunduran her şifreyi açacaktır , benzer şekilde tüm tek sayıları 1 fazlası olan çiftlerle değiştirdiğimizde oluşacak şifreler de tüm kalan şifreleri açacaktır.
    yani 32 elemanı olan ve tüm 512 şifreyi açabilecek bir çok deneme listesinden birisi aşağıdaki gibidir;

    117,135,153,171,315,337,351,373
    513,531,557,575,711,733,755,777
    228,246,264,282,426,448,462,484
    624,642,668,686,822,844,866,888

  8. Mantiksal1i dedi ki:

    2 tanesi dogru oldugunda açılıyorsa ben 1 dk da açarım xd önce 1 ini 1 yap sonra digerini 8 e kadar durmadan cevirirken kasayı kendine dogru çek
    sonra 2-8
    3-8
    4-8
    5-8
    6-8
    7-8
    8-8

    şifre tuttugunda kasanın kilidi cıt diye atıcaktır bu sesi duymak zaten cok kolay kendimize çektigimiz için kasayı kilit oraya sıkışmış gibi bişey olucak kilit cevirmeli kola geçerken yaylı sistemle kilidin geri geldigini bilenleriniz vardır yay kendini atar :d ve ses cıkar kasa kapısını bıraktıgınızdada kilit açılmaya hazırdır :d

    neyse asıl cevap
    1-1
    1-2
    1-3
    1-4
    1-5
    1-6
    1-7
    1-8

    her seferinde azalarak gidecek 8 lerde 1 tane 7 lerde 2 6 larda 3 5 lerde 4 – 4 lerde 5 3 lerde 6 2 lerde 7 1 lerde 8 kez deneyecez yani 8+7+6+5+4+3+2+1 yani terim sayısı ( kilidin 8 lik olması ) kadar bir biri ile topluyacaz buda 36 eder :) bu en fazla denemesi gereken sayı :d:d
    en az için bununun yarısını alırız oda 18 eder :)

    niye 2 ye böldük diyenlere 2 li yaptık 3 lüye cevirirken araya 8 karakter daha girmekte :d eger bozuk olmasaydı 36.(8/3) olucaktı ama bozuk oldugu için 36/(8/4) 3+1 terim oldugu için 4 e böldük :)

    • MyNameis_HIDIR dedi ki:

      2 tanesi doğru olduğunda açılıyo ve 33. denemeyi yaptığında kasa açılmamışsa patlıyomuş.

      çözümüne gelince anlamaya çalışıyorum ama gerçekten bağlantı kuramıyorum.

      şimdi 1 lerde 8 kez denemeden kasıt

      111,112,113,114,115,116,117,118 denemeleriyse
      ve bu mantıkla yapılan
      122,123,124,125,126,127,128
      133,134,135,136,137,138,

      177,178
      188

      28 denemeyle kasayı açmayı düşünmüşsen yanıldığını söyleyebilirim. bu denemelerin açamadığı yüzden fazla şifre vardır heralde, örneğin 876 ya da 765

      ——

      yukarda bu sorunun çözümünü herhangi bir kuşkuya mahal bırakmayacak şekilde (en azından ben öyle düşünüyorum) yazmıştım. soruyu okuyup bırakmasaydın az bişey de yorumları okuma zahmetine girseydin cevabının yanlış olduğunu zaten yazmadan görebilirdin. yok eğer yorumları ve dolayısıyla benim çözümümü okuyup bu cevabı yazmışsan benim çözümümün yanlış olduğunu düşünüyosundur ki nerlerde itirazın varsa söylersen tartışabiliriz.
      yorumlarda da yazdığım gibi soru eski bir uluslarası mat. olimpiyadı sorusu, soruyu önerenin nasıl çözdüğünü bilmiyorum ama cevabın 32 olduğunu biliyorum.

  9. nihilist dedi ki:

    32 olmasi lazim.
    yorumlari okumadim, eger daha once cevabi verildiyse ve benim cevabimdan farkliysa benim hatam.
    bu sonuca bes dakikada vardim umarim dogrudur.
    2 haneyi tuttursa yeterlidir diyorsun,
    o zaman 8 x 2 = 16
    16 x 2 = 32

  10. deanlamindakidahi dedi ki:

    Peki bu soruyu biraz degistirerek ben sorsam ve ilk denemede dogru bilme olasiligi nedir desem cevabiniz ne olurdu?

  11. deanlamindakidahi dedi ki:

    8*8*8/3 dogru cevap midir sizce?

  12. deanlamindakidahi dedi ki:

    Pardon 8*8/3 olucaktı

  13. sertac dedi ki:

    cevap 15; diyelim ki ilk iki rakam 8 111 211 311 411 511 611 711 811 821 831 841 851 861 871 881

  14. enisten dedi ki:

    ilki bozuksa 64 hangisinin bozuk olduğunu bilmiyorsak 192dir

Cevap yazın

Yorum yapabilmek için giriş yapmalısınız.