[?] bottiglia avvelenata

Vuoi proporre i tuoi esercizi? Qui puoi farlo!!

Moderatore: tutor

matthewtrager
Messaggi: 132
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

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?
<BR>
<BR>b) e se invece la festa la volesse fare dopo 35 giorni?
<BR>
<BR>ciao!

Avatar utente
Franchifis
Messaggi: 149
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da Franchifis » 01 gen 1970, 01:33

Caso semplice:
<BR>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.
<BR>
<BR>Adesso tocca ai cervelloni per il caso (b)! <IMG SRC="images/forum/icons/icon_smile.gif">

DB85
Messaggi: 145
Iscritto il: 01 gen 1970, 01:00
Contatta:

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 <!-- BBCode Start --><I>subset</I><!-- BBCode End --> per 5 bottiglie, dunque
<BR>5*2<sup>n</sup> > 200 --> 2<sup>n</sup> > 40 --> n=6.
<BR>
<BR>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...
<BR>
<BR>P.S.2: Certo questo \"tale\" dovrebbe distinfestare la cantina!
<BR>---
<BR>\"Le vite degli uomini famosi ci ricordano
<BR>Che possiamo rendere sublimi le noste esistenze
<BR>E, morendo, lasciare dietro di noi
<BR>Le nostre impronte sulle sabbie del tempo\"
<BR><!-- BBCode Start --><I>Henry Wadsworth Longfellow</I><!-- BBCode End -->
<BR>
<BR>EDIT: Aarrgghh, la citazione!
<BR><BR><BR>[ Questo Messaggio è stato Modificato da: DB85 il 17-10-2004 10:08 ]
"Le vite degli uomini famosi ci ricordano
Che possiamo rendere sublimi le nostre esistenze
E, morendo, lasciare dietro di noi
Le nostre impronte sulle sabbie del tempo"
Henry Wadsworth Longfellow

Avatar utente
NicolasBourbaki
Messaggi: 56
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da NicolasBourbaki » 01 gen 1970, 01:33

Per il momento mi limito ad indicare la mia soluzione della parte a) del problema.
<BR>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.
<BR>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.
<BR>-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.
<BR>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.
<BR>-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:
<BR>-bott.200 -insieme vuoto
<BR>-bott.da 1 a 8 -topi singoli
<BR>-bott.da 9 a 37 -coppie di topi
<BR>-bott.da 38 a 94-terne di topi
<BR>-bott.da 95 a 165-quaterne di topi
<BR>-bott.da 166 a 199-cinquine di topi (ne avanzo).
<BR>I dettagli sono abbastanza banali,basta qualche ovvio binomiale.
<BR>Fra un po\' arriva la soluzione del b).
<BR>Buona domenica,enjoy the forum!!

matthewtrager
Messaggi: 132
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

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">
<BR>
<BR>ciao!

DB85
Messaggi: 145
Iscritto il: 01 gen 1970, 01:00
Contatta:

Messaggio da DB85 » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-10-17 11:34, matthewtrager wrote:
<BR>pero\' non ve la voglio dire prima che venga risolto il secondo. <IMG SRC="images/forum/icons/icon_razz.gif">
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Devo presumere che la mia (ipo)tesi precedente sia errata?<BR><BR>[ Questo Messaggio è stato Modificato da: DB85 il 17-10-2004 13:00 ]
"Le vite degli uomini famosi ci ricordano
Che possiamo rendere sublimi le nostre esistenze
E, morendo, lasciare dietro di noi
Le nostre impronte sulle sabbie del tempo"
Henry Wadsworth Longfellow

matthewtrager
Messaggi: 132
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

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
Messaggi: 196
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da cekko » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-10-17 11:16, NicolasBourbaki wrote:
<BR>-bott.200 -insieme vuoto
<BR>-bott.da 1 a 8 -topi singoli
<BR>-bott.da 9 a 37 -coppie di topi
<BR>-bott.da 38 a 94-terne di topi
<BR>-bott.da 95 a 165-quaterne di topi
<BR>-bott.da 166 a 199-cinquine di topi (ne avanzo).
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>se non sbaglio sarebbero 1-8, 9-36, 37-92, 93-162, 163-199<BR><BR>[ Questo Messaggio è stato Modificato da: cekko il 17-10-2004 18:13 ]
"...e d'un tratto capii che il pensare è per gli stupidi, mentre i cervelluti si affidano all'ispirazione e a quello che il buon Bog manda loro".
Alex, Arancia Meccanica.

DB85
Messaggi: 145
Iscritto il: 01 gen 1970, 01:00
Contatta:

Messaggio da DB85 » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-10-17 18:10, matthewtrager wrote:
<BR>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...
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>Cioè, aspetta, non ho capito: il tuo post è alquanto controverso. Il risultato è giusto ma devo trovare una configurazione? Oppure il risultato è errato in sé?
<BR>
<BR>P.S.: Questo è il messaggio della paura... <IMG SRC="images/forum/icons/icon_biggrin.gif">
<BR>EDIT: Dimenticavo...<BR><BR>[ Questo Messaggio è stato Modificato da: DB85 il 17-10-2004 18:32 ]
"Le vite degli uomini famosi ci ricordano
Che possiamo rendere sublimi le nostre esistenze
E, morendo, lasciare dietro di noi
Le nostre impronte sulle sabbie del tempo"
Henry Wadsworth Longfellow

matthewtrager
Messaggi: 132
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da matthewtrager » 01 gen 1970, 01:33

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

cekko
Messaggi: 196
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da cekko » 01 gen 1970, 01:33

con 5 topi è possibile.
<BR>raggruppo le bottiglie in 100 coppie, a 2 a 2 disgiunte.
<BR>in ognuno dei primi 4 giorni provo 25 gruppi con il metodo già illustrato da nicolas.
<BR>2^5=32. a questi tolgo l\'insieme vuoto e l\'insieme fatto da tutti e 5 i topi.
<BR>ne rimangono 30, più che sufficienti.
<BR>il 5° giorno faccio provare a tutti i topi ciascuna prima bottiglia di ogni coppia.
<BR>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.
<BR>
<BR>tento di dimostrare che 5 è il minimo.
<BR>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.
<BR>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.
<BR>anche togliendo gli insiemi di 3, in modo che rimangano almeno 2 topi, la situazione non migliora: non so quali rimangono.
<BR>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.
<BR>se destinassi solo i primi 2 giorni alla scoperta del gruppo, potrei fare i gruppi di 4, ma avrei i gruppi di 25, impossibile.
"...e d'un tratto capii che il pensare è per gli stupidi, mentre i cervelluti si affidano all'ispirazione e a quello che il buon Bog manda loro".
Alex, Arancia Meccanica.

Avatar utente
MASSO
Messaggi: 134
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza\Pisa

Messaggio da MASSO » 01 gen 1970, 01:33

quote/
<BR>il 5° giorno faccio provare a tutti i topi ciascuna prima bottiglia di ogni coppia.
<BR>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. //
<BR>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;
<BR>inoltre mi sfugge il motivo per cui il tentativo di soluzione di DB85 (purche incompleta) sia da considerarsi errata, attendo chiarimenti
<BR> <IMG SRC="images/forum/icons/icon_confused.gif">
<BR>---- 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
Messaggi: 196
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

Messaggio da cekko » 01 gen 1970, 01:33

<!-- BBCode Quote Start --><TABLE BORDER=0 ALIGN=CENTER WIDTH=85%><TR><TD><font size=-1>Quote:</font><HR></TD></TR><TR><TD><FONT SIZE=-1><BLOCKQUOTE>
<BR>On 2004-10-18 16:09, MASSO wrote:
<BR>quote/
<BR>il 5° giorno faccio provare a tutti i topi ciascuna prima bottiglia di ogni coppia.
<BR>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. //
<BR>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;
<BR></BLOCKQUOTE></FONT></TD></TR><TR><TD><HR></TD></TR></TABLE><!-- BBCode Quote End -->
<BR>
<BR>potrei aver sbagliato, ma a me pare che funzioni.
<BR>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.
<BR>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.
"...e d'un tratto capii che il pensare è per gli stupidi, mentre i cervelluti si affidano all'ispirazione e a quello che il buon Bog manda loro".
Alex, Arancia Meccanica.

matthewtrager
Messaggi: 132
Iscritto il: 01 gen 1970, 01:00
Località: Pisa

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).
<BR>
<BR>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...
<BR>
<BR>si tratta solo di vedere tutto nel modo giusto... <IMG SRC="images/forum/icons/icon_wink.gif">

Avatar utente
MASSO
Messaggi: 134
Iscritto il: 01 gen 1970, 01:00
Località: Piacenza\Pisa

Messaggio da MASSO » 01 gen 1970, 01:33

@cekko: come previsto avevo capito male il tuo post, sorry
<BR>@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">

Bloccato