Generalizarea problemei lui Naruto (own)

[Marcelina Popa]

Sunt 10 saci cu monede din aur. Intr-unul din ei sunt monede false, iar in ceilalti saci monede bune. Monedele bune au cate 10 grame, iar cele false cate 9 grame. Dispunem de un cantar foarte precis, care poate masura si greutati foarte mici, de ordinul gramelor.

Cum putem face ca, dintr-o singura cantarire, sa aflam in care sac sunt monedele false?

Va propun o problema mai generala (are solutie, sa stiti):

Sunt 10 saci cu monede din aur. Unii dintre ei contin monede false, altii monede bune. Niciun sac nu contine monede amestecate - bune si false. Monedele bune au cate 10 grame, iar cele false cate 9 grame. Dispunem de un cantar foarte precis, care poate masura si greutati foarte mici, de ordinul gramelor.

Cum putem face ca, dintr-o singura cantarire, sa aflam in care saci sunt monedele false?

Problema se poate generaliza si mai tare, considerand n saci in loc de 10 saci. Ramane si atunci posibila determinarea printr-o singura cantarire a sacilor cu monede false.

[naruto]

In problema mea se rezolva asa: luam 1 moneda din primul sac, 2 din sacul al doilea ...... 10 monede din sacul a zecelea. Se pun toate pe cantar. Daca toate sunt egale trebuie sa iasa greutatea 10(1+2+.....+10) = 550 grame. Dar o sa fie mai putin, deoarece unele monede sunt mai mici. Daca avem 554 de grame => lipsesc 6 grame => de la 6 monede false => sacul 6 are monede false.

Dar cum se face problema dvs? Nu cred ca se poate . Daca lipsesc 6 grame de la 6 monede, ele pot sa vina din mai multi saci si nu stim din care.

[Marcelina Popa]

Se poate rezolva si problema mea. Luam monedele in felul urmator:

- \( 1 \) moneda din sacul 1;
- \( 2 \) monede din sacul 2;
- \( 2^2=4 \) monede din sacul 3;
- \( 2^3=8 \) monede din sacul 4;
- \( 2^4=16 \) monede din sacul 5;
- \( 2^5=32 \) monede din sacul 6;
....
- \( 2^9=512 \) monede din sacul 10.

In total sunt \( 2^{10}-1=1023 \) monede. Daca toate monedele ar fi bune, ar trebui sa cantareasca 10230 grame. Sa zicem ca ele cantaresc numai 10181 grame. Inseamna ca lipsesc 49 de grame, deci sunt 49 de monede false. Acestea provin din mai multi saci. Trebuie sa scriem numarul 49 ca suma de puteri diferite ale lui 2.

\( 49=32+16+1=2^5+2^4+1 \)

32 de monede provin din sacul 6, 16 monede din sacul 5 si 1 moneda din sacul 1. Inseamna ca sacii cu monede false sunt sacii 1, 5 si 6.

Acuma, se pune intrebarea: nu-l puteam scrie pe 49 ca suma de puteri diferite ale lui 2 si in alt mod? Nu puteam. Scrierea unui numar ca suma de puteri diferite ale lui 2 inseamna, de fapt, scrierea acelui numar in baza 2. Iar scrierea unui numar natural intr-o baza de numeratie data este unica.

Revenind la exemplul nostru:
\( 49=110001_{(2)}=2^5+2^4+1 \).
Alta scriere a lui 49 in baza 2 nu exista.

Tu te intrebai ce se intampla daca ne dam seama ca 6 monede sunt false. Pai, ia sa vedem, ce se intampla? Care ar fi sacii cu monede false in cazul asta?



P.S. Problema e cam ciudata, fiindca nu stiu pe ce cantar de precizie se pot pune 10230 de monede de cate 1 gram . O putem face mai normala daca lasam, sa zicem, 5 saci in loc de 10.

[Marcelina Popa]

Mi-am pus intrebarea daca se puteau alege si alte numere in loc de puterile lui 2. Nu se putea. La intrebarea asta raspunde o problema pe care am propus-o mai demult AICI, rezolvata de Laurian Filip.

[naruto]

Pentru 6 monede false: 6=4+2. 4 monede vin din sacul 3 si 2 monede vin din sacul 1.
E bine?

[Marcelina Popa]

Aproape bine. N-ai fost atent: 2 monede vin din sacul 2. De fapt regula ar fi: \( 2^k \) monede vin din sacul \( k+1 \).

[naruto]

Ah...da