[?] bottiglia avvelenata

matthewtrager · Messaggio da **matthewtrager** » 01 gen 1970, 01:33

a) un tale vuole organizzare una festa e compra 200 bottiglie di vino. Scopre pero\' che una di esse e\' avvelenata, ma non sa quale. Sapendo che puo\' dare un po\' del vino di ogni bottiglia a dei topi che muoiono per il veleno dopo 30 giorni, e che vuole comunque fare la festa dopo 30 giorni, quanti topi gli servono per trovare la bottiglia avvelenata?
 
 b) e se invece la festa la volesse fare dopo 35 giorni?
 
 ciao!

Franchifis · Messaggio da **Franchifis** » 01 gen 1970, 01:33

Caso semplice:
 Servono almeno 8 topi. Con n topi si possono fare al massimo 2^n gruppi di topi (non mi ricordo il termine esatto) con topi diversi, in pratica l\'insieme delle parti dell\'insieme dei topi. Si fa bere ad ognuno di questi gruppi il vino da una diversa bottiglia e andando a vedere quali topi muoiono si puo\'identificare la bottiglia avvelenata. siccome 2^7=128 e 2^8=256 la soluzione e\' 8.
 
 Adesso tocca ai cervelloni per il caso (b)! <IMG SRC="images/forum/icons/icon_smile.gif">

DB85 · Messaggio da **DB85** » 01 gen 1970, 01:33

Per me, riguardo al secondo punto, visto che ha un margine di 5 giorni, può utilizzare ogni subset per 5 bottiglie, dunque
 5*2n > 200 --> 2n > 40 --> n=6.
 
 P.S.: Questa è una \"intuizione\" avuta di domenica mattina, dopo la sbornia del sabato sera e i tutte le sue conseguenze psico-fisiche: non flagellatemi se è errata...
 
 P.S.2: Certo questo \"tale\" dovrebbe distinfestare la cantina!
 ---
 \"Le vite degli uomini famosi ci ricordano
 Che possiamo rendere sublimi le noste esistenze
 E, morendo, lasciare dietro di noi
 Le nostre impronte sulle sabbie del tempo\"
 Henry Wadsworth Longfellow
 
 EDIT: Aarrgghh, la citazione!
 [ Questo Messaggio è stato Modificato da: DB85 il 17-10-2004 10:08 ]

NicolasBourbaki · Messaggio da **NicolasBourbaki** » 01 gen 1970, 01:33

Per il momento mi limito ad indicare la mia soluzione della parte a) del problema.
 La risposta di Franchifis,infatti,è corretta ,ma non completa dato che il suo ragionamento mostra che il problema non è risolubile per t<8 (t indica il numero di topi),ma non che per t=8 esiste effettivamente una soluzione del problema dato.
 In altri termini è vero che con k topi si possono costruire 2^k gruppi(distinti) di topi,ma la costruzione di questi gruppi,benchè semplice,non mi pare scontata.
 -Parte Prima:il problema non è risolubile per t<8.Se ad ogni topo associamo una lettera (V per vivo,M per morto) abbiamo con k topi 2^k distinte configurazioni.
 Ma il problema è risolubile solo per 2^k>200 ovvero per K>=8.Infatti per k<8 (ad es. per K=7)si ha che,per il pricipio dei cassetti,ad ogni configurazione (ovvero per ogni possibile esito dell\'esperimento)corrispondono più bottiglie,sicchè non si potrà in generale determinare quella avvelenata.
 -Parte Seconda<IMG SRC="images/forum/icons/icon_razz.gif">er K=8 il problema è risolubile.Infatti si possono costruire 200 insiemi distinti di topi,ognuno posto in corrispondenza biunivoca con una data bottiglia.La costruzione dei gruppi può avvenire nel modo seguente:
 -bott.200 -insieme vuoto
 -bott.da 1 a 8 -topi singoli
 -bott.da 9 a 37 -coppie di topi
 -bott.da 38 a 94-terne di topi
 -bott.da 95 a 165-quaterne di topi
 -bott.da 166 a 199-cinquine di topi (ne avanzo).
 I dettagli sono abbastanza banali,basta qualche ovvio binomiale.
 Fra un po\' arriva la soluzione del b).
 Buona domenica,enjoy the forum!!

matthewtrager · Messaggio da **matthewtrager** » 01 gen 1970, 01:33

La soluzione di Nicolas e\' giusta, anche se forse la costruzione poteva essere fatta in un modo un po\' piu\' semplice... pero\' non ve la voglio dire prima che venga risolto il secondo. <IMG SRC="images/forum/icons/icon_razz.gif">
 
 ciao!

DB85 · Messaggio da **DB85** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-10-17 11:34, matthewtrager wrote:
 pero\' non ve la voglio dire prima che venga risolto il secondo. <IMG SRC="images/forum/icons/icon_razz.gif">
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Devo presumere che la mia (ipo)tesi precedente sia errata? [ Questo Messaggio è stato Modificato da: DB85 il 17-10-2004 13:00 ]

matthewtrager · Messaggio da **matthewtrager** » 01 gen 1970, 01:33

si\' la tua ipotesi e\' errata... comunque anche se fosse giusta, avresti fatto lo stesso errore di Franchifis, cioe\' avresti dimostrato che per n<6 non e\' possibile, ma non hai trovato una configurazione che sia valida per n=6...

cekko · Messaggio da **cekko** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-10-17 11:16, NicolasBourbaki wrote:
 -bott.200 -insieme vuoto
 -bott.da 1 a 8 -topi singoli
 -bott.da 9 a 37 -coppie di topi
 -bott.da 38 a 94-terne di topi
 -bott.da 95 a 165-quaterne di topi
 -bott.da 166 a 199-cinquine di topi (ne avanzo).
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 se non sbaglio sarebbero 1-8, 9-36, 37-92, 93-162, 163-199 [ Questo Messaggio è stato Modificato da: cekko il 17-10-2004 18:13 ]

DB85 · Messaggio da **DB85** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-10-17 18:10, matthewtrager wrote:
 si\' la tua ipotesi e\' errata... comunque anche se fosse giusta, avresti fatto lo stesso errore di Franchifis, cioe\' avresti dimostrato che per n<6 non e\' possibile, ma non hai trovato una configurazione che sia valida per n=6...
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 Cioè, aspetta, non ho capito: il tuo post è alquanto controverso. Il risultato è giusto ma devo trovare una configurazione? Oppure il risultato è errato in sé?
 
 P.S.: Questo è il messaggio della paura... <IMG SRC="images/forum/icons/icon_biggrin.gif">
 EDIT: Dimenticavo... [ Questo Messaggio è stato Modificato da: DB85 il 17-10-2004 18:32 ]

matthewtrager · Messaggio da **matthewtrager** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-10-17 18:26, DB85 wrote:
 
 Cioè, aspetta, non ho capito: il tuo post è alquanto controverso. Il risultato è giusto ma devo trovare una configurazione? Oppure il risultato è errato in sé?
 
 [ Questo Messaggio è stato Modificato da: DB85 il 17-10-2004 18:32 ]
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 no, il risultato e\' anche sbagliato. dicevo che in ogni caso non hai trovato una configurazione...

cekko · Messaggio da **cekko** » 01 gen 1970, 01:33

con 5 topi è possibile.
 raggruppo le bottiglie in 100 coppie, a 2 a 2 disgiunte.
 in ognuno dei primi 4 giorni provo 25 gruppi con il metodo già illustrato da nicolas.
 2^5=32. a questi tolgo l\'insieme vuoto e l\'insieme fatto da tutti e 5 i topi.
 ne rimangono 30, più che sufficienti.
 il 5° giorno faccio provare a tutti i topi ciascuna prima bottiglia di ogni coppia.
 questo sistema funziona perché con il procedimento dei primi 4 giorni trovo la coppia che contiene la bottiglia avvelenata; poiché non si dà nessuna coppia a tutti i topi, ne rimane almeno uno.
 
 tento di dimostrare che 5 è il minimo.
 2^4=16, quindi non posso testare più di 14 gruppi al giorno (l\'insieme vuoto non dà nessuna informazione e quello identità non assicura di lasciare topi). poi mi servirebbe almeno un giorno per trovare la bottiglia all\'interno del gruppo.
 se destinassi i primi 4 giorni alla scoperta del gruppo, potrei testare al massimo 56 gruppi, quindi c\'è almeno qualche gruppo da almeno 4. è impossibile trovare la bottiglia nel 5° giorno.
 anche togliendo gli insiemi di 3, in modo che rimangano almeno 2 topi, la situazione non migliora: non so quali rimangono.
 se destinassi il 4° e il 5° giorno alla scoperta della bottiglia nel gruppo potrei fare i gruppi di 3, ma in almeno un giorno dovrei fare almeno 23 gruppi, impossibile.
 se destinassi solo i primi 2 giorni alla scoperta del gruppo, potrei fare i gruppi di 4, ma avrei i gruppi di 25, impossibile.

MASSO · Messaggio da **MASSO** » 01 gen 1970, 01:33

quote/
 il 5° giorno faccio provare a tutti i topi ciascuna prima bottiglia di ogni coppia.
 questo sistema funziona perché con il procedimento dei primi 4 giorni trovo la coppia che contiene la bottiglia avvelenata; poiché non si dà nessuna coppia a tutti i topi, ne rimane almeno uno. //
 Questo sistema non mi pare funzionare nel caso esistesse un topo cosi sfigato da bere due volte il vino avvelenato; ma potrei aver compreso male;
 inoltre mi sfugge il motivo per cui il tentativo di soluzione di DB85 (purche incompleta) sia da considerarsi errata, attendo chiarimenti
 <IMG SRC="images/forum/icons/icon_confused.gif">
 ---- L\'Italia quattro anni fa era sull\'orlo del baratro...da allora abbiamo fatto un gran passo avanti---- <IMG SRC="images/forum/icons/icon_biggrin.gif">

cekko · Messaggio da **cekko** » 01 gen 1970, 01:33

<TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD>Quote:<HR></TD></TR><TR><TD><BLOCKQUOTE>
 On 2004-10-18 16:09, MASSO wrote:
 quote/
 il 5° giorno faccio provare a tutti i topi ciascuna prima bottiglia di ogni coppia.
 questo sistema funziona perché con il procedimento dei primi 4 giorni trovo la coppia che contiene la bottiglia avvelenata; poiché non si dà nessuna coppia a tutti i topi, ne rimane almeno uno. //
 Questo sistema non mi pare funzionare nel caso esistesse un topo cosi sfigato da bere due volte il vino avvelenato; ma potrei aver compreso male;
 </BLOCKQUOTE></TD></TR><TR><TD><HR></TD></TR></TABLE>
 
 potrei aver sbagliato, ma a me pare che funzioni.
 in un giorno tra il 31°, 32°, 33° e il 34° giorno muoiono k topi, con k tra 1 e 4 (non c\'è una bottiglia da cui bevono tutti e 5). in questo modo capisci in quale delle 100 coppie c\'è la bottiglia avvelenata.
 se i 5-k non muoiono nel 35° giorno sai che la bottiglia era la seconda della coppia che hai prima determinato. se muoiono era la prima.

matthewtrager · Messaggio da **matthewtrager** » 01 gen 1970, 01:33

allora, non mi sono messo a leggere attentamente la dimostrazione di cekko, ma il risultato e\' sbagliato. Faccio pero\' notare che se la festa la vuole fare dopo 35 giorni, il tipo ha a disposizioni SEI giorni per dare il vino ai topi (comunque il risultato di cekko e\' sbagliato anche se i giorni fossero 5).
 
 Per quanto riguarda l\'idea di DB85, e\' sbagliato il metodo che usa per \"contare\" quanti insiemi si possono avere...ma non riesco a spiegarlo senza dire l\'idea di base che serve per risolvere il problema...
 
 si tratta solo di vedere tutto nel modo giusto... <IMG SRC="images/forum/icons/icon_wink.gif">

MASSO · Messaggio da **MASSO** » 01 gen 1970, 01:33

@cekko: come previsto avevo capito male il tuo post, sorry
 @matthewtrager: il quesito b si fa veramente interessante, ci penserò su anche se ero convinto che l\'insieme delle parti di A fosse una buona idea <IMG SRC="images/forum/icons/icon_frown.gif"> sob sob <IMG SRC="images/forum/icons/icon_eek.gif">