Problema de les dotze monedes
El problema de les 12 monedes és un problema matemàtic al qual es demana trobar entre 12 monedes quina és la falsa, utilitzant només tres pesades de balança, i determinar, a més, si pesa més o menys que les altres.
El problema amb 12 monedes hauria aparegut en 1945 als Estats Units d'Amèrica, sense més detalls sobre la seva procedència. El problema admet una generalització quan s'augmenta el nombre de monedes i pesades i la qüestió esdevé aleshores: «quin és el màxim de monedes per a "n" pesades?[1] Hi ha dos solucions del problema.
1a solució
[modifica]La primera solució, de fàcil generalització amb més pesades, s'explica a continuació:
La 1a pesada es realitza així:
Braç dret Braç esquerre Taula 1 5 9 2,3,4 6,7,8 10,11,12
En la 2a pesada, es roten 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 han rotat: 1, 5, 9.
- Si la inclinació de la balança canvia, es pot identificar quin grup dels que han rotat té la moneda falsa.
- Queda la 3a pesada per identificar d'entre tres monedes quina és la falsa: Només s'ha de pesar dues d'elles, perquè ja hi ha informació d'anteriors pesades i es pot així identificar la moneda falsa.
Generalització
[modifica]La clau de la generalització consisteix que es pot abordar un grup de 3^n monedes amb "n" pesades, si ja ha estat prèviament pesat: Formar 3 grups, pesar 2 d'ells i identificar el grup problemàtic. I repetir el procés fins a obtindre una moneda.
Aquest problema admet una fàcil generalització per a 4 pesades en afegir 3 noves files de 9 monedes. Si abans es pesaven grups de 4 monedes: 1+3, ara se n'han de pesar grups de 13 monedes: 1+3+9 i rotar els grups de 9 monedes en la 2a pesada.
- Si canvia la inclinació es pot identificar el grup de 9 monedes que té la falsa.
- Si no canvia la inclinació, es poden retirar les files de 9 monedes i s'obté la mateixa situació del problema de les 12 monedes.
Amb 5 pesades, s'ha d'afegir 3 noves files de 27 monedes: cadascun dels tres grups tindrà 40 monedes: 1+3+9+27. Després s'ha de procedir 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]Un problema més difícil és demostrar quin és el màxim de monedes, i per això s'ha d'utilitzar la 2a solució. No obstant, hi ha un argument intuïtiu:
Per a (n+1) pesades s'ha d'analitzar el màxim de monedes, entre balança i taula: Un màxim a la balança és 3^n monedes, ja que després de la 1a inclinació de balança 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.
El màxim de monedes a la taula: si la moneda falsa està a la taula, hi a equilibri en la 1a pesada i són totes monedes «bones»: en escullir 3^(n-1) monedes de la taula en pesar-les amb altres tantes «bones», si està aquí la moneda falsa se la pot trobar-la amb (n-1) pesades que queden; si hi ha equilibri s'ha de repetir el procés amb 3^(n-2) monedes, amb (n-2) pesades que queden;...; si hi ha equilibri s'ha de repetir el procés amb 3^2 monedas amb altres 9 "bones"; si hi ha equilibri s'ha de repetir el procés amb 3^1 monedes amb altres 3 "bones"; i finalment, si hi ha equilibri s'ha de pesar l'última moneda amb 1 «bona» per saber si pesa més o menys, amb l'última pesada que queda. Sumant totes les monedes de la taula que hem pesat, hi ha 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ó.
2a Solució
[modifica]Vegem primer un mètode per a monedes «orientades» (procedents de la 1a inclinació de balança):
- Es denoten al grup de "n" monedes on s'ha decantat el braç de la balança com: (n+).
- Es denoten 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 es pot identificar el grup de 3 monedes on està la moneda falsa. Anàlogament, si hi ha 27 monedes «orientades» s'ha d'identificar 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" cal n pesades: si 3 és el màxim per a 1 pesada, no es pot 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.
El procediment general: ara només queda veure com configurar la 1a pesada.
Siga la successió A(n)= màxim de monedes per a "n" pesades.
S'ha de calcular A(n+1): màxim de monedes per a "n+1" pesades. A la balança es poden posar un màxim de 3^n; que és el màxim de monedes orientades amb les "n" pesades que hi ha encara. Però com s'ha de pesar un nombre parell, s'ha de restar 1:
Balança = 3^n - 1
I a la taula s'ha de posar un màxim de A(n), però ara no cal pesar un nombre parell, doncs hi haurà monedes de l'hipotètic equilibri de la balança:
Taula = A(n) + 1
Calcular 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 es pot posar 1 moneda, i en la balança ja s'ha 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
squema 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
- 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 1a pesada, està en el grup (1,2,6). Si no, estarà en el grup (3,4,5).
Referències
[modifica]- ↑ Smith, Cedric A. B «The Counterfeit Coin Problem» (en anglès). The Mathematical Gazette. The Mathematical Association, 31, No. 293, 1947 (febrer), pàg. 31-39.