Problema de les 12 monedes
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.
Taula de continguts |
1ª Solució [modifica]
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]
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]
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à ahí 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 progresió 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]
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).
