[HOME - BASE Cinque - appunti di Matematica ricreativa]

Il famoso problema delle 12 monete

Questo problema si trova in altre pagine di BASE Cinque ma siccome periodicamente ricevo richieste di chiarimenti, ho deciso di dedicargli una ulteriore pagina. Un particolare ringraziamento a Dario Uri, Paolo Hägler, Alberto Fabrizi Massimo Giorgi e Matteo per avermi segnalato queste varianti e/o inviato le soluzioni.

Il problema delle 12 monete (versione facile)
Abbiamo 12 monete che sembrano identiche ma non lo sono. Una di esse ha un peso diverso dalle altre ma non sappiamo qual è e neppure se è più pesante o più leggera delle altre. Originale, vero?
Dobbiamo scoprire qual è la moneta di peso diverso, con 3 pesate comparative utilizzando una bilancia a due piatti.

Il problema delle 12 monete (versione difficile)
Siano date 12 monete, tra cui una di peso diverso dalle altre, e una bilancia a due piatti. Stabilire con 3 pesate quale sia la moneta di peso diverso, e se è più pesante o più leggera delle altre.

Il problema delle 13 monete (ci aspettiamo una dimostrazione!)
Abbiamo 13 monete apparentemente uguali nella forma, dimensione, colore, etc. Però siamo sicuri che una di queste ha un peso diverso dalle altre 12.
Non ci dicono se pesa di più o di meno.
Con una bilancia a 2 piatti e tentando solo 3 pesate dobbiamo individuare questa moneta.
Sembra che 13 monete sia il massimo numero per cui il problema possa essere risolto con tre pesate. Chi sa dimostrarlo?

Nota storica.
Emil D. Achell in una lettera del 17 luglio 1978 a Paul J. Campbell afferma di aver sentito parlare di un problema simile a questo da Walter W. Jacobs nel 1944. Il problema era di trovare una moneta falsa più leggera fra altre 26 di peso uguale in 3 pesate. Lo stesso Achell afferma che il problema è forse anteriore al 1939.
Sembra che nel 1943 (però pubblicato nel 1945) sia stato posto il problema in cui non si sa se la moneta falsa è più leggera o più pesante delle altre.

Nel 1976 N. J. Maclean e nel 1992 Calvin T. Long, espongono un metodo ternario per risolvere il problema delle 12 monete. Il caso generale è (3n-3)/2 monete in n pesate comparative. Ciascuna pesata determina una cifra di un numero in base 3. Il numero risultante rivela qual è la moneta diversa e se è più pesante o più leggera delle altre.

Ultimo aggiornamento: gennaio 2006

Risposte & riflessioni

Il problema delle 12 monete (versione difficile)
Soluzione di Paolo Hägler
Pesata 1: pesiamo due insiemi di 4 monete (lasciandone 4 da parte).

Caso A. I due piatti indicano lo stesso peso.
Quindi le 8 monete messe sulla bilancia sono buone (siano BBBBBBBB) e tra le quattro non pesate (NNNN) si nasconde quella taroccata.

Pesata 2: pesiamo NNN con BBB

Aa) NNN hanno un peso superiore a BBB La moneta taroccata è tra NNN ed è più pesante delle altre.

Pesata 3: pesiamo N con N

Aai) Una delle due monete ha peso maggiore dell'altra, quella di peso maggiore è quella diversa.

Aaii) Le due monete hanno lo stesso peso . Quella non pesata delle 3 N è quella diversa ed ha peso maggiore.

Ab) NNN e BBB hanno lo stesso peso La moneta N non messa sulla bilancia ha peso diverso dalle altre. Con la pesata 3, a confronto con un'altra moneta, scopriamo se è più pesante o leggera delle altre.

Ac) NNN hanno un peso inferiore a BBB La moneta taroccata è tra NNN ed è più leggera delle altre.

Pesata 3: pesiamo N con N

Aaiii) Una delle due monete ha peso minore dell'altra, quella di peso minore è quella diversa.

Aaiv) Le due monete hanno lo stesso peso. Quella non pesata delle 3 N è quella diversa ed ha peso minore.

Caso B. I due piatti indicano pesi diversi.
Siano AAAA le 4 monete pesate a sinistra (supponiamo più pesanti delle 4 a destra, chiamate DDDD) e siano BBBB le 4 (buone) che non sono salite sulla bilancia.

Pesata 2: DAAA-ABBB

Ba) DAAA hanno peso maggiore di ABBB La moneta diversa ha peso maggiore delle altre, ed è tra le 3 a. Vedi caso Aa)

Bb) DAAA hanno peso pari a ABBB La moneta diversa ha peso minore delle altre, ed è tra le 3D non messe sulla bilancia. Vedi caso Ac)

Bc) DAAA hanno peso minore a ABBB La moneta diversa o è la D spostata a sinistra (più leggera), o è la a spostata a destra (più pesante). Si pesi una di queste due con una terza per scoprire di quale caso si tratta.

Ancora il problema delle 12 monete (versione difficile)
Una soluzione col metodo ternario
La soluzione col metodo ternario si basa su questa idea:

associamo un simbolo ad ciascun piatto della bilancia, ad es. S, D (sinistra, destra) e un numero ad ogni moneta;
associamo un simbolo ad ognuno dei tre possibili esiti di una pesata, ad esempio S se è più pesante il piatto a sinistra, D se è più pesante il piatto a destra e = se i piatti sono in parità; in alternativa si possono usare le lettere a, b, c oppure i numeri 1, 2, 0.
nel caso di 12 monete, facciamo tre confronti di gruppi opportuni di monete; se le monete sono più di 12 serviranno più pesate;
ad ogni pesata associamo uno dei simboli S, D, = a seconda dell'esito;
in base alla sequenza di simboli ottenuti, deduciamo qual è la moneta diversa e se pesa più o meno delle altre.

La tabella qui sotto illustra tre possibili raggruppamenti delle monete. Le lettere S, D indicano i due piatti della bilancia.

Moneta n°

1° pesata

2° pesata

3° pesata

Le possibili sequenze diverse di tre simboli, S, D, = con ripetizione sono 27, cioè tutti i possibili numeri di tre cifre in base 3 (inserendo anche gli zeri iniziali, 000, 001, 002, 010, ...).
Tuttavia i possibili esiti validi delle pesate sono soltanto 24, o meglio 25 nel caso nessuna delle monete avesse peso diverso dalle altre.
Vediamoli in dettaglio. Per capire i risultati occorre osservare la tabella sopra.

===	è possibile solo se le monete hanno tutte lo stesso peso, il che contraddice l'ipotesi del problema
==S	la 12 è la più pesante perché dalle pesate 1 e 2 si capisce che le altre 11 monete sono tutte buone e nella terza pesata il piatto dov'è la 12 è più pesante
==D	la 12 è la più leggera perché dalle prime 2 pesate si capisce che le prime 11 monete sono tutte buone e nella terza pesata il piatto dov'è la 12 è più leggero
=S=	la 11 è la più pesante perché dalle pesate 1 e 3 si capisce che le altre 11 monete sono tutte buone e nella terza pesata il piatto dov'è la 11 è più pesante
=SS	la 9 è la più pesante perché è l'unica che compare nel piatto S in entrambe le pesate 2, 3 e il piatto S è il più pesante
=SD	la 10 è la più pesante perché è l'unica che compare nei piatti SD , che risultano più pesanti in entrambe le pesate 2, 3
=D=	la 11 è la più leggera perché dalle pesate 1 e 3 si capisce che le altre 11 monete sono tutte buone e nella terza pesata il piatto dov'è la 11 è più leggero
=DS	la 10 è la più leggera perché è l'unica che compare nei piatti SD , che risultano più leggeri in entrambe le pesate 2, 3
=DD	la 9 è la più leggera perché è l'unica che compare nel piatto S in entrambe le pesate 2, 3 e il piatto S è il più leggero
S==	la 8 è la più leggera perché è l'unica che compare nel piatto D, che risulta più leggero, nella pesata 1
S=S	la 7 è la più leggera perché è l'unica che compare nei piatti DD, che risultano più leggeri, nelle pesate 1, 3
S=D	la 6 è la più leggera perché è l'unica che compare nei piatti DS, che risultano più leggeri, nelle pesate 1, 3
SS=	la 5 è la più leggera perché è l'unica che compare nei piatti DD, che risultano più leggeri, nelle pesate 1, 2
SSS	questo caso non si può verificare perché non c'è nessuna moneta che compare nello stesso piatto in tutte le pesate
SSD	la 1 è la più pesante perché è l'unica che compare nei piatti SSD, che risultano più pesanti, nelle 3 pesate
SD=	la 4 è la più pesante perché è l'unica che compare nei piatti SD, che risultano più pesanti, nelle pesate 1, 2
SDS	la 2 è la più pesante perché è l'unica che compare nei piatti SDS, che risultano più pesanti, nelle 3 pesate
SDD	la 3 è la più pesante perché è l'unica che compare nei piatti SDD, che risultano più pesanti, nelle 3 pesate
D==	la 8 è la più pesante perché è l'unica che compare nel piatto D, che risulta più pesante, nella pesata 1
D=S	la 6 è la più pesante perché è l'unica che compare nei piatti DS, che risultano più pesanti, nelle pesate 1, 3
D=D	la 7 è la più pesante perché è l'unica che compare nei piatti DD, che risultano più pesanti, nelle pesate 1, 3
DS=	la 4 è la più leggera perché è l'unica che compare nei piatti SD, che risultano più leggeri, nelle pesate 1, 2
DSS	la 3 è la più leggera perché è l'unica che compare nei piatti SDD, che risultano più leggeri nelle tre pesate
DSD	la 2 è la più leggera perché è l'unica che compare nei piatti SDS, che risultano più leggeri, nelle 3 pesate
DD=	la 5 è la più pesante perché è l'unica che compare nei piatti DD, che risultano più pesanti, nelle pesate 1, 2
DDS	la 1 è la più leggera perché è l'unica che compare nei piatti SSD, che risultano più leggeri, nelle 3 pesate
DDD	questo caso non si può verificare perché non c'è nessuna moneta che compare nello stesso piatto in tutte le pesate

Esistono molti altri raggruppamenti oltre a quelli proposti nella tabella precedente.
Basta fare in modo che in ogni riga ci siano 4 D e 4 S e che le colonne siano tutte diverse.
Attenzione! C'è bisogno di una condizione in più.
Definisco complementare di una colonna, la colonna che si ottiene scambiando ogni S con un D e viceversa. La condizione in più è che non ci devono essere colonne complementari.
Ad esempio:

Moneta n°

1° pesata

2° pesata

3° pesata

Quanti sono i casi possibili?

La soluzione postata da John Conway al Math Forum!
Conway gioca meravigliosamente su un'ambiguità: le terne di lettere sono i nomi delle monete, ma indicano anche le terne di esiti delle pesate.

Posted: Jan 28, 1999 7:19 PM
Here's the solution to the n-weighing version of this problem that I said I'd recently read. It was found by Dyson and Lyness in 1946; I think I've improved the exposition. I'll explain it for the original problem first, and then explain the generalization.

Label the 12 coins by the sequences

AAB ABA ABB ABC BBC BCA BCB BCC CAA CAB CAC CCA

and in the

1st AAB ABA ABB ABC BBC BCA BCB BCC
2nd weighings put AAB CAA CAB CAC in pan A, ABA ABB ABC BBC in pan B.
3rd ABA BCA CAA CCA AAB ABB BCB CAB

Now in a given weighing, a pan will either end up in the

Canonical position (C) that it assumes when the pans are balanced, or
Above that position (A), or
Below it (B),

so the weighings determine a sequence of three of these letters.

If this sequence is CCC, then there's no fake coin. Otherwise, for just one of the two pans the sequence is among the 12 above, and names the fake coin, whose weight is Above or Below the proper one according as the pan is A or B.

N weighings can be used to locate a possible fake from among (3^N - 3)/2 coins in the same way, by labelling them with all the non-constant sequences of N letters from A,B,C whose first change is A-to-B or B-to-C or C-to-A, and at the kth weighing putting those whose kth letter is A in pan A and those whose kth letter is B in pan B.

Neat, isn't it?

John Conway

Il problema delle 12 monete (versione facile)
Soluzione di Alberto Fabrizi
Definiamo BUONE le 11 monete di eguale peso e <D> la moneta di peso diverso.
Osserviamo preliminarmente che:
osservazione 1) avendo una riserva di "buone" è possibile individuare <D> fra due monete mediante il confronto di una di esse con una delle buone;
osservazione 2) qualora si sapesse che <D> abbia peso maggiore (o minore) basterebbe una sola pesata per individuarla fra tre monete.

Si proceda dunque nel modo seguente.
Si pongano su ciascuno dei due piatti quattro monete.
Possono verificarsi due casi:
1° caso: i due gruppi di 4 monete hanno lo stesso peso;
2° caso: i due gruppi di 4 monete hanno peso diverso.

Esaminiamo ora i due casi possibili.

1° caso: i due gruppi di 4 monete hanno lo stesso peso;
Se hanno peso uguale, abbiamo costituito una riserva di otto buone, e <D> sta tra le altre quattro. Nella seconda pesata confrontiamo due di quest'ultime con due buone: se il peso è uguale, <D> starà fra le due monete mai pesate, altrimenti è una di queste due; la terza pesata, per l'osservazione 1, la individuerà.

2° caso: i due gruppi di 4 monete hanno peso diverso.
Se dalla prima pesata il piatto sinistro risulta più pesante del destro, abbiamo una riserva di quattro buone, che sono le monete non pesate.
Dette AAAA le monete che sono state pesate nel piatto sinistro, DDDD quelle pesate nel piatto destro e BBBB quelle buone, operiamo la seconda pesata nel seguente modo: DAAA - ABBB (abbiamo scambiato di piatto due monete e sostituito tre monete del piatto destro con tre buone).

a questo punto si hanno 3 sotto-casi.

1) Se il piatto sinistro continua a essere più pesante, sappiamo che <D> è una delle tre AAA dello stesso piatto, e sappiamo anche che la falsa è più pesante; con la terza pesata possiamo individuarla (per l'osservazione 2).
2) Se invece i piatti alla seconda pesata registrano lo stesso peso, sappiamo che <D> è una delle tre DDD sostituite sul piatto destro con tre buone, e sappiamo anche che <D> è più leggera; perciò <D> può essere individuata con la terza pesata (osservazione 2).
3) Se infine il piatto sinistro diviene più leggero, <D> è una delle due monete scambiate da un piatto all'altro, e anche in questo caso la terza pesata può individuarla (osservazione 1).

Il problema delle 13 monete (ci aspettiamo una dimostrazione!)
Soluzione di Alberto Fabrizi
Si pongano 4 monete su un piatto e 4 in un altro. Nel caso in cui abbiano lo stesso peso, il procedimento è lo stesso che nel problema delle 12 monete. Se invece si riscontra peso diverso, rimangono due pesate per individuare tra le 5 monete rimanenti quella di peso diverso.

Premesso che:

(1) è possibile individuare in una sola pesata la moneta diversa tra due confrontando una di queste con una moneta "buona";
(2) è possibile individuare in una sola pesata la moneta diversa tra tre, nel caso in cui si sappia se essa ha peso maggiore o minore rispetto alle altre;

nella seconda pesata basta porre tre monete delle cinque su un piatto e tre monete "buone" sull'altro.
Se la bilancia rimarrà in equilibrio, allora la scelta si restringe alle due uniche monete mai pesate, e per la premessa (1) è individuabile in una sola pesata.
Se invece un piatto risulterà più pesante dell'altro, sarà finalmente noto se la moneta cercata ha peso maggiore o minore rispetto alle altre, così per la premessa (2) è individuabile in una sola pesata.

Sito Web realizzato da Gianfranco Bo