L'imperatore e la bottiglia avvelenata

[rporrini]

Siete il monarca di un impero medievale ed avete organizzato una grande festa celebrativa per il giorno a venire. Questa festa è la più importante di quelle che avete organizzato finora. Sono arrivate 1000 bottiglie di vino che avete intenzione di offrire durante la festa, ma venite a sapere con certezza che una di queste è avvelenata.

Il veleno non da altri sintomi se non la morte che avviene tra le dieci e le venti ore dopo avere ingerito anche una goccia di veleno.

Avete più di mille schiavi a vostra disposizione e solo 24 ore per determinare quale sia la bottiglia avvelenata.

Avete qualche prigioniero già condannato a morte, e la morte di chiunque altro rovinerebbe la vesta.

Qual è il minimo numero di prigionieri necessari da utilizzare come assaggiatori per essere assolutamente sicuro di trovare la bottiglia avvelenata entro 24 ore?

 

[Ramsey]

1 solo: consegno una bottiglia per uno con l'obbligo di riportarla il giorno dopo dopo averne assaggiato massimo un bicchiere, pena la morte. Me ne torneranno 999.

 

[rporrini]

1 solo: consegno una bottiglia per uno con l'obbligo di riportarla il giorno dopo dopo averne assaggiato massimo un bicchiere, pena la morte. Me ne torneranno 999.

Non hai così tanti prigionieri. E comunque la domanda è: Quale è il numero minimo di persone di cui hai bisogno per assaggiare il vino?

 

[kadaj]

Ma le altre 999 bottiglie le devo utilizzare per la festa immagino... :-?

 

[eriadan]

Siete il monarca di un impero medievale ed avete organizzato una grande festa celebrativa per il giorno a venire. Questa festa è la più importante di quelle che avete organizzato finora. Sono arrivate 1000 bottiglie di vino che avete intenzione di offrire durante la festa, ma venite a sapere con certezza che una di queste è avvelenata.

Il veleno non da altri sintomi se non la morte che avviene tra le dieci e le venti ore dopo avere ingerito anche una goccia di veleno.

Avete più di mille schiavi a vostra disposizione e solo 24 ore per determinare quale sia la bottiglia avvelenata.

Avete qualche prigioniero già condannato a morte, e la morte di chiunque altro rovinerebbe la vesta.

Qual è il minimo numero di prigionieri necessari da utilizzare come assaggiatori per essere assolutamente sicuro di trovare la bottiglia avvelenata entro 24 ore?

ma anche nessuno.
incarico ogni schiavo di recapitare la bottigilia a chi la ha offerta intimandogli di berne un sorso. QUello che nicchia o tergiversa lo si arresta e lo si decolla o gli si fa ingurgitare a forza il vino, e con tutte le altre? "FIESTA!"

 

[bandian]

64. Ma il margine di questo post è troppo stretto per poter contenere una dimostrazione di questo fatto.

 

[rporrini]

64. Ma il margine di questo post è troppo stretto per poter contenere una dimostrazione di questo fatto.

Se ne possono usare anche meno.

 

[Angiolillo]

Direi 10... Di cui ne muoiono in media poco meno di cinque.

Se la mia idea è giusta, ci sono diverse soluzioni che portano tutte a far morire circa cinque, o una media di quasi cinque, prigionieri. Ma ipotizzando che le bottiglie siano di qualità diversa (volendo anche di mille qualità diverse, di ciascuna delle quali si può dire se sia migliore o peggiore di ogni altra), qual è il sistema che consente di sprecare meno vino pregiato sacrificando quello più "andante"?

 

[ZioCino]

0 prigionieri.
1000 schiavi.

risultato: 1 schiavo morto -> 1 bottiglia selezionata...

 

[Angiolillo]

Variante. Non sono 1000 schiavi, sono 1000 dipendenti. E all'imporovviso, sciopero! on c'è modo di farli lavorare.

Vi restano il matematico di corte e un plotone del Genio, una manciata di uomini numerosa quanto i condannati a morte. Come fate?

 

[kadaj]

Direi 10... Di cui ne muoiono in media poco meno di cinque.

DI-MO-STRA-ZI-O-NE DI-MO-STRA-ZI-O-NE DI-MO-STRA-ZI-O-NE !!! :lol: :lol: :lol:

 

[Angiolillo]

Facciamo giocare anche gli altri, no?

 

[bandian]

Ecco perchè ho detto 64.


Il fatto che a far effetto ci metta tra le 10 e le 20 ore e a disposizione ce ne sono solo 24, mi fa pensare che non si possano fare due test successivi (non si avrebbe il tempo), mentre se ne possono fare quanti ne vuoi contemporaneamente.

Prendi 32 schiavi. A ognuno di loro dai 32 bottiglie. (32x32 > 1000). Se ne mischia un goccetto da ognuna e ciascuno beve.

Contemporaneamente prendi altri 32 schiavi e a ognuno di loro dai una bottiglia proveniente da uno degli altri 32 schiavi. Mischiano e bevono.

Visti i due schiavi che muoiono hai individuato la bottigia avvelenato ottenuto il risultato sperato in meno di 24 ore e con 32+32= 64 schiavi.

Come si fa a fare meno?

 

[rporrini]

Direi 10... Di cui ne muoiono in media poco meno di cinque.

Parlami di più di questa idea.

 

[rporrini]

Ricordo a tutti che il veleno assomiglia al vino in tutto e per tutto, dunque la bottiglia avvelenata ne è piena.

 

[Angiolillo]

Direi 10... Di cui ne muoiono in media poco meno di cinque.

Parlami di più di questa idea.

Ecco le due soluzioni che avevo in mente, quella che minimizza il vino buono bevuto e quella che fa a meno degli schiavi. Da leggere in fretta, perché abbiamo meno di quattro ore... I prigionieri devono assaggiare quasi 500 bottiglie a testa, in 4 ore fa poco meno di 30 secondi ad assaggio.

Poiché ciascuno assaggia quasi metà delle bottiglie, i prigionieri hanno poco meno della metà di probabilità di morire. Il che porta a perdite medie poco sotto ai cinque condanati.

Per consumare di meno il vino migliore
Prendiamo 10 prigionieri e 999 schiavi. Ogni prigioniero, in ceppi in un punto diverso di un vasto spiazzo, ha una lettera dell'alfabeto da A a J. Ogni schiavo per comodità potrebbe avere un numero da 1 a 999 e riceve una bottiglia e precise istruzioni. La bottiglia migliore non la prende nessuno, quella un po' peggiore lo schiavo 1, quella un pochino peggiore il 2 e così via fino al 999 che ha la peggiore di tutte.
Lo schiavo 1 deve far assaggiare al prigioniero A, il due al B e così via fino al 10 che va da J.
L'11 va da A e B, il 12 da A e C e così fino al 19 che va da A e J, il 20 da B e C, il 21 da B e D e così via ancora fino a I e J.
Poi si prosegue con tutte le combinazioni di 3 prigionieri, poi di 4 e così via fino a combinazioni di 9 prigionieri (sui 10 disponibili).
Ogni bottiglia viene assaggiata da un numero di prigionieri compreso tra 0 (la bottiglia migliore) e 9 (la peggiore). Ogni schiavo deve far fare un massimo di nove assaggi in quattro ore, può farcela. Specie se il matematico di corte si mette lì e trova un sistema per minimizzare le file e le attese davanti a ciascun prigioniero - questo io me lo risparmio.
Entro 20 ore morirà un certo numero di prigionieri. Si va dall'unico schiavo che ha fatto assaggiare a tutti quelli e solo a quelli, la bottiglia avvelenata è quella che ha lui. Se nessuno muore vuol dire che la bottiglia avvelenata è la migliore di tutte, e la festa un pochetto ce la siamo guastata uguale...

Se gli schiavi scioperano
Ogni prigioniero viene affidato a un geniere che lo trascina ad assaggiare le bottiglie. Le bottiglie sono in fila, da 1 a 1000 con un po' di spazio tra l'una e l'altra.
Il primo geniere salta le prime 512 bottiglie e fa assaggiare le altre in ordine.
Il secondo geniere fa assaggiare 256 bottiglie no e 256 bottiglie sì (quindi dalla 257 alla 512 e dalla 769 in poi).
Il terzo geniere fa assaggiare 128 bottiglie no e 128 sì (quindi dalla 129 alla 256, dalla 385 alla 512 e così via).
...
Il decimo fa assaggiare ua bottiglia no e una sì.
In questo caso i tempi sono affini, un po' meno di mezzo minuto i media per ogni assaggio. Se le bottiglie sono ancora da stappare, con 10 genieri al posto di 1000 schiavi il primo assaggio sarà un po' più lento ma possiamo farcela uguale. Tutti partono da bottiglie diverse e quindi ci si dovrebbe impicciare poco con le file, almeno all'inizio (il matematico di coprte potrebbe decidere un sistema per far andare alcuni in direzione opposta o partendo dal centro e trucchi simili al fine di minimizzare le file sulle stesse bottiglie).
Uno o più dei prigionieri moriranno, si va a vedere la bottiglia che è stata assaggiata da tutti loro e solo loro, ed è quella avvelenata. Se nessuno muore, la bottiglia avvelenata è la prima.

Nel secondo metodo si potrebbero anche disporre le bottiglie più pregiate nei punti che verranno assaggiati di meno (nell'ordine il primo, il cinquecentotredicesimo, il duecentocinquantasettesimo e il settecentosessantanovesimo, e così via) ma qui è parecchio più complicato.
Iniziare saltando le bottiglie, e saltandone 512 anziché 500 (il metodo funzionerebbe ugualmente, con qualche arrotondamento) serve a minimizzare gli assaggi, e quindi il vino consumato.

Ciao a tutti!

Andrea

 

[rporrini]

In realtà supponiamo di avere un numero sufficiente di schiavi, mentre i prigionieri sono in numero ridotto.

Provate a fare i conti come se le bottiglie fossero 8. E poi estendete il ragionamento.

 

[Prousseau]

Il ragionamento di Angiolillo mi sembra avviato correttamente, ma qualcosa non mi torna perché mi sembra che il suo si basa sul sistema decimale di numerazione, mentre la soluzione che ho trovato io si basa su quello binario.

Soluzione
Ci vogliono tanti schiavi (prendiamo tutti i 1000) e 10 condannati. Di questi potrebbero morire tutti ma anche nessuno

Procedimento
Ogni schiavo prende una bottiglia e la numera, rigorosamente in notazione binaria (questo sistema funziona fino a 2 alla 10 bottiglie, cioè 1024), quindi si porranno i numeri 00 00 00 00 00 fino a 11 11 11 11 11 della 1024-esima.
Ai 10 condannati vengono assegnate 10 posizioni fisse, contrassegnate con le cifre dallo 0 al 9, e 10 bicchieri con lo stesso contrassegno, uno per ogni condannato.
Ogni schiavo prende un contagocce, preleva dalla sua bottiglia un po' di vino e ne versa una quantità pari a 1/512 di bicchiere in ogni bicchiere la cui posizione coincide con gli 1 del numero binario sulla sua bottiglia.
Ogni condannato beve solo dal proprio bicchiere.
La posizione dei condannati morti quella sera indicheranno gli 1 del numero binario relativo alla bottiglia avvelenata.

Esempio
Lo facciamo con 8 bottiglie, come consigliato dal buon rporrini. In questo caso bastano 3 condannati (2alla3=8 )

Condannato/bicch.: 2 1 0
------------------------------------------------------------
Schiavo/bottiglia 0: 0 0 0
Schiavo/bottiglia 1: 0 0 1
Schiavo/bottiglia 2: 0 1 0
Schiavo/bottiglia 3: 0 1 1
Schiavo/bottiglia 4: 1 0 0
Schiavo/bottiglia 5: 1 0 1
Schiavo/bottiglia 6: 1 1 0
Schiavo/bottiglia 7: 1 1 1

Questo significa che lo schiavo con la bottiglia 010, ad es., verserà 1/4 di dose (non più 1/512) solo nel bicchiere del condannato 1, lo schiavo 5, ad es., verserà 1/4 nel biccihere 2 e 1/4 nel bicchiere 0.
Così i 3 bicchieri avranno una dose intera di miscela e i 3 condannati la berranno. Se la sera muoiono, ad es., il condannato 1 e il condannato 0, ma non il 2, la bottiglia avvelenata sarà la numero 3 (011), se non muore nessuno la numero 0 (000), se muoiono tutti la numero 7 (111) e così via, se muore solo il condannato 2 la bottiglia è la 4 (100), ecc.

L'esempio è facilmente estendibile a 1024, ma ci vogliono appunto 10 condannati (10 cifre binarie).

 

[Angiolillo]

Mi pare ottima anche questa! Anche se Raffaele non ci ha ancora detto se 10 è davvero il numero necessario o ne bastano meno...

Il ragionamento di Angiolillo mi sembra avviato correttamente, ma qualcosa non mi torna perché mi sembra che il suo si basa sul sistema decimale di numerazione, mentre la soluzione che ho trovato io si basa su quello binario.

Come dicevo scherzando ad alcuni di voi in mail privata, non ho usato direttamente il sistema binario perché siamo in un impero medievale, non in un impero settecentesco, e prima di Leibniz ciò mi pareva un po' anacronistico. Però gli effetti sono gli stessi e alcuni principi impliciti in comune al sistema binario le mie soluzioni li sfruttano: non a caso in uno dei miei due metodi uso i numeri 512, 256, 128 e così via, cioè le potenze di 2... E a confermarlo c'è una sorpresa finale che ti dico più sotto.

Infatti i risultati tuoi e miei sono equivalenti. Le mie due soluzioni, come la tua, sono estensibili fino a 1024 bottiglie senza dover aumentare il numero dei dieci condannati. E anche loro richiedono tre condannati per il caso delle otto bottiglie. Come da richiesta di Raffaele, vado a declinare.

Nella prima soluzione, con otto bottiglie e tre condannati una non viene fatta bere e le altre si fanno bere ai condannati A, B, C, A+B, A+C, B+C, A+B+C.

Nella seconda soluzione, con otto bottiglie e tre genieri assegnati ad altrettanti condannati il primo geniere salta le prime quattro bottiglie e fa assaggiare 5, 6, 7 e 8; il secondo va due a due e fa assaggiare 3, 4, 7 e 8; il terzo va una a una e fa assaggiare 2, 4, 6 e 8. Di nuovo abbiamo una serie di combinazioni esaustiva: la bottiglia 1 non l'assaggia nessuno, la 2 il terzo condannato, la 3 il secondo, la 4 il secondo e il terzo, la 5 il primo, la 6 il primo e il terzo, la 7 il primo e il secondo, la 8 tutti.

Nel mio caso, come nel tuo, si ha una media di poco meno di 5 morti e potrebbero morire al massimo anche in 9 (9 con la seconda soluzione e 8 con la prima soluzione, come vedremo poi): la media sarebbe di 5, e potrebbero effettivamente morire tutti i condannati, se le bottiglie fossero 1024 anziché 1000. Con il tuo metodo: per la media perché se prendi i numeri binari considerando 10 cifre, se ti fermi a mille gli 1 sono un po' meno degli 0 mentre sarebbero invece in ugual numero se tu arrivassi a 1024; per il numero massimo, perché affinché tutti possano morire nel tuo metodo devi assegnare la bottiglia avvelenata allo schiavo 1111111111, che è appunto il milleventiquattresimo, altrimenti se ti fermi a 1000 hai cifre che hanno al massimo nove 1 con le bottiglie numero 511, 767, 895, 959 e 991.

Quindi direi che siamo alla perfetta equicalenza. Se vogliamo divertirci a vedere dei dettagli che sono irrilevanti per il problema come lo ha posto Raffaele, l'unico vantaggio che vedo nella prima delle mie soluzioni è quella, nella variante del quesito che proponevo con qualità disomogenea del vino, del minor spreco di vino buono: le bottiglie sono infatti ordinate per numero crescente di assaggi, cosa che nelle altre soluzioni non è, ed è agevole metterle in fila dalla più buona alla peggiore. Con la mia seconda soluzione, o con il metodo binario che tu proponi, questo non avviene (lo schiavo 0001001010 fa fare molti meno assaggi del precedente 0000111111 ma molti più del precedente 0000000100).
In realtà un altro vantaggio (del tutto non richiesto dal problema) c'è comunque: se si hanno 1000 bottiglie anziché 1024 (o qualunque numero di bottiglie che non sia una potenza di 2), si escludono delle combinazioni, e questo metodo esclude quelle con più assaggi. Con 1000 bottiglie, le 24 combinazioni escluse sono quella con dieci assaggi a bottiglia, dieci combinazioni con 9 assaggi a bottiglia e 13 combinazioni con 8 assaggi a bottiglia. Quindi la mia prima soluzione minimizza il numero di assaggi, e conseguentemente anche la quantità di vino sprecato. Inoltre se ho scartato tutte le combinazioni da 9 e da 10 assaggi, nessuna bottiglia delle 1000 è assaggiata da più di 8 condannati e questo è il numero massimo dei morti (anche se di questo non me ne curo, tanto moriranno ugualmente).

Veniamo alla sorpresa finale. Soluzione in cui i genieri accompagnano i condannati lungo la fila delle bottiglie, caso in cui abbiamo tre prigionieri e otto bottiglie. Dicevamo che la bottiglia 1 non l'assaggia nessuno, la 2 il terzo condannato, la 3 il secondo, la 4 il secondo e il terzo, la 5 il primo, la 6 il primo e il terzo, la 7 il primo e il secondo, la 8 tutti. Per ogni bottiglia mettiamo in fila i tre prigionieri e diamo uno 0 se non l'assaggiano, un 1 se lo assaggiano.

la bottiglia 1 non l'assaggia nessuno: 000
la 2 il terzo condannato: 001
la 3 il secondo: 010
la 4 il secondo e il terzo: 011
la 5 il primo: 100
la 6 il primo e il terzo: 101
la 7 il primo e il secondo: 110
la 8 tutti: 111

Sorpresa: non solo a ogni combiazione corrisponde un numero binario diverso (questo vale anche per l'altra mia soluzione), ma sono anche in perfetto ordine numerico. Esattamente come nella tua soluzione.

Posso chiedere la fonte di questo bell'enigma? Non lo conoscevo affatto.

 

[Prousseau]

Praticamente la mia soluzione e quella di Angiolillo coincidono. La sua non l'avevo "provata" e per questo ho detto che qualcosa non mi tornava.
Mi sembra di aver capito ora, leggendo più attentamente, che l'unica cosa che cambia fra le due è l'ordine dei numeri (binari) utilizzati: io li metto in ordine crescente, cioè nel loro ordine aritmetico (0,1,2,3,...), lui li mette in ordine di numerosità di 1, in modo da risparmiare le bottiglie migliori, quindi 0 (zero uni), 1, 2, 4, 8, ecc... (un 1 a testa) e così via.
Con 8 bottiglie l'ordine di Angiolillo sarebbe quindi:

Condannato/bicch.: 2 1 0
------------------------------------------------------------
Schiavo/bottiglia 0: 0 0 0 (la bottiglia migliore)
Schiavo/bottiglia 1: 0 0 1
Schiavo/bottiglia 2: 0 1 0
Schiavo/bottiglia 3: 1 0 0
Schiavo/bottiglia 4: 0 1 1
Schiavo/bottiglia 5: 1 0 1
Schiavo/bottiglia 6: 1 1 0
Schiavo/bottiglia 7: 1 1 1 (la bottiglia peggiore)

in modo che la quantità di uni vada via via crescendo.
Può darsi però che mi sbagli... o no?