Un re malvagio ha 1000 bottiglie di vino. Un re rivale invia un assassino per avvelenare una delle bottiglie. Il veleno è talmente potente che anche una singola goccia uccide, ma impiega esattamente 30 giorni per fare effetto.
Il re malvagio ha 10 schiavi che può usare come assaggiatori. Qual è il numero minimo di schiavi necessari per determinare con certezza quale bottiglia è avvelenata entro 30 giorni?
Pensa alla codifica binaria. Con 10 bit, quanti numeri diversi puoi rappresentare?
Servono solo 10 schiavi.
Numera le bottiglie da 1 a 1000 in binario (da 0000000001 a 1111101000). Assegna ogni schiavo a un bit. Lo schiavo 1 beve da tutte le bottiglie il cui numero binario ha il primo bit = 1, lo schiavo 2 da quelle con il secondo bit = 1, e così via.
Dopo 30 giorni, gli schiavi morti formano un numero binario che identifica la bottiglia avvelenata. Con 10 schiavi puoi codificare 2^10 = 1024 bottiglie, più che sufficienti per 1000.