teste haioase

7)Haidem sa punem problema altfel:

In maxim cate monezi pot sa caut moneda falsa daca pot sa fac n masuratori (cantariri) si stiu sau nu stiu daca acea moneda e mai usoara sau mai grea decat celelalte. S-o numim P(s/n,n), adica P(n,3) in cazul nostru.

Sa rezolvam P(s,1): raspunsul e 3 deoarece comparand 2 monezi pot obtine 3 raspunsuri, sau =. Daca obtin =, moneda cautata (falsa) e cea care nu a fost cantarita.

P(s,2)=9 : Impart in 3 gramezi in care cel putin 2 sa fie egale (pt. cantarire). Printr-o masuratoare aflu in care gramada este moneda. Pt. ca mai am dreptul la o masuratoare, in gramada descoperita sunt P(s,1) monezi, oricare gramada as obtine, astfel P(s,2)=3*P(s,1)

P(s,n) = 3*P(s,n-1) = 3^n = 3 la puterea n

Notez: g=grea, u=usoara, n=normala, f=falsa, gf=(grea si falsa)

P(n,1) nu are solutie decat daca ma poate imprumuta cineva cu o moneda normala si atunci P´(n,1)=1

P´(n,2)=4 daca as avea suficiente monezi normale pt. test : Am 2 grupe necunoscute si una normala, compar gr.1 cu cele normale si din (gr.1, gr.2) obtin (gf,n) si =(n,f) deci gr.1 are P(s,1)=3 si gr.2 are P´(n,1)=1. P(s,1)+P´(n,1)=3+1=4

P´(n,n)=P(s,n-1)+P´(n,n-1)=3^(n-1)+...+9+3+1=(3^n-1)/2

P(n,2)=3 : Am m1, m2 si m3. Compar m1 cu m2 si pot avea (g,u,n), =(n,n,f). Dc. < sau > compar g cu n si pot avea din (g,n,u): >(gf,n,n) sau =(n,n,uf). Dc. am = compar f cu n si (f,n,n) devine: (gf,n,n)

Se observa ca prima masuratoare are 3 variante dar a doua doar 2. Putem sa facem ceva ca sa aflam mai mult de la a doua masuratoare?

P(n,3)=9? : Impart in 3 gramezi si dupa ce repet rationamentul anterior pt.3 grupe in loc de 3 unitati obtin dupa 2 masuratori o grupa cu P(s,1) monezi deci P(n,3)=3*P(s,1)=9.

P(n,3)=10? : Am 3 grupe. Masor cele 3 grupe si dc. la prima am =(n,n,f), gr.3 are P´(n,2)=4 variante deci 2*P(s,1)+P´(n,2)=6+4=10. Deci am facut ca a doua intrebare dc. prima era = sa ne ofere 3 variante.

Cum facem cu a 2-a masuratoare dc. prima este < sau >? Primele 2 gr. au acelasi nr. de monezi altfel nu le putem compara. Le impartim si pe acestea in cate 2 dupa prima masuratoare si avem u1,u2,g1,g2,n1 unde ca nr. u1=g1=n1 si u2=g2. Compar g1+u2 cu n1+g2 : Dc. in greutate u2=g2=n comparatia ar fi intre g1 si n1 ca mai inainte cu variantele > si =. Varianta < apare doar daca u2(gf1+n2, n1+n2, n1), =(n1+n2, n1+n2, uf1) sau si = aflam g1=u1=P(s,1). Din < stim doar ca u2(n2,gf2) sau =(uf2,n2). Epuizand toate cantaririle => g2=u2=P(s,0)=1

Deci g=u=3+1 si din paragraful anterior a 3-a grupa are tot 4 monezi astfel P(n,3)=12

~~~~~~~~~~

Generalizand, dc. am 2 gramezi egale numeric, in care stiu ca una e mai grea decat cealalta si suficiente monezi martor (normale, pt. test), notez P½(n,n) nr maxim de monezi pe care le poate avea una din grupe ca dupa n masuratori sa stiu in care grupa e cea falsa si care e. Repetand algoritmul de mai sus obtin g1=u1=P(s,n-1) si g2=u2=P½(n,n-1), deci P½(n,n)=P(s,n-1)+P½(n,n-1)=3^(n-1)+...+9+3+1=(3^n-1)/2

P(n,n)=2*P½(n,n-1)+P´(n,n-1)=3*(3^(n-1)-1)/2