# 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? Hi ha dos solucions del problema.

## 1a solució

La primera solució, de fàcil generalització amb més pesades, s'explica a continuació:
La 1a pesada es realitza així:
En la 2a pesada, es roten els grups de tres monedes així:
* 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ó

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:

## Quin és el màxim de monedes per a "n" pesades?

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:
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:
que coincideix amb l'obtinguda en la generalització.

## 2a Solució

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 al cas de 9 monedes «orientades»:
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:
I en general, per a 3^(n+2) monedes:
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 procediment general: ara només queda veure com configurar la 1a pesada.
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:
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:
Calcular el total entre monedes de la balança i taula:
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:
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.
Endemés, per ser A(n) suma de progressió geomètrica es compleix que cada braç i la taula tenen les mateixes monedes:
squema dels primers termes, així com la configuració de la primera pesada para a cada cas:
* l'exemple de 12 monedes:
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:
b) I si s'inclina, tenim 8=3^2-1 monedes "orientades" i apliquem el mètode descrit per a monedes orientades:

## Referències

* ↑ 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.