Problema este destul de simplă şi am primit multe rezolvări corecte. De la
SzaboZoltan, Aurel Ionescu, Viorel Manta, Ady Nicolae, Radu Grama, Claudiu Emil Man, Marius Alecsandru, Angela Sandu.
Toate au mers pe varianta următoare (Ady Nicolae):
Vom împărți cele 68 de monede în 34 de perechi şi vom face 34 de cântăriri. În urma acestora vom avea 34 de monede mai grele şi 34 de monede mai uşoare.
Definirea celei mai grele monede:
Vom lua cele 34 de monede mai grele şi le vom împărți în 17 perechi. Vom realiza cele 17 cântăriri şi vom avea 17 monede mai grele. Cu acestea vom lucra în continuare.
Vom împărți aceste 17 monede mai grele în 8 perechi, iar moneda în plus (17-1):2=8 o vom păstra.
Vom realiza cele 8 cântăriri şi vom păstra cele mai grele 8 monede.
Vom împărți aceste 8 monede în 4 perechi şi vom păstra cele mai grele 4 monede.
La fel, vom împărți cele 4 monede în 2 perechi şi vom păstra cele mai grele 2 monede.
Apoi, vom cântări cele două monede şi o vom păstra pe cea mai grea.
Ultima cântărire o vom face între aceasta şi moneda păstrată mai sus.
Definirea celei mai uşoare monede se va face analog, începând cu cele mai uşoare 34 de monede şi păstrând de fiecare data cele mai uşoare monede.
Numărul necesar de cântăriri este:
34 + 2 * (17 + 8 + 4 + 2 + 1 + 1) = 100
Am mai reţinut:
Cele două grupe cu 34 de monede candidate pentru moneda uşoară respectiv moneda grea se pot rezolva optim în 33 de măsurări oricum am alege metoda.
Dacă le luăm liniar prima cu a doua, apoi moneda mai uşoară (mai grea) cu a treia, apoi moneda mai uşoară (mai grea)cu a patra monedă, ..., apoi moneda mai uşoară (mai grea) cu ultima monedă, rezolvăm problema în 33 de paşi.
Dacă grupăm monedele în 17 grupe şi păstrăm monedele mai uşoare (grele) , apoi formăm 8 grupe şi păstrăm monedele mai uşoare (mai grele) o monedă rămâne neverificată, apoi 4 grupe, apoi 2 grupe, apoi 1 grupă, moneda astfel obţinută se compară cu moneda încă neverificată şi se obţin 17+8+4+2+1+1=33 de cântăriri.
Orice altă modalitate de grupare a monedelor, prin care după cântărire se elimină moneda "greşită" şi se păstrează moneda "valida" (mai grea sau mai uşoară) va rezulta 33 de cântăriri, întrucât macheta asociată măsurărilor este un arbore, în care nodurile sunt monedele iar muchiile sunt măsurările efective.
Acest arbore are 34 de noduri, în consecinţă are 33 de muchii. Adică orice modalitate de măsurare se va finaliza în exact 33 de paşi.
Sa ne imaginam ca suntem la un turneu de fotbal si monedele sunt echipele iar balanta terenul de fotbal, si trebuie sa aflam campioana si echipa care retrogradeaza.
Prima data joaca toate echipele cate un meci fiecare si se impart in doua grupe grupa campioanei si grupa retrogradarii. deci 34 partide
In grupa campioanei se mai joaca 17 meciuri apoi 8, 4 2 si 1 deci dupa 33 de meciuri se stabileste campioana la fel si cea care retrogradeaza in total 100 de meciuri
În general, pentru a rezolva problema având 2n monede sunt necesare 3n−2 cântăriri.
Monedele se împart la inceput în n perechi şi se efectuează n căntăriri, care duc la formarea a două mulţimi G1 (unde se află moneda mai grea) şi G2 (unde este moneda cea mai uşoară).
În continuare, în fiecare mulţime o cântărire duce la eliminarea unei monede. Pentru că sunt n monede, n-1 cântăriri sunt suficiente (şi necesare) pentru a afla cea mai grea monedă din G1.
Similar, n-1 cântăriri vor allege cea mai uşoară monedă din G2.
Deci, in total vor fi n +(n-1) + (n-1) = 3n-2 cântăriri.
Logic
