L’indovinello del dittatore e della bottiglia avvelenata: come trovare l’elemento difettoso nel gruppo

L'indovinello del dittatore e delle bottiglie di vino è un celebre problema di logica. Un dittatore deve scoprire quale bottiglia, tra le 1000 in suo possesso, è stata avvelenata da un assassino. Per farlo ha solo 24 ore e può usare come assaggiatori 10 prigionieri condannati a morte. L'unica certezza che ha è che basta una sola goccia del vino avvelenato per uccidere un adulto. Come farà a trovare esattamente la bottiglia contaminata?

Questo indovinello non è soltanto un gioco di logica: è un esempio di group testing, una tecnica per individuare rapidamente un elemento difettoso all'interno di un gruppo molto numeroso. Nata in ambito medico, questa procedura viene utilizzata ancora oggi in settori come le telecomunicazioni e la cybersecurity. In questo articolo vediamo qual è stata la soluzione utilizzata dal dittatore e come questa strategia si applica a problemi reali.

L'indovinello del dittatore e delle bottiglie di vino

La situazione è questa: un crudele dittatore ha organizzato una festa grandiosa nel suo paese e, per l’occasione, si è fatto arrivare 1000 bottiglie di vino pregiato. Si scopre, però, che un assassino si è intrufolato nelle cantine e ha avvelenato una e una sola delle bottiglie. Il veleno iniettato dall’assassino è incolore, inodore e privo di sintomi fino alla morte, che sopraggiunge tra le 10 e le 15 ore dopo l'ingestione. Non esiste alcun modo di individuare la bottiglia contaminata se non facendone bere il contenuto a qualcuno e basta una sola goccia di veleno ad uccidere una persona adulta.

Il dittatore ha 10 prigionieri condannati a morte e decide di usarli per testare il vino. La sua prima idea è di dividere le bottiglie in 10 gruppi da 100 e di far bere a ciascun condannato una goccia di ciascuna bottiglia del gruppo. Quindi, il primo condannato berrebbe 100 gocce prese dalle bottiglie 1-100, il secondo 100 gocce dalle bottiglie 101-200, il terzo 100 gocce dalle bottiglie 201-300 e così via. Alla morte di uno dei condannati, il dittatore si sbarazzerà delle 100 bottiglie da cui ha bevuto quel condannato e potrà usare le restanti 900.

Il dittatore, però, vorrebbe salvare ancora più bottiglie. Interviene allora un fido consigliere che gli suggerisce una soluzione per trovare esattamente la bottiglia avvelenata. Vediamo qual è!

La soluzione: utilizzare il codice binario

Per capire la soluzione del consigliere dobbiamo pensare come dei computer, cioè in sistema binario. A differenza del sistema decimale, che utilizziamo ogni giorno e si basa su dieci cifre (da 0 a 9), il sistema binario usa soltanto su due cifre: 0 e 1.

Proviamo quindi a descrivere il nostro problema usando solo 0 e 1, partendo dai condannati. Ciascuno di loro può fare due azioni: bere o non bere da una bottiglia. Quindi, possiamo rappresentare le loro azioni con un 1 (beve dalla bottiglia) o uno 0 (non beve dalla bottiglia). Guardiamo ora le bottiglie.

Numeriamo le bottiglie usando il sistema binario. Nel sistema decimale, quello che siamo abituati ad usare, ogni posizione corrisponde a una diversa potenza di 10: la cifra più a destra corrisponde a 10⁰ (cioè 1, le unità), poi c’è 10¹ (cioè le decine), poi 10² (cioè le centinaia) e così via, aumentando man mano l’esponente di uno. La cifra (da 0 a 9) che leggiamo in ogni posizione ci dice quante volte dobbiamo considerare quella potenza. Ad esempio, il numero 34 è fatto da 4 volte 10⁰ , cioè 4 · 1 = 4 e  3 volte 10¹ , cioè 3 · 10 = 30. Se sommiamo 30 e 4, otteniamo proprio 34.

Per scrivere un numero in binario, si ragiona in maniera analoga, ma si usano le potenze di 2, non di 10. In questo caso, la cifra più a destra corrisponde a 2⁰ (cioè 1), alla sua sinistra abbiamo 2¹ (cioè 2), poi 2² (cioè 4) e così via. Anche qui la cifra che leggiamo in ogni posizione ci dice quante volte dobbiamo considerare quella potenza, ma in questo caso abbiamo solo due possibilità, cioè 0 (non usare quella potenza) e 1 (usala).

Riprendendo il numero 34, in binario è fatto da: 0 volte 2⁰, cioè 0 · 1 = 0; 1 volta 2¹ , cioè 1 · 2 = 2; 0 volte 2², cioè 0 · 4 = 0; 0 volte 2³, cioè 0 · 8 = 0; 0 volte 2⁴, cioè 0 · 16 = 0; 1 volta 2⁵, cioè 1 · 32 = 32. Mettendo tutto insieme, abbiamo che 34 scritto in binario è 100010. Infatti, se sommiamo 32 + 2 otteniamo 34.

Etichettiamo quindi le bottiglie in binario. Sulle etichette vedremo quindi comparire i numeri da 1 (la numero 1) a 1111101000 (la numero 1000).

A questo punto, prendiamo i dieci condannati e li mettiamo in fila. Ciascun condannato rappresenterà una potenza di 2. Il condannato più a destra sarà 2⁰ (cioè 1), quello più a sinistra 2⁹ (cioè 512).

Ora prendiamo ciascuna bottiglia e leggiamo l’etichetta con sopra scritto il numero in codice binario. Diamo poi una goccia da bere a tutti i condannati che si trovano nelle posizioni in cui c’è un “1” (che corrispondeva a “beve”). Ad esempio:  la bottiglia numero 4 avrà 00000000100 (4 in binario) scritto sull’etichetta. Quindi, verrà fatta bere una goccia di quel vino al terzo condannato da destra, perchè c’è un 1 in terza posizione. Per la bottiglia 295 (0100100111) daremo da bere (partendo da destra) ai primi tre, al sesto e al nono condannato.

Fatto questo, ci basterà attendere fino a 20 ore e vedere quali condannati muoiono. Se morissero, ad esempio i condannati in posizione 2 e 6, sapremmo che la bottiglia avvelenata è quella che sull’etichetta ha scritto 0000100010, cioè la bottiglia numero 34.

Usando questa strategia, saremo in grado di ricavare esattamente il numero della bottiglia avvelenata e potremo quindi salvare le altre 999.

Come trovare gli “errori” in un grande gruppo: cos'è il group testing

Questo tipo di ragionamento è un esempio di quello che viene chiamato group testing, o test di gruppo, una procedura in cui si cerca di identificare elementi “difettosi” (nel nostro caso, la bottiglia avvelenata) all'interno di un insieme molto grande. Di solito, questo tipo di test viene fatto con più di un elemento “difettoso” e diventa, di conseguenza, più complesso dell’esempio che abbiamo riportato qui.

La prima formulazione del group testing risale al 1943, durante la Seconda Guerra Mondiale. Fu inventato per risolvere un problema critico durante la leva: testare decine di migliaia di reclute per la sifilide. Per ridurre il numero di test necessari, si raccoglievano i campioni di siero di molti soldati insieme e si analizzava l’intero gruppo, invece di testare ogni recluta singolarmente. Il principio del group testing ha trovato applicazione anche in altri ambiti. Ad esempio, viene usato per gestire la condivisione dei canali tra dispositivi di comunicazione radio. Anche nel campo dell'informatica e della cybersecurity si utilizza un approccio simile per scoprire errori o vulnerabilità in grandi sistemi complessi.

Il principio alla base è sempre lo stesso: ridurre al minimo il numero di test necessari usando la strategia migliore, come ha fatto il consigliere con le bottiglie di vino.