La bottiglia avvelenata

Questo è un problema che in passato ho affrontato con i miei alunni in classe, soprattutto quelli di terza, perché, oltre a essere legato a tematiche curricolari, è un buon allenamento per il ragionamento deduttivo in quanto richiede di applicare dei concetti astratti a un problema reale (beh, più o meno reale).

Ecco il problema:

Il nuovo ambasciatore del regno di Caledornia ha organizzato un grande ricevimento per il suo insediamento. Gli invitati arriveranno entro un’ora e le 1000 bottiglie di vino da offrire sono già pronte per essere stappate. Sei il capo della security e hai appena scoperto che una spia ha avvelenato una delle bottiglie. Purtroppo la spia è morta prima di rivelare quale. Hai a disposizione 10 topini catturati in cantina e sai che il veleno agisce in un’ora, cioè proprio quando inizierà la festa! Come farai a individuare la bottiglia avvelenata in tempo?

Riepiloghiamo i dati:

• numero di bottiglie totali: 1000
• topini a disposizione: 10
• $T_{veleno} = 1$ ora
• $T_{festa} = 1$ ora

Il problema è qui, la soluzione invece vi attende dopo l’interruzione. Prendetevi 10 minuti di tempo (o quanti ve ne pare) per risolverlo. Se non ci riuscite, andate avanti.

Finalmente… ve la siete presa comoda.

Soluzione

La prima osservazione da fare è che ciascun topino rappresenta un elemento di memoria binaria, infatti possiede due stati:

Siccome abbiamo 10 topini, è come se avessimo 10 bit.

Quante sono le combinazioni che possiamo ottenere con 10 bit? Se chiamiamo $K$ questo numero, si ottiene:

$K = 2^{10} = 1024$

Dunque possiamo contare da 0 a 1023.

Perciò possiamo numerare tutte le bottiglie di vino adoperando il codice binario. Ad esempio, la bottiglia n. 150 sarà associata al codice seguente:

Allo stesso modo, ogni topino dovrà essere numerato da 0 a 9, a seconda della sua posizione all’interno della stringa di bit.

A questo punto, il trucco consiste nel fare assaggiare il vino solo ai topini corrispondenti agli «1» dell’etichetta di ogni bottiglia. Pertanto, ricapitolando le proprietà dei numeri binari, il topino contrassegnato con 0 assaggerà il vino di tutte le bottiglie dispari, mentre il topino n. 9 assaggerà tutte le bottiglie dalla 512 in poi.

Se, ad esempio, la bottiglia avvelenata è la n. 835, possiamo scrivere

$835_{\text{DEC}} = 1101000011_{\text{BIN}}$

e darla solo ai topini corrispondenti agli «1» dell’etichetta:

Che fortunati, vero?

Dopo aver somministrato un campione di vino da ogni bottiglia, occorre aspettare un’ora affinché il veleno faccia effetto.

Una volta trascorsa l’ora, basta annotare la posizione degli eroici topini che si sono sacrificati, per scoprire la verità. Infatti, i topini morti rappresentano gli 1 nella sequenza binaria, mentre quelli vivi rappresentano gli 0.

Et voilà, la bottiglia avvelenata è la seguente:

Che corrisponde proprio alla n. 835, come già sapevamo. Grazie topini!