vineri, 8 aprilie 2011

Problema cu 12 bile - rezolvare

Cred ca este cea mai grea problema pe care am facut-o vreodata. Multumesc Lucian si pentru problema si pentru indicii de abordare.

Cerinta este in felul urmator: "Se dau 12 bile din care 11 identice si una cu greutate diferita (nu se stie daca e mai usoara sau mai grea). Folosind o balanta si doar 3 cantariri sa se determine care este bila si in ce fel este ea diferita (mai usoara sau mai grea)".

Pentru usurinta am numerotat bilele de la 1 la 12. Si le-am separat in 3 grupe de cate 4 bile: 1-4, 5-8, 9-12.

1. Prima cantarire 1-4 vs 5-8 Daca balanta este egala atunci rezulta varianta 1, daca balanta este inegala atunci rezulta varianta 2.

Varianta 1 Daca balanta 1-4 vs 5-8 a ramas egala inseamna ca bila cu probleme e in gruparea 9-12 si primele 8 vor fi folosite ca stas
Se sparge gruparea 9-12 in: 9, 10, 11 pe o parte si 12 de una singura.
2a. Comparam 9-11 vs 3 bile stas obtinute din prima masuratoare. Daca balanta ramane pe loc inseamna ca bila 12 este cu probleme.
3a. Din a 3-a masuratoarea cu una din bilele stas vom sti si daca bila 12 este mai usoara sau mai grea. Daca se duce in jos fata de una stas e grea, daca se duce in sus e usoara.
2b. Comparam 9-11 vs 3 bile stas obtinute din prima masuratoare. Si vedem ca balanta se inclina intr-o parte, in acest moment stim daca bila cu probleme aflata in 9-11 este mai usoara sau mai grea decat bilele stas.
3b. Spargem grupul 9-11 in 2 +1 bile. Comparam oricare 2 intre ele, si in functie de cum se inclina balanta, tinem cont si de concluzia de la pasul anterior, astfel putem spune care bila are propietatea de a fi mai usoara sau mai grea. Daca balanta a ramas pe loc stim ca bila care nu a fost masurata este mai usoara sau mai grea (dupa cum am aflat la pasul anterior).
Deci, daca stiam de la pasul anterior ca bila este grea, punand 2 bile in balanta cea care trage in jos e grea, daca stiam ca bila este usoara cea care se duce in sus este usoara.

Varianta 2 Balanta cu 1-4 vs 5-8 s-a inclinat intr-o parte. Trebuie tinut minte in ce parte s-a inclinat! Inseamna ca in 1-8 e bila cu probleme si ca 9-12 pot fi folosite ca stas.
Fac o permutare in 1-8 astfel: 1 2 3 5 vs 4 x x x (am interschimbat 4 cu 5 si am pus 3 bile stas in partea dreapta).
2a. Daca balanta 1 2 3 5 vs 4 x x x este in echilibru inseamna ca si 1-5 erau bile stas si ca bila cu probleme se afla in 6, 7, 8. Asta mai inseamna si ca din prima cantarire am aflat cum sunt 6,7,8 fata de bilele stas (mai usoare sau mai grele)
3a. Spargem grupul 6, 7, 8 in 2 +1 bile. Comparam oricare 2 intre ele, si in functie de cum se inclina balanta, tinem cont si de concluzia de la pasul anterior, astfel putem spune care bila are propietatea de a fi mai usoara sau mai grea. Daca balanta a ramas pe loc stim ca bila care nu a fost masurata este mai usoara sau mai grea (dupa cum am aflat la pasul anterior).
2b. Daca balanta 1 2 3 5 vs 4 x x x este in dezechilibru , inseamna ca in 1-5 se afla bila cu probleme si ca restul pot fi folosite ca stas.
3b1. Daca dupa permutare balanta a aratat la fel (a inclinat in aceeasi directie) ca la prima masuratoare inseamna ca bila cu probleme e in 1-3 si in functie de inclinare stim ca este mai usoara sau mai grea fata de bilele stas.
Spargem grupul 1, 2, 3 in 2 +1 bile. Comparam oricare 2 intre ele, si in functie de cum se inclina balanta, tinem cont si de concluzia de la pasul anterior, astfel putem spune care bila are propietatea de a fi mai usoara sau mai grea. Daca balanta a ramas pe loc stim ca bila care nu a fost masurata este mai usoara sau mai grea (dupa cum am aflat la pasul anterior).
3b2. Daca dupa permutare balanta si-a inversat directia inseamna ca bila cu probleme este 4 sau 5.
Comparam oricare din cele doua (sa zicem 4 de exemplu) cu una stas si aflam daca este mai usoara sau mai grea decat una stas, in cazul in care este egalitate inseamna ca bila care a ramas nemasurata este cea cu probleme si in functie de cum a aratat balanta la prima masuratoare vom sti daca a fost mai grea sau mai usoara decat una stas.
3b1 si 3b2 au fost abordari diferite in functie de cum a aratat balanta la pasul anterior.

Acest algoritm trateaza toate cele 12 bile! Practic la fiecare masuratoarea se deschid 2 ramuri. Masuratoarea 1 deschide 2 ramuri. Masuratoarea 2 deschide 4 ramuri (cate 2 pentru fiecare 2 anterioare).

5 comentarii:

Anonim spunea...

Hehe, acum v-a ramas de rezolvat problema cu snururile si cele 45 minute

fly spunea...

Salut, foarte tare blogul, tine-o tot asa. Succes

Eugen Popp spunea...

@fly Multumesc frumos !
@Raluca: saptamana viitoare intra problema cu snururile :)

muresan dani spunea...

Aceasta e o problema care mi-a mancat multe ore de somn acum vreo 15 ani si mi-am adus aminte de ea. Am avut o mare satisfactie rezolvand-o. Ii voi da un copy textului. Mersi

Sorin Calinescu spunea...

Mai grea ca această problemă a fost numai cubul Rubik.Se împart cele 12 monede in 3 grupe de cate 4. La prima cåntărire se pun două grupe de 4 monede pe talerele balanței. CAZUL I. Talere se echilibrează, deci monedele
sunt bune. Celelalte 4 sunt suspecte (S) deoarece conțin moneda falsă. La cântărirea II, lăm 3 monede suspecte şi le compară cu 3 bune (B). Dacă balanta se echilibrează, înseamnă că cele 3 monede sunt bune. A patra monedă ramasă deoparte este falsă. O comparăm cu una bună pentru a vedea dacă e mai uşoară sau mai grea. Dacă balanța nu s-a echilibrat moneda falsă e printre ele şi am aflat cä e mai uşoară sau mai grea. Luăm douä dintre ele şi le comparăm. Dacă balanța se echilibrează e falsă a treia monedă, fiind mai usoară sau mai grea ca talerul de pe care provine. Dacă nu se echilibrează va fi falsă cea care e mai grea sau mai uşoară ca talerul de pe care provin.
CAZUL II. La prima cantărire, balanța s-a dezechilibrat. Rezultă 8 monede suspecte şi
4 bune.Cele suspecte sunt 4G (grele) şi 4U (uşoare).La a doua cântărire, punem pe fiecare taler câte 2G şi 1U. Rămân deoparte 2U. Dacă balanța se echilibrează, moneda falsă va fi una dintre cele 2U. La a treia cântărire le comparăm şi care e mai uşoară e falsă.
Dacä balanța nu se echilibrează, la cântărirea III, comparăm între ele cele 2 monede 2G de pe talerul mai greu. Care e mai grea e falsä. Dacă balanța se echilibrează va fi falsă moneda 1U de pe talerul mai uşor
Dacă inversăm G cu U, obținem aceleaşi rezultate dar in altă ordine.