Este anul 2015. Cu ocazia zilei

, fondatorii ProDidactica au decis sa faca o mare petrecere la care sa invite pe toti utilizatorii ProDidactica. Cand mai este doar o ora pana la sosirea invitatilor, responsabilul SRI cu protejarea invatamantului romanesc aduce vestea ca niste teroristi au pus otrava in unul din cele 10 butoaie de vin pregatite pentru petrecere. Singura informatie suplimentara este ca otrava actioneaza in o ora asupra oricarei vietuitoare.

In afara de aceasta informatie, responsabilul SRI a gasit si adus 4 soareci de laborator. Folosind acesti soareci (rugam Asociatia pentru Protectia Animalelor sa inteleaga ca soarecii se jertfesc pe altarul cunoasterii) determinati care este butoiul cu vinul otravit.

Comentariu: Pentru cei care nu stiu inca, ziua

este 14 martie. Explicatia tine de modul cum se scrie data in unele tari
luna.ziua
adica in cazul de fata 3.14. Luand si ultimele doua cifre ale anului 2015 (si uitand sa punem .) vom avea chiar 3.1415

Petrecerea poate incepe la ora stabilita, dar s-ar putea sa moara unii dintre soricei. Dar , asta le este menirea, nu?

Vom da soriceilor sa bea niste cokteiluri de vin astfel:

S1....din butoaiele: {2,3,4,5,6,7}
S2.... din butoaiele: {5,6,7,8,9,10}.
S3.....din butoaiele: {3,6,9}
S4......din butoaiele: {4,7,10}.

1.- daca nu moare nici unul dintre soriceii S1 si S2, otrava e in butoiul 1.
2.- daca S1 moare si S2 nu, otrava e in unul din butoaiele 2,3,4
3.- daca mor ambii (S1 si S2), otrava e in unul din butoaiele 5,6,7

4.- daca moare S2 si S1 nu, otrava e in unul din butoaiele 8,9,10

6. In cazul 2. - a) Daca S3 si S4 nu mor, otrava e in butoiul 2
b) daca S3 moare si S4 nu, otrava e in butoiul 3
c) daca S4 moare si S3 nu, otrava e in butoiul 4

5. In cazul 3. - a) daca S3 si S4 traiesc, otrava e in butoiul 5
b) daca S3 moare si S4 nu, otrava e in butoiul 6
c) daca S4 moare si S3 nu, otrava e in butoiul 7

7. In cazul 4. - a) Daca S3 si S4 nu mor, otrava e in butoiul 8
b) daca S3 moare si S4 nu, otrava e in butoiul 9
c) daca S4 moare si S3 nu, otrava e in butoiul 10

Aceeasi problema pentru N soareci, T ore, determinati nr maxim de butoaie B care pot fi testate. (deduceti o formula)

Solutia de mai sus nu e unica. Se pote calcula usor numarul de solutii ale acestei probleme. Poate o face cineva!

O rezolvare mai scolareasca ar fi urmatoarea:
Enunt generalizat: ...ca mai sus doar ca se dau n butoaie, si se cere numarul de soricei necesari, si " secretul" folosirii lor, pentru depistarea butoiului otravit intr-o ora.

Pentru n butoaie, avem nevoie de k soricei, unde

.
II vom folosi astfel:
- Numerotam butoaiele si soriceii.
- Asociez fiecarui butoi, numarul sau scris in baza 2
- Dau sa bea fiecarui soricel un amestec din butoaiele ce au cifra 1 pe pozitia cu numarul soricelului, numarand pozitiile de la dreapta la stanga. (deci daca numarul are cifra 1 pe pozitia 3, atunci si soricelul 3 va bea din el)
- Cu soriceii morti, considerandu-i cifra 1 pe pozitia indicata de numarul primit de ei la numerotare, formez un numar in baza 2, punand pe pozitiile goale cifra 0.
- numarul format indica numarul butoiului otravit.

Exemplu:
16 butoaie, 4 soricei. Daca otrava ar fi in butoiul 12, pentru ca 12 in baza 2 se scrie 1100 inseamna ca din acest butoi au baut soriceii 3 si 4. Deoarece scrierea este unica, doar din acest butoi au baut numai soriceii 3 si 4.(in momentul in care am constatat ca au murit soriceii cu numeele 3 si 4, scriu numarul in baza 2, care are cifrele 1 pe pozitiile 3 si 4 si cifra 0 pe celelalte pozitii. Numarul astfel obtinut da numarul butoiului in baza 2)
Observatie: Daca nu moare nici un soricel, butoiul otravit este cel cu numarul 16, doar el are ultimile 4 cifre 0.

La aceeasi concluzie am ajuns si eu
n soricei verifica maxim 2^n butoaie

un butoi il lasam liber
un butoi soricelului 1, altul lui 2, 3, 4, apoi 12,13,14,23,24,34,123,124,134,,234,1234.

Dar puneam problema altfel:
Aveam la dispozitie mai multe ore, nu doar una. Cum deducem numarul maxim de butoaie care pot fi verificate in cele T ore?

In ultima ora stiu ca cei n soricei pot verifica 2^n butoaie. Asta inseamna ca in penultima ora imi permit sa las libere maxim 2^n butoaie. Tinand cont ca in acest pas soriceii verifica doar 31 de butoaie (nu mai exista 1 sg butoi liber, ci 32, deci nu stim starea sa), in 2 ore oriceii verifica 2*2^n - 1 butoaie?
Iar in T ore, T*2^n - (T-1) butoaie ?

[Citat] In ultima ora stiu ca cei n soricei pot verifica 2^n butoaie. Asta inseamna ca in penultima ora imi permit sa las libere maxim 2^n butoaie. Tinand cont ca in acest pas soriceii verifica doar 31 de butoaie (nu mai exista 1 sg butoi liber, ci 32, deci nu stim starea sa), in 2 ore oriceii verifica 2*2^n - 1 butoaie? Iar in T ore, T*2^n - (T-1) butoaie ?

.... daca crezi ca dupa ce au murit, niste soricei ar putea fi reactivati in functie....

[Citat] La aceeasi concluzie am ajuns si eu n soricei verifica maxim 2^n butoaie un butoi il lasam liber un butoi soricelului 1, altul lui 2, 3, 4, apoi 12,13,14,23,24,34,123,124,134,,234,1234.

Nu stiu la ce concluzie ai ajuns tu, dar, din cate inteleg, e foarte departe de adevar!

Si pentru ca tot doreai o formula, poate ne-o arati si noua, ca, pe mine cel putin ma depaseste! Si asta nu e tot, sunt convins ca nu ai de unde scoate asa ceva!

revin asupra rationamentului
nici cel initial nu era gresit, dar avea eficienta scazuta

stim ca n soricei verifica 2^n butoaie intr-o zi
pentru exemplificare, luam n=4 si t=2 (ore)

trebuie sa ma sigur ca dupa prima ora voi ramane cu un numar suficient de soricei ca sa verifice butoaiele ramase

de aceea:
0:las 16 libere (nu moare nimeni, le verifica cei 4 soricei ramasi)
1,2,3,4: fiecare bea cate 8, deoarece daca acesta moare, cei 3 ramasi in viata vor verifica printre butoaiele mortului ; 2^3=8
12,13,14,...,34: fiecare pereche de cate 2 bea cate 4 butoaie, pentru ca cei 2 ramasi sa verifice cele 4 butoaie, in caz ca primii doi mor
123,...,234: fiecare pereche de cate 3 => 2 butoaie, ultimul soricel putand verifica cele 2 butoaie ramase
1234: 1 singur butoi pentru toti

astfel avem // C{x}{y}=combinari de x luate cate y

16+C{4}{1}*8 + C{4}{2}*4 + C{4}{3}*2 + C{4}{4}*1 = 16+4*8+6*4+4*2+1=16+32+24+8+1 = 81

La faza asta doar am demonstrat prin inductie ca numarul de butoaie verificate in 2 ore de n slugi este 3^n. Si apoi pentru t ore, tot prin inductie, avem (t+1)^n nr maxim de butoaie verificate.

In primul rationament consideram ca nu trebuie sa moara nimeni, de aceea iesea un numar mai mic de butoaie. Era doar o intrebare care mi-o puneam.