I rompicapi di Alice: pesare monete

Il 6.o enigma de Il professor Layton e il paese dei misteri propone al giocatore una bilancia a due bracci e otto pesi, di cui uno è più leggero degli altri. Bisogna trovare questo peso usando la bilancia solo due volte.
In questo caso la soluzione è semplice: basta scegliere due gruppi da tre e confrontarne il peso: se sono uguali, il più leggero è uno dei due scartati, altrimenti si selezionerà il gruppo più leggero e si effettuerà un'ultima pesata tra due dei tre pesetti selezionati.

Padre William e figlio nell'illustrazione di John Tenniell

Diverso il discorso dell'enigma che Harold Hopwood, ottantaduenne enigmista di Gravesend, ripescò dagli archivi del Daily Telegraph del 1937: egli, scrivendo al giornale, chiedeva la risoluzione dell'enigma, che non era ancora riuscito a risolvere:
Supponiamo di avere 12 monete apparentemente tutte identiche. Sappiamo, però, che una di queste è falsa, ma non sappiamo se sia più pesante o più leggera. Per trovarla il numero minimo di pesate necessario è tre.
Una possibile soluzione, citata da Ian Stewart nel bestseller matematico La piccola bottega delle curiosità matematiche del professor Stewart (l'intero micro-capitolo è disponibile in inglese: To find fake coin), è quella proposta da Thomas H. O'Beirne su New Scientist una ventina di anni fa. Nel suo articolo, O'Beirne fa risalire questo rompicapo al 1945, per mano di Howard Grossman, anche se probabilmente risale al XVII secolo. Una, invece, molto bella, scritta in versi, è quella proposta da Blanche Descartes e pubblicata nel 1950 su Eureka:

F set the coins out in a row
And chalked on each a letter, so,
To form the words "F AM NOT LICKED"
(An idea in his brain had clicked).
And now his mother he'll enjoin:
MA DO LIKE
ME TO FIND
FAKE COIN

Ovviamente le monete vengono identificate dalle lettere maiuscole e sono divise in gruppi di quattro. Per determinare la moneta falsa, bisogna comunque preparare una tabella, in modo da determinarla. Alcune di queste tabelle e una serie di altre con disposizioni differenti possono essere trovate su 12 coins problem, pagina di Franciscus Johannes Faase, che segnala anche la soluzione di Bennett Haselton al problema con 13 anziché 12 monete.

Il barone di Münchhausen di Gustave Doré

Altra soluzione è quella proposta da Tanya Khovanova, che è successivamente tornata sull'argomento delle monete in Baron Münchhausen's Sequence, articolo scritto insieme con Konstantin Knop e Alexey Radul. I tre autori riprendono un puzzle proposto nelle Olimpiadi della Matematica russe del 2000:

Sono date 8 monete dal peso di 1, 2, 3, ..., 8 grammi, ma non si conosce quanto pesa ciascuna. Il Barone di Münchhausen afferma di sapere il peso di ciascuna moneta; si offre di dimostrare l'affermazione utilizzando un'unica pesata su una bilancia, così da dimostrare inequivocabilmente il peso di almeno una moneta. E' possibile o sta esagerando?

Mentre è abbastanza scontato che determinare il peso di ciascuna moneta è piuttosto difficile utilizzando un'unica pesata, diverso è il discorso del determinare il peso di almeno una moneta con un'unica pesata. Khovanova, Knop e Radul partono dalla così detta Sequenza di Münchhausen:

Siano date n monete del peso di 1, 2, 3, ..., n grammi. Si suppone che il Barone di Münchhausen conosca il peso di ogni moneta, ma il suo pubblico no. Allora a (n) è il numero minimo di pesate che il Barone deve realizzare su una bilancia in modo da dimostrare inequivocabilmente il peso di almeno una delle monete.

Mentre nel caso di una moneta non è necessario effettuare alcuna pesata (dalle ipotesi, questa pesa 1 grammo), per gli altri casi è necessaria almeno una pesata. In particolare, per un numero che va da 2 a 8, si ottiene la seguente sequenza di pesate:

1, 1, 1, 2, 1, 1, 1

Il caso di due monete è semplice: basta pesarne una. Anche per tre monete basta una pesata: basta dare un'occhiata ai casi possibili.
Caso 1: entrambi i piatti sono all'equilibrio. Questo vuol dire che la moneta da sola pesa 3 grammi.
Caso 2: uno dei due piatti è più leggero dell'altro. Si possono avere in questo caso due possibilità: o la differenza è tale per cui la moneta da sola pesa la metà delle altre due e quindi ha un peso di 2 grammi, o la differenza è superiore, quindi la moneta solitaria ha un peso di 1 grammo.
Il caso a 4 monete è risolubile con una pesata, così come gli altri casi sono risolubili con una pesata, solo nell'ipotesi in cui il Barone conosca il peso di ciascuna moneta (in pratica solo nel caso in cui stia barando!). Il modo di procedere è, come prima confrontare due monete su un piatto con un'altra sull'altro. In quali casi i due piatti della bilancia si equilibrano?

1) Su un piatto ci sono 1+2 grammi, sull'altro 3 grammi: resta la moneta da 4 grammi.
2) Su un piatto ci sono 1+3 grammi, sull'altro 4 grammi: resta la moneta da 2 grammi.

Se ci troviamo, dunque, nella situazione di due piatti in equilibrio, in quale delle due situazioni ci troviamo? Diventa evidentemente necessaria una seconda pesata, a meno di non conoscere il peso di ciascuna moneta⁽¹⁾.
Al di là di questo piccolo dettaglio, i tre ricercatori però sembrano in grado di dimostrare che:

1) due pesate sono sempre sufficienti;
2) nella maggior parte dei casi 1 pesata è sufficiente.

Non mi sono perso nei dettagli della dimostrazione, che comunque si basa tutta sui numeri triangolari e sul fatto che si verifichino alcune condizioni necessarie e sufficienti, ovvero che è possibile determinare il peso di una moneta con un'unica pesata se e solo se:

1) un piatto contenga tutte le monete da 1 a un dato i;
2) l'altro piatto contenga tutte le monete da un dato j fino a n;
3) o la differenza tra i piatti della bilancia è di, o il piatto contenente la moneta da 1 grammo è più leggero di 1 grammo;
4) almeno un piatto contenga esattamente una moneta, o esattamente una moneta è stata scartata.

In effetti, al di là del caso specifico a 4 monete, ciò che è stupefacente è che al crescere delle monete, il numero di pesate minimo non solo è 2, ma in molti casi è addirittura 1.
Maggiori dettagli sul problema specifico potete trovarli sul blog di Tanya. Sempre sul suo blog potete anche trovare Coins sequence e Another coin sequence, che fanno parte della bibliografia del loro preprint, e che ne costituiscono anche parte della dimostrazione.
Infine, ultima segnalazione per Two-pan balance and generalized counterfeit coin problem di Marcel Kołodziejczyk.

P.S.: invece di chiedervi cosa c'entri con Alice un rompicapo dove non viene citato Carroll, chiedetevi invece cosa c'entri una scacchiera con le monete...

---

(1) I tre autori tengono in considerazione questi due casi differenti, ma visto che lasciano due monete di peso differente fuori dai piatti, i due casi sono distinguibili. Non specificano, però, in che modo.

---

Update del 16 giugno 2024, data di ristampa del post: ho recuperato il commento di Piero Patteri, molto interessante, che sulla attuale piattaforma non sarebbe stato possibile importare:

Questo problema me lo propose un mio amico proprio il giorno in cui sostenni l' esame di maturità (1972); glielo aveva presentato il suo professore di matematica e fisica (non all' esame, ovviamente). Tornato a casa, in uno degli stati psicologici più 'svolazzanti' che si possono provare nella vita, mi misi a risolverlo e ci riuscii in un paio d' ore. Premetto che non ho letto tutti i link riportati da Gianluigi, ma in quelli che ho letto ho trovato delle soluzioni meno nitide della mia, e almeno in un caso la soluzione è insufficiente, insomma.... sbagliata.
Nella pagina di Tanya Khovanova nell' enumerazione dei vari casi arriva a individuare (terz' ultimo rigo) la moneta falsa in una terna

If the cups are equal, then the fake coin will be found among 3, 4 or 6

avendo preso la 3 e 4 da un piatto p.es. quello più leggero, e la 6 dall' altro, ovviamente più pesante, non ha acquisito alcuna informazione sulla differenza di peso, in più o in meno, della moneta falsa; quindi se nell'ultima pesata pone sui piatti la 3 e la 6 e la bilancia non è in equilibrio, non può deternimare se la moneta falsa è la 3, più leggera, o la 6, più pesante.
A questo punto vi dico come ho ragionato io. Il concetto di 'acquisire informazioni aggiuntive sulla differenza di peso' fu essenziale per la mia soluzione, e credo per qualsiasi soluzione corretta.
Se consideriamo la pesatura come l' acquisizione di un bit di informazione (uguale-non uguale) con tre pesature si possono discriminare solo otto monete. Per discriminare fra dodici occorre una quarta pesatura, oppure una delle tre deve fornire un' informazione in più. È circa lo stesso procedimento presentato da Tanya, però evita l' errore che ho evidenziato prima.
Si pesano due gruppi di quattro monete, e l' unico caso critico è se la moneta falsa è fra queste, quindi \(P(1 2 3 4) > P(5 6 7 8)\) o viceversa, ma proseguo così...
La pesata successiva deve ridurre la scelta a meno di quattro monete e aggiungere l' informazione 'più pesante' o meno pesante' di quelle buone tra le quali sicuramente sono le quattro monete non pesate (9 10 11 12).
Dal piatto di sinistra togliamo le tre monete  1 2 3 e sostituiamole con tre prese dal piatto di destra 5 6 7, sostituendo queste ultime con tre monete buone 9 10 11.
Sono possibili ora tre casi
\(P(4 5 6 7) > P(8 9 10 11) \rightarrow\) sbilanciam. identico (caso 1)
\(P(4 5 6 7) < P(8 9 10 11) \rightarrow\) sbilanciam. invertito (caso 2)
\(P(4 5 6 7) = P(8 9 10 11) \rightarrow\) equilibrio (caso 3)
Nel caso 3 la moneta falsa è fra quelle tolte dalla bilancia, come nel caso su cui è scivolata Tanya, ma poichè le abbiamo tolte tutte dallo stesso piatto (qui è il punto!), ora sappiamo che la falsa è più pesante e l'ultima pesata disponibile permette di individuarla.
Nel caso 2 sappiamo che la moneta falsa è tra quelle spostate (quindi 5 6 o 7 ) dal piatto più leggero a destra a quello di sinistra, ma ora appunto sappiamo che la moneta falsa, fra quelle tre, è la più leggera, quindi con una pesata si individua.
Nel primo caso invece la moneta falsa è la 4 o la 8, e la si individua facilmente nel confronto con una buona nell' ultima pesata.