Problema de les 12 monedes

De Viquipèdia
Dreceres ràpides: navegació, cerca

En el "problema de les 12 monedes" hem de trobar entre 12 monedes quina és la falsa, utilitzant només 3 pesades de balança. A més, saber si pesa més o menys que les altres.

En la versió de 12 monedes hauria aparegut en 1945, sense saber la seua procedència.

El problema admet una generalització immediata augmentant el nombre de monedes i pesades: Quin és el màxim de monedes per a "n" pesades?

Oferim ací dos solucions del problema.

1ª Solució[modifica | modifica el codi]

La primera solució, de fàcil generalització amb més pesades, s'explica a continuació:

La 1ª pesada la realitzem així:

Braç dret Braç esquerre Taula 
1 5 9
2,3,4 6,7,8 10,11,12


En la 2ª pesada, rotem els grups de tres monedes així:

Braç dret Braç esquerre Taula 
1 5 9
10,11,12 2,3,4 6,7,8 
  • Si la inclinació de la balança no canvia, la moneda falsa està entre les tres que no hem rotat: 1, 5, 9.
  • Si la inclinació de la balança canvia, podem identificar quin grup dels que hem rotat té la moneda falsa.


I ens queda la 3ª pesada per identificar d'entre tres monedes quina és la falsa: Només hem de pesar dos d'elles, doncs ja tenim informació d'anteriors pesades i podem així identificar la moneda falsa.

Generalització[modifica | modifica el codi]

La clau de la generalització consisteix en que podem abordar un grup
de 3^n monedes amb "n" pesades, si ja ha estat prèviament pesat:
Formem 3 grups, pesem 2 d'ells i identifiquem el grup problemàtic.
I repetim el procés fins a obtindre una moneda.

Aquest problema admet una fàcil generalització per a 4 pesades, afegint 3 noves files de 9 monedes. Si abans pesavem grups de 4 monedes: 1+3, ara en pesem grups de 13 monedes: 1+3+9.

I ara rotarem els grups de 9 monedes en la 2ª pesada.

  • Si canvia la inclinació identifiquem el grup de 9 monedes que té la falsa.
  • Si no canvia la inclinació, retirem les files de 9 monedes i estem en la mateixa situació del problema de les 12 monedes.

Amb 5 pesades, afegim 3 noves files de 27 monedes: cadascun dels tres grups tindrà 40 monedes: 1+3+9+27. I procedim anàlogament al cas anterior.

Aquest és l'esquema de la solució general:

3 monedes en 2 pesades
12 monedes en 3 pesades: 3 + 3^2 = 12
39 monedes en 4 pesades: 12 + 3^3 = 39
120 monedes en 5 pesades: 39 + 3^4 = 120
363 monedes en 6 pesades: 120 + 3^5 = 363
120 monedes en 7 pesades: 363 + 3^6 = 1092

(3^n-3)/2 monedes, amb "n" pesades.

Quin és el màxim de monedes per a "n" pesades?[modifica | modifica el codi]

Un problema més difícil és demostrar quin és el màxim de monedes, i per això utilitzarem la 2ª solució. No obstant, oferim un argument intuïtiu:

Per a (n+1) pesades analitzem el màxim de monedes, entre balança i taula:

Un màxim a la balança és 3^n monedes, doncs després de la 1ª inclinació de balança ens queden n pesades i 3^n és el màxim de monedes. Però com que ha de ser parell (dos braços), hi haurà 3^n-1 com a màxim.

Vegem el màxim de monedes a la taula: si la moneda falsa està a la taula, hi a equilibri en la 1ª pesada i disposem de monedes "bones": Escullim 3^(n-1) monedes de la taula i les pesem amb altres tantes "bones", si està ací la moneda falsa podem trobar-la amb (n-1) pesades que ens queden; si hi ha equilibri repetim el procés amb 3^(n-2) monedes, amb (n-2) pesades que ens queden;...; si hi ha equilibri repetim el procés amb 3^2 monedas amb altres 9 "bones"; si hi ha equilibri repetim el procés amb 3^1 monedes amb altres 3 "bones"; i finalment, si hi ha equilibri pesem l'última moneda amb 1 "bona" per saber si pesa més o menys, amb l'última pesada que ens queda. Sumant totes las monedes de la taula que hem pesat, tenim una progressió geomètrica de raó 3:

S(n)= 1 + 3 + 9 +...+ 3^(n-1)

que, curiosament, coincideix amb la mitat del màxim de la balança, és a dir com cada braç de balança.

Finalment, sumant el màxim de la taula i la balança:

1+3+9+...+3^(n-1) + 3^n-1 = 3 + 9+ ...+ 3^(n-1) + 3^n

que coincideix amb l'obtinguda en la generalització.

2ª Solució[modifica | modifica el codi]

Vegem primer un mètode per a monedes "orientades" (procedents de la 1ª inclinació de balança):

  • Denotarem al grup de "n" monedes on s'ha decantat el braç de la balança com: (n+).
  • Denotarem al grup de "n" monedes on s'ha alçat el braç de la balança com: (n-).
Per a 3 monedes "orientades", la solució és pesar 2 monedes. 

Per al cas de 9 monedes "orientades":

Braç dret Braç esquerre Taula
(2+), (1-) (2+), (1-) 3 monedes

Segons s'incline la balança identifiquem el grup de 3 monedes on està la moneda falsa.

Anàlogament, si tenim 27 monedes "orientades" identifiquem un grup de 9 monedes:

Braç dret Braç esquerre Taula
(6+), (3-) (6+), (3-) 9 monedes 

I en general, per a 3^(n+2) monedes:

Braç dret Braç esquerre Taula

(2*3^n+), (3^n-) (2*3^n+), (3^n-) Monedes restants

En general, per a 3^n monedes "orientades" necessitem n pesades:

si 3 és el màxim per a 1 pesada, no podem excedir 3 grups de 3 monedes en 2 pesades; ni 3 grups de 9 monedes en 3 pesades;...etc.; per tant:

El màxim de monedes "orientades" amb n pesades és 3^n.

Vegem ara el procediment general:

Ara només queda veure com configurar la 1ª pesada.

Siga la successió A(n)= màxim de monedes per a "n" pesades.

Calculem A(n+1): màxim de monedes per a "n+1" pesades.

A la balança podem posar un màxim de 3^n; que és el màxim de monedes orientades amb les "n" pesades que tenim encara. Però com hem de pesar un nombre parell, restem 1:

Balança = 3^n - 1

I a la taula posem un màxim de A(n), però ara no tenim l'exigència de pesar un nombre parell, doncs tindrem monedes del hipotètic equilibri de la balança:

Taula = A(n) + 1

Calculem el total entre monedes de la balança i taula:

Total = Balança + Taula

A(n+1) = 3^n-1 + A(n)+1 = 3^n + A(n)

Per tant, A(n) té estructura de suma d'una progressió geomètrica de raó: r= 3.

El primer terme de la successió A(n) és:

A(2)= balança + taula = 2+1 = 3

doncs en la taula és evident que només podem posar 1 moneda, i en la balança ja hem argumentat que és 3^1-1=2.

A(3) = 3^2 + A(2) = 12; A(4) = 3^3 + A(3) = 39;
A(5) = 3^4 + A(4) = 120; A(6) = 3^5 + A(5)........ 
A(n+1) = 3+9+27+...+3^n = 3*(3^n-1)/2

Per tant A(n) = (3^n-3)/2. Com volíem demostrar.

Endemés, per ser A(n) suma de progressió geomètrica es compleix que cada braç i la taula tenen les mateixes monedes:

mesa = balança / 2 

A(n)+1 = (3^n-1)/2


Vegem un esquema dels primers termes, així com la configuració de la primera pesada para a cada cas.

PRIMERA PESADA

braç esquerre braç dret taula

2 pesades: 1 1 1 

3 pesades: 4 4 4 = A(2) + 1 

4 pesades: 13 13 13 = A(3) + 1

5 pesades: 40 40 40 = A(4) + 1

6 pesades: 121 121 121 = A(5) + 1

7 pesades: 364 364 364 = A(6) + 1

Veiem l'exemple de 12 monedes:

Braç dret Braç esquerre Taula
1,2,3,4 5,6,7,8 9,10,11,12

a) Si s'equilibra, ataquem les 4 monedes restants formant un grup de 3 monedes, doncs ara sí que podem pesar un nombre imparell a la balança:

Braç dret Braç esquerre Taula
9,10 11,1 12

b) I si s'inclina, tenim 8=3^2-1 monedes "orientades" i apliquem el mètode descrit per a monedes orientades:

Braç dret Braç esquerre Taula
1 2 5 3 4 6 7,8 
Si s'equilibra, està en el grup (7,8), evidentement.
Si s'inclina com la 1ª pesada, està en el grup (1,2,6). 
Si no, estarà en el grup (3,4,5).