Pentru a vă înregistra, vă rugăm să trimiteți un email către administratorul site-ului.
Pune o întrebare

3.6k intrebari

6.8k raspunsuri

15.5k comentarii

2.5k utilizatori

3 plusuri 0 minusuri
2.0k vizualizari
Iată întreg scenariul:

Un rege urmează să dea o petrecere a doua zi.

Plănuieşte să deschidă 1000 de sticle de vin cu această ocazie. Află că una din cele 1000 de sticle conţine otravă, o otravă mortală, indiferent cât de mică e cantitatea consumată şi care nu dă niciun simptom înainte de deces, care survine la 10-20 de ore după consum.

Regele are peste 1000 de sclavi la dispoziţie şi mai puţin de 24 de ore pentru a găsi sticla cu otravă.

Regele are la dispoziţie şi câţiva prizonieri condamnaţi deja la moarte şi nu ar vrea să mai sacrifice şi alte vieţi înainte de petrecere.

Care este numărul minim de prizonieri care trebuie să bea din sticlele de vin astfel încât să asigure găsirea sticlei otrăvite în mai puţin de 24 de ore?
Senior (8.1k puncte) in categoria Matematica
0 0
Ar mai trebui specificată şi premiza că se pot "degusta" porţii de vin oricât de mici e nevoie din oricâte sticle, evitându-se astfel varianta intoxicaţiei cu alcool a prizonierilor. Mai mult, degustarea dintr-o sticlă durează oricât de puţin timp e nevoie.

3 Raspunsuri

7 plusuri 0 minusuri
 
Cel mai bun raspuns
Eu m-aș descurca cu 10 condamnați, caz în care soluția merge pînă la 1024 de sticle.

Sclavii fac următoarele operații:

- numerotează toate sticlele începînd de la 0, în baza 2 (pentru comoditate);
- numerotează condamnații începînd de la 0;
- prepară amestecuri pentru fiecare condamnat luînd picături din anumite sticle.

Și anume, pentru condamnatul numărul 0 sclavii prepară un amestec cu picături din acele sticle care au pe poziția 0 (a unităților) cifra 1. Mai exact, condamnatul nr. 0 nu bea din sticla nr. 0, bea din sticla nr. 1, din nr. 2 nu, din nr. 3 da etc.

La fel și ceilalți, după regula: condamnatul N bea din sticlele care pe poziția N au cifra 1. Asta înseamnă că nu bea din primele 2^N sticle, bea din următoarele 2^N etc.

Cînd trece perioada după care acționează otrava, mă uit cine a murit. Alcătuiesc un număr de 10 cifre în binar care pe fiecare poziție N are cifra 0 dacă condamnatul N e viu și cifra 1 dacă e mort. Numărul astfel alcătuit este egal cu numărul de pe sticla cu otravă. Problemă rezolvată.

De exemplu, dacă au murit condamnații nr. 0, 1, 2, 5, 6, 7, 8, 9 (adică au rămas în viață numai condamnații nr. 3 și 4) înseamnă că sticla cu otravă are numărul 1111100111, adică în zecimal 999, adică e ultima sticlă din cele 1000.

Încă nu știu bine cum aș optimiza organizarea muncii. S-ar putea să existe o metodă simplă de a mișca sclavii așa încît să nu fie nevoie ca ei să aibă cunoștințe de aritmetică binară, dar încă nu știu cum aș face asta. Așa că, dacă nu găsesc nici un sclav priceput, aș scrie eu numerele pe sticle, iar lor le-aș lăsa operația simplă de a prepara amestecurile conform cu numerele scrise de mine.
Expert (12.9k puncte)
0 0
Foarte ingenios. Felicitări! Cred că pentru o înţelegere de toată lumea a metodei propuse ar fi util să reducem problema la 3 prizonieri şi 8 sticle de vin.
0 0
Și eu am rezolvat-o mai întîi cu 16 sticle, pentru simplitate, și apoi am extins-o la cît cerea enunțul.
0 0
O observație: dacă sînt mai puțin de 1024 sticle, putem face numerotarea sticlelor în așa fel încît să moară cît mai puțini condamnați. Pentru asta evităm numerotările sticlelor care se scriu în binar cu multe cifre de 1. De exemplu dacă avem 1023 de sticle eliminăm numărul care se scrie cu 10 cifre de 1, deci din cei 10 condamnați mor cel mult 9. Dacă avem 1013 sticle eliminăm toate numerotările care se scriu cu 9 sau cu 10 cifre de 1, deci mor cel mult 8 condamnați. Și așa mai departe.

Dar problema întreabă care e numărul minim de condamnați care trebuie să bea, nu care trebuie să moară. Dacă ar întreba cîți trebuie să moară răspunsul ar fi simplu: unul. Dai să bea la 1000 de condamnați cîte o picătură dintr-o singură sticlă. Dar problema ar fi banală.
Daca otrava s-ar afla in sticla numerotata cu 0?
0 0
Nu ştiu dacă a înţeles toată lumea, aşa că adaptez răspunsul lui AdiJapan la 3 prizonieri şi 2^3=8 sticle:

                    Sticla1 Sticla2 Sticla3 Sticla4 Sticla5 Sticla6 Sticla7 Sticla8
Prizonier 1                   x                    x                     x                     x
Prizonier 2                              x         x                                 x         x    
Prizonier 3                                                    x          x          x         x

Fiecare prizonier bea din sticlele unde are marcat un x.  Dacă mor toţi, sticla8 e cu otravă. Dacă nu moare niciunul, sticla1 conţine otrava. Şi aşa mai departe.

Dacă avem 10 prizonieri la dispoziţie putem testa 2^10=1024 de sticle. Noi având de testat doar 1000 de sticle, se pot face şi optimizările de care a pomenit AdiJapan, pentru a sacrifica maximum 8 prizonieri.
0 0
ok, o numerotare de la 0 a condamnatilor ar ajuta in economia calculelor, adica condamnatul N nu bea din primele 2^N .....,
0 0
Și eu prefer numerotarea de la 0, atît la sticle cît și la condamnați, ca să nu fie nevoie de adăugarea unor -1 sau +1 în calcule.
1 0
As adauga ca, pentru o simplificare a calculelor de la trecerea din binar in zecimal ,am putea face urmatorul lucru: vom atribui fiecarui condamnat numarul primei sticle din care el o sa bea (numerotam sticlele incepand cu 0). Condamnatului 0 o sa-i atribuim nr. 1, cond. 1 nr.2, cond.2 nr 4, lui 3 pe 8, lui 4 pe 16, lui 5 pe 32, lui 6 pe 64, lui 7 pe 128, lui 8 pe 256 si lui 9 pe 512. Ca sa aflam sticla cu otrava , vom suma numerele atribuite condamnatilor care au murit. In exemplul de mai sus mor condamnatii 0,1,2,5,6,7,8 si 9. Facand suma numerelor atribuite lor, vom avea: 1+2+4+32+64+128+256+512=999 adica sticla cu otrava.
0 plusuri 1 minus

"care survine la 10-20 de ore după consum"....daca surivine la 10 avem un minim de unu...daca survine la 20...avem o problema

Novice (119 puncte)
2 0
Răspunsurile sînt răspunsuri. Comentariile sînt comentarii.
0 0
Ok. Atunci să fie 20. Dar pe varianta cu 10 cum de avem un minim de 1?
1 0
Dacă moartea survine sigur după maximum 10 ore, atunci putem rezolva problema cu 9 condamnați. Dar enunțul spune „10-20 de ore”, deci trebuie neapărat să așteptăm cel puțin 20 de ore pînă ne socotim morții. Atunci nu putem face decît o singură încercare în 24 de ore. Mie enunțul mi se pare bun așa cum e.
0 plusuri 2 minusuri
In scenariu se mentioneaza si cei 1000 de sclavi. De ce se mentioneaza daca ei nu pot fi folositi? Ca ar fi simplu, pui cate un sclav sa bea din cate o sticla (1000 de sticle - 1000 de sclavi) si unul o sa moara.

Oare pot fi acesti sclavi folositi altfel pentru descoperirea sticlei cu otrava ?
Experimentat (3.6k puncte)
1 0
Pai nu. Ideea e să nu folosim sclavi pe post de degustători. Eventual la manevrarea numărului impresionant de sticle ar putea fi utili. Dar în principiu  ai dreptate. Se poate face abstracţie de acea parte a enunţului.
0 0
Deci am dreptate. Ai pus parti inutile in enunt, asa-i ?
1 0
Ideea era că, deşi are la dispoziţie cei 1000 de sclavi şi ar putea apela la o metodă "prin forţă brută" de a identifica otrava, regele caută o soluţie care să nu mai provoace şi alte morţi în afara celor ale prizonierilor a căror soartă era deja pecetluită. E o poveste cu un rege. Atât.
1 0
Sclavii erau o avere, mai ceva decît sînt astăzi vacile sau caii țăranilor. Așa că nu se punea problema să sacrifici un sclav în locul a 10 prizonieri care oricum erau condamnați la moarte.

Apoi nu trebuie să ne jenăm să ignorăm părți din enunț dacă problema se poate rezolva și fără ele. De altfel lumea reală a matematicii e plină de așa ceva.
0 0
sa presupunem ca asezam sticlele intr un cub cu latura de 10. acest cub are 10 planuri orizontale (x1, x2, ....x10), 10 verticale (y1,....y10) si alte 10 verticale (z1, ....z10). prizonierul nr. 1 bea din toate sticlele din x1, y1, z1. prizonierul 2 bea din x2,y2,z2, etc.sticla otravita se va afla la intersectia celor 3 axe. deci pot sa moara maxim 3 prizonieri (1, 2 sau 3) !!!
0 0
3 prizonieri înseamnă 3 biți de informație, deci identificarea a o sticlă din cel mult 8.

Apoi nu înțeleg cum ați distribuit prizonierii. Numărul 1 bea din planele x1, y1, z1, numărul 2 din x2, y2, z2 etc., dar cine mai bea din planele x4, y7 și celelalte? Cum v-au ieșit doar 3 cînd fiecare orientare are 10 plane?
0 0
de unde ati gasit 10 plane? nu sunt 3 intr un cub?

din x4 bea prizonierul nr 4care mai bea si din y4 si z4; la fel si din y7 bea prizonierul nr 7!
0 0
nu am zis ca foloseste doar 3 prizonieri ci ca mor maxim 3 din 10 pe care ii foloseste!
0 0
imi cer scuze este vorba de 10 plane pe fiecare orientare. primul prizonier bea din primul plan de pe fiecare orientare, al 2-lea din al 2 -lea plan de pe fiecare orientare s.a.m.d
1 0
Acum am înțeles, dar soluția dumneavoastră e tot greșită. Să zicem că mor prizonierii 1 și 2. Care e sticla cu vin otrăvit? Nu veți ști, pentru că există șase sticle care îi pot omorî pe prizonierii 1 și 2 fără să-i omoare pe ceilalți. Și anume e vorba de sticlele aflate în cub la adresele (x,y,z) următoare: (1,1,2), (1,2,1), (1,2,2), (2,1,1), (2,1,2), (2,2,1). La fel se întîmplă dacă mor alți doi prizonieri.

Dacă mor trei prizonieri situația e la fel de gravă, adică sînt tot șase sticle suspecte din care însă nu puteți ști sigur care e cea otrăvită. De exemplu dacă mor prizonierii 1, 2 și 3 otrava e în una din sticlele aflate în cub la adresele: (1,2,3), (1,3,2), (2,1,3), (2,3,1), (3,1,2), (3,2,1).

Soluția e bună numai întîmplător, dacă moare un singur prizonier, adică dacă sticla otrăvită se întîmplă să se afle pe diagonala cubului. De exemplu dacă moare prizonierul 7 știm sigur că vinovată e sticla (7,7,7).

Dar o soluție care funcționează numai parțial nu e soluție.
1 0
din nou aveti dreptate d-l Adi !

multumesc pt lamuriri !
...