Problemi del bilanciamento

I problemi del bilanciamento o problemi della pesata sono problemi di logica che riguardano il bilanciamento di oggetti simili tra di loro, spesso monete. L'obiettivo è determinare quale di questi oggetti abbia un peso diverso dagli altri usando il numero minore di pesate.

Tipi di problemi

In questi tipi di problemi è importante specificare la differenza tra le situazioni in cui si sa già se tra gli oggetti da pesare è sicuramente presente un oggetto diverso e situazioni in cui l'oggetto diverso può anche non essere presente.

Un’animazione del problema del bilanciamento, in questo caso la moneta falsa è più leggera delle altre.

Problema	Tipi di problema	Obiettivo	Numero massimo di monete per n pesate	Numero di pesate per m monete
È noto che una moneta pesa di meno o di più delle altre	La moneta diversa è presente	Trovare la moneta	$3^{n}$	$\lceil \log _{3}(m)\rceil$
È noto che una moneta è diversa ma non se pesi di meno o di più delle altre	La moneta diversa è presente	Trovare la moneta	${\frac {3^{n}-1}{2}}$	$\lceil \log _{3}(2m+1)\rceil$
Non è noto se una moneta sia diversa o se sono tutte uguali	Non è noto se la montea diversa sia presente	Capire se la moneta esiste, e se sia più o meno pesante	${\frac {3^{n}-1}{2}}-1$	$\lceil \log _{3}(2m+3)\rceil$

Problema delle nove monete

Un esempio ben conosciuto del problema del bilanciamento è quello delle nove monete: ci sono nove monete identiche in peso eccetto una, che è più leggera. Questa differenza di peso è percepibile solamente con l’utilizzo di una bilancia a due piatti. Come è possibile isolare la moneta con due sole pesate?

Soluzione del problema delle nove monete in due pesate.

Soluzione

Per trovare una soluzione al problema è necessario capire il numero massimo di monete di cui si può determinare il peso con una sola pesata.

Il numero massimo è tre. Per cercare la più leggera si può infatti fare un confronto tra due monete lasciando una terza al di fuori dei due piatti. Se i piatti della bilancia saranno in equilibrio, la moneta più leggera sarà quella lasciata fuori dalla bilancia, altrimenti sarà la moneta sul piatto che si sposterà più in alto.

Seguendo questa logica, si possono suddividere le nove monete iniziali in tre pile da tre monete l’una. In questo modo è possibile determinare quale delle tre pile sia più leggera, cioè quale sia quella contenente la moneta leggera. Una volta identificata la pila più leggera basterà un'altra pesata per identificare la moneta. Quindi la risposta al quesito è che servono due pesate, con le quali è possibile analizzare fino a 9 oggetti (3 con la prima e 3 con la seconda): 3 X 3 = 9.

Estendendo il ragionamento, con tre pesate sarà possibile analizzare 27 oggetti, e con quattro 81.

Problema delle dodici monete

Una versione più complicata del problema del bilanciamento è dato dal problema delle dodici monete: ci sono dodici monete dall'aspetto identico, tra cui si potrebbe nascondere una moneta falsa che ha un peso diverso dalle altre. Questa possibile differenza di peso è percepibile soltanto con l'utilizzo di una bilancia a due piatti. Come è possibile verificare la presenza della moneta e determinare se questa sia più o meno pesante delle altre, con tre sole pesate?

Soluzione

immagine raffigurante la soluzione del problema delle dodici monete

È opportuno chiedersi innanzitutto se sia possibile risolvere il problema. Si prendono le dodici monete e si elencano tutte le soluzioni possibili, che sono venticinque: più precisamente per ogni moneta è possibile ottenere due soluzioni in cui questa è quella falsa (una nel caso sia più pesante delle altre, una nel caso sia più leggera), e una soluzione in cui la moneta non è presente. Poiché ogni pesata può valutare tre oggetti, con due pesate non sarà possibile risolvere il problema in quanto due pesate permettono di valutare solo nove oggetti. Invece tre pesate permettono di valutare ventisette oggetti. Tre pesate sarebbero quindi sufficienti a risolvere il problema e di conseguenza costituiscono il limite inferiore al numero di operazioni.

Tuttavia, il fatto che non è noto che la moneta diversa è presente, unito al fatto che il numero di oggetti presi in esame è aumentato, comporta la necessità di cambiare il modo in cui si approccia il problema. È importante infatti mantenere il bilanciamento tra i gruppi di oggetti quando si eseguono le pesate. Nel problema delle nove monete le pile erano tre, formate ciascuna da tre monete. Per la risoluzione del problema delle dodici monete si utilizza un metodo simile: si dividono le dodici monete in tre pile da quattro monete l’una. Due pile sono poi poste sui piatti della bilancia. Ci sono due possibilità:

• Un piatto è più pesante dell’altro. In questo caso si rimuovono tre monete dal piatto più pesante e si lasciano fuori dalla pesata, si prendono tre monete dal piatto più leggero e si spostano su quello pesante. A questo punto si prendono tre monete tra quelle non pesate e si mettono sul piatto più leggero. Ci troviamo adesso davanti a tre possibilità:
  • Il piatto che inizialmente era quello pesante rimane quello pesante. Questo può voler dire due cose: che la moneta rimasta sul piatto più pesante è quella pesante o che quella rimasta sul piatto leggero è più leggera. Dopodiché basta confrontare queste monete con una delle dieci monete rimanenti e vedere quale di queste opzioni è vera, risolvendo il problema.
  • Il piatto che inizialmente era quello pesante diventa leggero alla seconda pesata. Questo significa che una delle tre monete passate dal lato leggero a quello pesante è la moneta leggera. Per la terza pesata basta confrontare due di queste tre monete: se queste si bilanciano la terza è quella leggera, altrimenti quella leggera sarà quella sul piatto più leggero.
  • I piatti hanno lo stesso peso. In questo caso vuol dire che tra le tre monete rimosse dal piatto pesante si trova la moneta pesante. Con la terza pesata sarà necessario confrontare due delle tre monete: se queste si bilanciano la terza è quella pesata, altrimenti quella pesante è quella sul piatto più pesante.
• Entrambi i piatti sono bilanciati. In questo caso le otto monete presenti sui due piatti sono identiche e quindi la moneta falsa, se presente, si trova tra le quattro lasciate inizialmente fuori. A questo punto si prendono tre di queste monete e si confrontano con tre monete delle otto iniziali. Ci sono tre possibilità:
  • Le tre monete rimaste fuori inizialmente sono più pesanti. In questo caso è possibile affermare che una delle tre monete è quella falsa e che è anche quella pesante. Si prendono allora due di queste tre monete e si confrontano sulla bilancia. Se queste si bilanciano quella pesante è la terza, altrimenti è quella sul piatto più pesante.
  • Le tre monete rimaste fuori inizialmente sono più leggere. In questo caso possiamo affermare che una delle tre monete è quella falsa e che è anche quella leggera. Si prendono allora due di queste tre monete e si confrontano sulla bilancia. Se queste si bilanciano la terza è quella leggera, altrimenti è quella sul piatto più leggero.
  • I due piatti si bilanciano. In questo caso sappiamo che undici di queste dodici monete sono uguali in peso; perciò, basta confrontare la dodicesima con una qualunque delle altre. Dalla pesata possiamo vedere se questa moneta sia più o meno pesante delle altre, confermando la presenza di una moneta falsa, oppure se abbia lo stesso peso, implicando che tutte e dodici le monete sono uguali e che, di conseguenza, non esiste la moneta falsa.

Esempi di uso dei problemi del bilanciamento nelle opere letterarie

• Niobe, il protagonista del libro Piers Anthony La vendetta di Niobe, deve risolvere una versione del problema delle dodici monete per trovare suo figlio all’inferno: Satana ha trasformato suo figlio in una copia di altri undici demoni; il figlio è però più leggero o più pesante degli altri demoni.
• Beremiz, il protagonista del romanzo di Júlio César de Mello e Souza L’uomo che sapeva contare, incontra un mercante indiano che lo sfida a risolvere un problema in cui otto perle identiche sono poste di fronte all’uomo. Beremiz lo risolve utilizzando solo due pesate seguendo il procedimento spiegato nelle soluzioni precedenti.

Esempi di uso dei problemi del bilanciamento nelle serie televisive

• Nell’episodio Il Capitano Peralta della serie televisiva Brooklyn Nine-Nine, il capitano Holt presenta alla sua squadra una versione del problema delle dodici monete che coinvolge dodici persone diverse.
• Nell’episodio Prova d’intelligenza della serie televisiva Colombo, il detective Colombo risolve una versione del problema in cui dieci sacchetti pieni di monete sono messi a confronto per trovare quale di questi fosse riempito di falsi, sapendo che i falsi e le monete hanno un peso diverso.

Collegamenti esterni

• Un esempio interattivo del problema delle nove monete: (EN) Heavy weights: after Martin Gardner, su puzzles.com. URL consultato il 2 agosto 2022 (archiviato dall'url originale il 15 dicembre 2007).
• Un esempio interattivo del problema delle dodici monete: (EN) The Great Weights Puzzle, su nrich.maths.org. URL consultato il 2 agosto 2022.
• Un video che spiega il problema delle dodici monete e la sua soluzione: Jennifer Lu, Puoi risolvere l'enigma della moneta contraffatta?. URL consultato il 2 agosto 2022.