Задача с бурета

Сподели тази публикация:

В една далечна страна, живеел крал, известен с организирането на огромни банкети… Всяка година кралят дарявал 1000 бурета със скъпо вино, викал най-добрите диджеи и танцьорки за партито, а последната година дори поканил „Те“, „Б.Т.Р.“, Лили Иванова, група „ФМИ“ и дори Manowar на банкета…
Въобще, купонът се очертавал да бъде тотално на макс, но точно 5 дни преди партито един отмъстителен селянин-нинджа се промъкнал до 1000-та бурета и сипал отрова в едно от тях…
Кралят предвидливо бил сложил СОТ във винарната, така че охраната заловила селянина, докато се опитвал да избяга… за съжаление, не станало ясно кое точно буре с вино било отровено.
Кралският лаборант в момента се занимавал с откриването на ваксина против СПИН, така че нямало как да се занимава с изследването на буретата. За съжаление, отровата била толкова силна, че една капка от нея можела да убие човек, дори ако е изсипана в милиони литри вино! Също така, отровата не убивала внезапно – жертвата умирала 3 дни след изпиването й.
Кралят решил да открие отровеното буре, като използва осъдени на смърт затворници. Естествено, ако имаше 1000 затворници, осъдени на смърт, работата му би била много лесна – номерира затворниците от 1 до 1000, дава на затворник 1 – буре 1, на затворник 2 – буре 2 и т. н. до 1000… след 3 дни резултатът става ясен. Ето защо в задачата се пита – какъв е най-малкият брой затворници, с който може да се определи кое буре е отровено, така че банкетът да се организира с останалите 999 бурета?

Сподели тази публикация:

44 мнения за “Задача с бурета”

  1. Задачата пак ти е харесала, а deadline чука на вратата ли? 🙂

  2. edit:
    хахахахахха

    е с тая задача скрих шапката на един програмист 😉

    дай ми десет затворника и ти казвам кое ти е отровеното буре.

    (само дето на мен ми я казаха със 100 бурета и после дъъълго време обяснявах, че 7 затворника ми стигат…. явно софийското фми е по-слабичко 😉 )

  3. Чакам решението ти, Силвия, щото по моите изчисления са нужни 333. То всичко зависи от точността с която определяме за колко време действа отровата, но да приемем, че действието от 3 дни означава между 48:01 часа и 72:00 часа след приемането на отровата…

  4. Глупости!
    Как не ме е срам, при условие, че съм завършил ФМИ… Отговорът е 10. Решението чакам от вас!

  5. Всичко зависи от времето на действие и от времето, с което разполагаме :
    При достатъчно време даже един ни е достатъчен- една по една пробва всяка бъчва като изчаква … до евентуалното откриване на бъчвата.

    Но при недостатъчно време ето примерно решение :

    Да приемем случай при който имаме 3-ма затворници A,B&C и 8 бурета номерирани от 1 до 8- получаваме следната матрица:

    . 1 2 3 4 5 6 7 8
    A 0 0 0 0 1 1 1 1
    B 0 0 1 1 0 0 1 1
    C 0 1 0 1 0 1 0 1

    A опитва вина от бурета 5,6,7,8

    B от 3,4,7,8 и C от 2,4,6,8.

    така че ако A,B,C са живи, тогава отровното буре е 1.
    A,B са живи & C е умрял тогава буре 2 е отровнои т.н…

    със 3 затворника може да открием отровното буре от 8 бурета (2^3=8).

    Така че е възможно да открием отровното буре от 1000 с 10 зтворника = 2^10=1024 бурета

  6. решението е ужасно просто и логично, връщам си думите за софийското фми, явно и то е също толкова силно като пловдивското.

    Ами много е просто – представяме числата от 1 до 1000 по единствения начин в двоичен вид. Номерираме затворниците от 0 до 9. Всеки от затворниците пие от буретата, в които на позицията, броено отдясно наляво (започвайки от нула) фигурира 1-чка в двоичния запис на бурето.

    Така от бурета 7, 42, 333, 456, 1000 ще пият съответно затворници {0,1,2}, {1,3,5}, {0,2,3,6,8}, {3,6,7,8}, {3,5,6,7,8,9}.

    Така като умрат затворници с номера х1…..хк – намираме номера на заразеното буре по формулката sum(2^i). Тоест ако умрат {0,2,3,5,7,9}, то заразеното буре е:
    2^0 + 2^2 + 2^3 + 2^5 + 2^7 + 2^9. , тоест 1 + 4 + 8 + 32 + 128 + 512 = 685.

    Естествено най-прецакани са затворниците с по-малки номера. Например шанса на затворник 0 да се отрови е 50/50… Ама на краля не би следвало да му пука.

    (извинявам се, не съм била особено добра в обясненията…)

  7. Браво, Силвия и Erko! Имате по една бира от мен 🙂

  8. :)))) Хубаво обещание на място – току що прочетох една статия в dir.bg за бирата :

    „Бирата е най-полезна … сутрин на гладно
    24 юни 2008 / News.dir.bg
    Хубаво е да се пие студена бира сутрин на гладно. Тя действала като сутрешния душ.
    Това каза диетологът Милка Милушева, цитирана от Фокус.
    Милушева посочи, че бирата почиства организма и по-специално пикочните пътища и черния дроб. Освен това хмелът действа успокояващо на нервната система. Важно е обаче приемът и да не се превръща в ежедневие, тъй като тогава може да се стигне до битов алкохолизъм. Изпита вечер преди 20 часа обаче бирата осигурява добър и спокоен сън.
    През лятото е добре да се консумират и много плодове и зеленчуци, но сезонни, не цитрусови. Те трябва да се употребяват предимно сурови, добре измити и в никакъв случая да не се ядат вечер в големи количества, тъй като съдържат целулоза, а нейното преработване изисква по-голямо натоварване на храносмилателния тракт.
    Изключително полезно според диетоложката е и да се похапват и желирани храни, тъй като желатинът освежава работата на черния дроб, бъбреците и има пряко отношение към лекото и бързо смилане. Според Милушева полезни за летния сезон са и сладоледите, но не сметановите, а плодовите, тъй като те носят по-малко калории.
    Плодовите сладоледи са за предпочитани още заради това, че подтикват образуването на повече хормони на щастието – ендорфини. По думите на диетоложката 300 грама сладолед може безпроблемно да замести една вечеря, ако човекът се е хранил по-обилно през деня. Сладоледът, както и бирата са полезни заради това, че понеже са студени храни организмът ги затопля и така употребява и гори повече калории. Това помага на човек да не тлъстее въпреки, че си похапва.“

  9. ама да знаеш, че аз такива обещания не ги забравям 😉

    ако може и да е на някое бургаско капанче с огромна купа цаца….

    ех, размечтах се 🙂

  10. А не могат ли да накарат селянина, който е заразил бурето (и са го заловили), да отпие последователно от всяко буре. Ако му е мил живота, няма да пие от заразеното. Освен ако не е камикадзе 🙂

  11. Мммм оцелял – 0, умрял – 1. На всеки затворник даваме уникална комбинация от вина, като ако сме му дали от отровното, той е 1, ако не сме – 0. Това означава, че като номерираме всяка бъчва, трябва да можем да запишем номера й с двоично число (числото, което се получава от стринга смърт/живот на затворниците). След като го смятах и установих, че 2 на осма е 1024, отговорът ми беше 8. После прочетох, че верният отговор е 10 и разбрах, че съм тъпак. 🙂 2 на десета е 1024, което е най-малкият точен квадрат, който е по-голям от (или равен на – няма да мога да заспя довечера, ако не го напиша това) 1000, така че това е отговорът.

  12. Filip, в условието е казано, че е нинджа, няма как да разчитаме на това! 😉
    TAfricanski, не точен квадрат, а степен на двойката!

  13. КАК изкара 333 затворници? Защо раздели точно на 3, че й после трънкейтна, а не закръгли нагоре?
    Силвия, да те питам – защо номерира първия затворник 0? 😀 Егати промитите мозъци. 🙂
    Иначе ще прочета внимателно точния алгоритъм на установяване на отровното буре – въпросът беше за броя затворници, така че не съм го мислил, а и няма да мога сам да го измисля.

  14. Пешо, да, голяма тъпотия написах…

  15. Вие сте болни.
    Как може в тези жеги да мислите…

  16. tafrikanski – нямаш никакъв проблем да ги номерираш от 1 до 10 ако искаш. Просто ако ги номерираш от 1 до 10 трябва за да установиш шравилното буре да приложиш формулката sum(2^(i-1))…. същата работа реално погледнато 😉

    В интерес на истината, ако имаш 1024 бурета например, пак може да минеш с 10 затворника, стига от едно буре никой никога да не пие(последното) ако никой не умре – значи то е заразеното.

    А въпроса за чене в жеги хич и не го повдигайте в мое присъствие, че ми е Държавен Изпит на хоризонта.

  17. Срамота ви за ФМИ-то 😉

    Това е екстремална задача – всички описвате решение, но не доказвате, че то е екстремалното (най-малко).

    Среден (3+) 😉

  18. аз допуснах, че след отпиване от отровеното буре, човек умира след 72 часа (не е ли така по условие?)..

    след което сметнах, че ако веднага почнат да пият, всеки затворник от различно буре на кръгъл час, ще са необходими 20 затворника. първия пие от 1-во до 10то буре, 2-я от 11-то до 20-то и тн.като се водят записки в колко точно часа отпиват..

    следователо ако пият на половин час, са нужни 10. на всеки по 20 различни бурета, и изчисление „час на смъртта минус 72 = x точен час“ и след това намиране на бурето по точен час в записките

    следователно, 5 затворника ще са достатъчни ако отпиват на 15 минути,и трима ако отпиват на 5 минути. ако един затворник пие от всички бурета, то максимума интервал, който може да се допусне, е 1.67 минути..

    това е ако е известно, че отпиване от отровата + точно 72ч. е равно на смърт.

  19. petаr, най-малкото е, защото във всяка друга бройна система трябва да отчетеш коефициент от 0 до n-1 където n ти е съответната бройа система (това мдд ми е във въпроса по висша алгебра), а в случая няма как да отчетеш степента на пиене – или пие или не. И ако го направиш в троична бройна система например, ще трябва да имаш три затворника за всяко – един не пие, един пие една лъжичка, втори пие две лъжички. Обаче като тръгнеш да изчисляваш кое е заразеното буре – и този с една и този с две лъжички (и този с n-1) ще са „еднакво умрели“. Тоест само с двоична система ти е биекция функцията. Аз поне за тая задача с друга бройна система не се сещам как ще го направят. 😉 Тука или умира или не умира. Тоест коефииентите ти не могат да са повече от два, тогава за всяка друга бройна система задачата гърми. Поправете ме, ако греша 😉

    p.s. Аз на 3+ съм съгласна, къде и кога да нося книжката????

  20. Има много особености в задачата, а аз винаги съм мразел доказателствата… Ясно е, че за 3 дни определяме с log(2,N) затворници кое от N бурета е отровено. Но ние имаме 5 дни… Т.е. ако разделим буретата на 3 равни части от по 333 бурета, имаме възможност да засичаме и на кой ден умира даден затворник… Тогава ще можем да решим задачата и с 9 затворници…
    Интересното е, че с 9 можем да я решим и ако буретата са не 1000, а 1536(=3 дни х 512 бурета в множество). Така с 10 затворници пък можем да тестваме измежду цели 3 х 1024 = 3072 бурета!

  21. Не знам, доколко се разбра, затова:
    В крайна сметка отговорът е 9, ако използваме факта, че имаме 5 дни за тестване.
    Екстремалността се доказва най-лесно с допускане на противното. Т.е. при решението на Силвия допускаме, че задачата може да се докаже с един затворник по-малко. Тогава за всеки затворник имаме случай, в който две бурета се представят чрез затворници с едни и същи номера, т.е. бурето не може да се определи еднозначно, т.е. стигаме до противоречие… Поне за 4 хванахме ли, адаш?

  22. додо принципно е прав с посоката на логиката си, ако наистина имаме 5 дена на разположение и 3 за смърт.

    ….
    Тогава обаче, комбинирайки логиката на borime4kata за 1000/3, няма ли да паднат до 10/3, тоест 3 затворника?

  23. Не, Силвия…
    Не падат до trunc(log(2,1000)/3+0.5) = 4, а до trunc(log(2,1000/3)+0.5) = 9 – който може, да използва математически запис на горните формули, на информатиците им е ясно.
    Колкото до предположението на Додо, ако е толкова точно, ще ни стигне и един затворник, който отпива примерно на всеки 10 секунди по глътка от дадено буре, след което просто му засичаме час на смъртта, вадим 3 дни и получаваме часа, в който е пито от дадено буре – преглеждаме .log файловете и готово! 🙂

  24. дам, знаех си, че тая логика трябва да изгърми някъде 😉 Не ти прочетох твоите обяснения, когато го писах. Последно пазим ли си бирата с erko или се отмяташ? 😉

  25. Пазим я, естествено… Бирата си е бира!

  26. Това с 9те е вече извратено. Да, прави сте, но е извратено. Ако умират точно след 3 дни, добре, но след като „нинджа“ означава, че поради някаква причина или няма да можем да го накараме да пие от буретата, или че той няма да умре от отровата, или че би се самоубил, само за да не им покаже кое е отровното, без това да е изрично казано в условието, значи го приемаме за подразбиращо се. А по подразбиране отровите не убиват точно по часовник и никога не може да има сигурност 100% при тях. Така че са си 10 пък. 🙂

  27. E, to e ochevidno che purvoto reshenie (deto dava otgovor 10) e chupeno
    ako e viarno ne izpolzva pulnia resurs (vremeto) toest ima po-dobro reshenie ako ne e viarno… prosto ne e viarno.

    Tova razbira se ne oznachava, che e ochevidno, che otgovorut e greshen, a che nachina za stigane do nego neshto kuca. Vsichki znaem, che v zadachite nikoga niama nenujna informacia.

  28. Osven tova mi se struva che ideiata da se polzva dvoichna broina sistema ne e suvsem pravilna
    ako priemem che nai-malkata edinica za vreme e den (shtoto zadachata inache e idiotska) i ako priemem che ima 3 dena v koito moje da umre zatvornika (to taka e kazano) znachi ima 3 vuzmojni sustoiania spriamo vsiako bure
    pil predi 1via den
    pil predi 2ria den
    pil predi 3tia den
    taka sus 7 troichni cifri(zatvornika) moje da predstavim 3^7=2187 bureta

    eto primer s 27 bureta nomerirani v troichna broina sistema pochvashta ot 0 0 0
    0 0 0 – 1
    0 0 1 – 2
    0 0 2 – 3
    0 1 0 – 4
    0 1 1 – 5
    0 1 2 – 6
    0 2 0 – 7
    0 2 1 – 8
    0 2 2 – 9
    1 0 0 – 10
    1 0 1 – 11
    1 0 2 – 12
    1 1 0 – 13
    1 1 1 – 14
    1 1 2 – 15
    1 2 0 – 16
    1 2 1 – 17
    1 2 2 – 18
    2 0 0 – 19
    2 0 1 – 20
    2 0 2 – 21
    2 1 0 – 22
    2 1 1 – 23
    2 1 2 – 24
    2 2 0 – 25
    2 2 1 – 26
    2 2 2 – 27

    zatvornik 1 shte pie v den 1vi ot buretata v koito ima 0 v purvata kolona
    zatvornik 2 shte pie v den 1vi ot buretata v koito ima 0 vuv vtorata kolona
    zatvornk 3 shte pie v den 1vi ot buretata v koito ima 0 v tretata kolona
    v den vtori sushtoto ama gledat da ima 1ci v suotvetnite koloni
    i v den 3ti shte piat kogato ima 2ki
    za 1000 bureta sushtoto ama sus 7 koloni

    taka kato zasechem koi koga e puknal shte imame unikalen identifikator na buretata ako primerno kolona 2 pukne v den 3 znachi zapodozreni sa buretata deto imat vtora cifra 2

    btw smiatam che pravilnia otgovor e 5
    koito izmisli zashto moje da vzeme birata mi ot Subev

    Moje i da izpisah masa gluposti v koito sluchai se priznavam za po-prost ot Subev i poveche niama da pisha za nikvi zadachi da ne se izlagam kato nego.

    Osven tova iskam da otbeleja zabelejitelnia napreduk koito imate ot predishnia put kato se postvaha zadachi. Tazi e znachitelno po-slojna ot „kakva e veroiatnostta ot 2 kutii da ni se e padnala tazi s nagradata“. Osven tova tozi put napredvate s otgovorite malko po-malko i nai-vajnoto TOZI PUT SUBEV NE E PISAL PROGRAMA DA RESHAVA ZADACHATA!

  29. assumption1: Задачата не е малоумна, и фактът, че купонът е след „точно“ пет дни има значение

    assumption2: Задачата не е малоумна, и фактът, че използваната единица за отмерване на време е „дни“ означава, че това е най-малката мярна единица която може да се използва за решението

    assumption3: 90% от коментиралите не са малоумни, и само се правят на такива

    assumption4: авторът на задачата и той не е малоумен, но пък добре се прави

    Май много assumption-и станаха….

  30. Stilgar, съвсем си прав, трябва да призная… Изобщо не ми беше хрумвало за троична бройна система!
    Todor, всъщност само един assumption: нищо не е малоумно 🙂

  31. Идеята на 5 е, че е по-малко от 6, което пък е 2*3. Тоест имаме точно една проба, не можем да правим втора. И понеже сега ще кажете защо точно 5 – еми трябва да е НЕЩО, а понеже между 3 и 6 няма особено много цели числа, вероятността да е просто така е толкова голяма, че да ти се доплаче. Казаха ви алгоритъм с нито един умрял затворник – карате отровителя да пие от 999 бъчви. Не ви хареса, ама сега ще си смучем от пръстите, че отровата убива за между 7,15000000Е+01 и 7,25000000Е+01 часа…

  32. Само да вметна, че да се заяждаме за части от секундата в тази задача няма никакъв смисъл, понеже за да върви такава логика и да няма излишък в условието, то цитиращия задачата трябва да е много наясно с решението и с условията които са нужни и/или излишни. Аз лично тази задача съм я виждала в няколко варианта, включително с 2-ма мъдреци, ама нямаш пораво да убиваш никой от тях. Е като нямаш право да ги убиваш, защо са двама, ами не един? Много просто – понеже автора на задачата го прави по-интересно, но тази част от условието няма никаква връзка с решението. Толкова.

    При положение, че проверяващия (тоест черпещият бири и задаващия конкретното условие) сам не е наясно (в момента на цитиране на условието), то всякакви спорове за това има ли излишество от данни/липса на данни са повече от неоснователни.

    Хайде пийте по една студена бира и по-спокойничко. 😉

  33. Аз пък, като биолог човек, мисля че задачата може да се реши със същата математика дето я обяснявахте на дълго и на широко до сега, но като се ползват 0 затворници и за доста по кратко време.
    Просто кралят от задачата трябва да хване 10 придворни мишки и да експериментира на тях! Поради краткия им естествен живот (~ 2г.) и забързания метаболизъм, мишките биха реагирали на отровата много по бързо, така че вместо да се чака 3 дена да се види дали затворникът ще умре, се чака към 3 часа и се гледа дали мишката ще умре! Вероятно ще трябват 1 – 2 екстра мишки за контролна група да се види дали отровата им въздейства, как и колко бързо! Но за разлика от затворниците, мишките в един царкси палат са много по-неограничена бройка. 🙂

  34. Mda mnogo ste ostroumni! Stiga da ne beshe ochevidno che tova e shibana matematicheska zadacha i smisula i e da se reshi matematicheski. V kraina smetka ako ne iskate da ia reshavate prosto ne ia reshavaite.

    Silvia ne vijdam kvo se obiasniavash. Fakt e, che reshenieto ti e chupeno i ne znam kvi shapki kriesh s nego. Ne ia znam taia zadacha s mudrecite ama kato nishto i tam e imalo smisul da sa 2ma.

    iskam sushto da higlight-na liubimia mi post ot Subev:

    Не падат до trunc(log(2,1000)/3+0.5) = 4, а до trunc(log(2,1000/3)+0.5) = 9 – който може, да използва математически запис на горните формули, на информатиците им е ясно.

    ne znam koe e po-zabavno v tozi post, che tezi velichestveni smetki niamat nikva vruzka sus zadachata ili che I DVETE sa smetnati greshno

  35. Stilgar, колкото си неграмотен, толкова и ти се заяжда.

  36. poveche:)
    osven tva az kato sum negramoten ne postvam eseta na tema pravopis

  37. За добро или за зло, ако не можеш да дишаш, не стига да не пишеш есета за дишане. Мре се.

  38. 5 е долната граница. За всеки затворник има 4 възможности – остава жив, умира на 3-ия, 4-ия или 5-ия ден, съответно. 4^5 > 1000 > 4^4. Предполагам, че няма да е трудно да се намери съответния оптимален алгоритъм…

  39. На пръв прочит ми хрумва числото 30.
    Може би не е минималната бройка но е реалнен брой хора, които могат да изпълват килиите на двореца в този момент. Аз поне ако бях крал щях да се задоволя с 30 и нямаше да мисля повече (дори и да е възможно по-малко престъпници да умрат).
    Моето решение е просто>>>
    Нареждат се буретата в простата 3-измерна фигурка, наречена куб, като всяка страна на куба има 10 бурета (10х10х10=1000). Всеки от 30-те затворника трябва да отпие от точно 100 бурета (което е малко много, но какво от това);
    Първите 10 започват да пият от бъчвите по колони от по 10х10, следващите 10 започват да пият по редове (10 реда от по 10х10 буррета) и най накрая -> последните 10 пият по етажи (10 етажа от по 10х10 бурета)…
    Така накрая на експеримента ще има пбщо 3ма мъртви от 30 пили от буретата в тази 3измерна матрица – а това е допустим резултат – особено след подсказката, че действието на отровата се установаява точно след 3 дни 🙂
    Предполагам всички се досещате кое ще е отровното буре, убило 3ма от нещастниците – това което попада в съответната колона/ред/етаж от куба. Може и да стане с по малко „плъхове“, но едва ли с по малко жертви 🙂 Това измислих за 20 секунди 😉

  40. И ако все пак имам 5 дни (което пропуснах на пръв прочит) то вместо 30 души можем да използваме само 10, но като изпиването по колони/редици/етажи става на 24 часа. Така след точно 72/96/120 часа ще имаме:
    1/0/0 починали
    1/1/0 починали
    1/1/1 починали
    1/0/1 починали
    според точния ден и брой на жертвите можем да определим кое е заразеното буре…
    Не знам защо (можеби заради логическото си мислене и слабата си програмистка култура) си мисля, че решението може да се намери не само чрез алгебра, а също чрез проста права мисъл. Не знам…

  41. И последно да добавя една главоблъсканица за всички умни глави тука…
    Какво ще стане, ако се опитате да докажете минималния брой, като имате право на 3 опита и развиете тези опити в различна числова система за всеки от опитите: двуична, троична и 4ворична да кажем.
    Или погледанто от др. ъгъл:
    n броя пият по следния ред
    ден 1: 010101010101 тн за 2ична
    ден 2: 210210210210 и тн за 3ична
    ден 3: 321032103120 и тн за 4ична
    за всеки от n и така при засечка на 3те системи да намерим правилният отговор… предполагам е възможно
    ако n^2хn^3хn^4>m примерно, като вие определите какво по дяволите е m 🙂
    надявам се дори да имам огромни пропуски в теорията си да помогна на някой по-развит в тази област на математиката да стигне до някакъв извод и да разцепи с ненормално решение 🙂 не знам
    поне се зарибих по този блог…
    ех… ако бях учил още малко математика…
    😉

Вашият коментар

Вашият имейл адрес няма да бъде публикуван.