miercuri, 11 mai 2011

Problema cu 1000 de damigene de vin

Esti un mare imparat si peste 24 ore ai o si mai mare petrecere. La aceasta se vor servi 1000 damigene de vin. Insa afli ca una din ele este otravita. Otrava folosita nu are nici un fel de simtome pina la moartea propriu-zisa, iar aceasta apare intre 10 si 12 ore dupa administrarea chiar a unei cantitati minuscule de vin otravit.

Ai la dispozitie peste 1000 sclavi, insa moartea acestora nu ar da bine la petrecerea de a doua zi. Din fericire ai la dispozitie si un numar de prizonieri pe care ai fi dispus (bucuros) sa-i sacrifici pentru identificarea otravii.

Care este numarul minim de prizonieri necesar pentru a identifica damigeana otravita?

7 comentarii:

Lucian spunea...

date fiind conditiile, mai exact intervalul aparitiei mortii (10-12 ore), un prizonier poate testa 7 damigene in 24 de ore de aici rezulta ca un numar de 143 de prizonieri este raspunsul.

Eugen Popp spunea...

Salut! La problema precedenta nu ti-am raspuns ca era prea simpla.
Nu stiu daca abordarea asta e cea care va da rezultatul corect, ramane de vazut.
Ma gandesc la o abordare binara. De genul o persoana bea (f. putin) din 500 de damigene, alta din 250. Asa izolezi rand pe rand damigeana otravita... mai calculez

Raluca spunea...

Eu ma gndeam la un fel de scriere binara. Fiecare damigeana are un numar (0-999) care poate fi scris in baza 2. Fiecare cifra din scrierea baza 2 reprezinta un scalv. Daca =0 nu bea din damigeana aia, daca =1 atunci bea. Deci din damigeana numarul 9 = 000 000 100 1 o sa bea soldatul 0 si soldatul 3. Asa vazand care soldati au murit, stim din ce damigeana s-a baut. Daca mor soldatii 1, 3, 6 s=a baut din damigeana 2^1 + 2^3 + 2^6 = 74. Problema e ca nu am bagat deloc faza cu mor in 10-12 ore, deci poate incerca in mai multe randuri, deci ies maxim 9 soldati (500 damigene prima data, 500 dupa aia). Si daca mai stim sigur si care e intervalul de timp in care moare, rezulta ca poti imparti in 7 transe damigenele (asa zicea Lucioan, nu mai verific)... 143 damigene ... merg scrise pe 7 biti => 7 prizonieri.

Raluca spunea...

*pe 8 biti

Anonim spunea...

x prizonieri * y damigene = 1000, x cat mai mic dar x > y.
40 * 25 => 40 prizonieri gusta fiecare din cate 25 damigene. Unul moare dupa 10-12 ore, cele 25 damigene din care a gustat se pun deoparte si dintre cei 39 prizonieri ramasi se aleg 25. Dintre acestia 25, fiecare va gusta din cate o damigeana, dupa 10-12 ore cel care va muri va arata care damigeana este otravita. Deci 40 prizonieri in total.

Anonim spunea...

32 de prizonieri. Acestia vor fi impartiti in doua (chiar daca nu e corect :) ) 24 vor gusta din 31 de damingene si 8 vor gusta din 32 de damingene. Unul va muri dupa 10-12 ore. Cei 31 care au ramas vor gusta din cele 31 sau 32 de damingene ramase. Daca raman 31 de damingene e clar , daca raman 32 de damingene si nu va muri niciunul dintre cei 31 prizonieri ramasi in urmatoarele 10-12 ore atunci butoiul ramas este cel otravit.

Cristi spunea...

Eu cred ca e chiar simplu, cel putin daca e permisa varianta mea :)
Eu zic ca un prizonier ar fi bucuros sa lucreze ca sclav decat sa stea captiv, asa ca, toti cei 1000 de sclavi vor incerca cate o damigeana, iar unu din ei va muri in cele din urma,asa ca acel sclav va fi inlocuit cu un prizonier care are la dispozitie cel putin 12 ore sa invete sa fie sclav :)
Deci raspuns final 1 prizonier :)