Due indovinelli logici
Su uno strano pianeta esiste un albergo con infinite stanze. Il direttore, anche quando l'albergo è pieno, riesce sempre a trovare posto per i nuovi arrivati, spostando tutti i clienti da una stanza alla successiva. In questo modo si libera la prima stanza. Ma un giorno arrivano all'albergo infiniti clienti. Come fa il direttore a sistemarli tutti?
Ci sono n sacchi di monete d'oro. Ciascun sacco contiene un numero diverso, e non noto, di monete. C'è il sospetto che fra i sacchi ce ne siano alcuni che contengono solo monete finte. Conoscendo il peso di una moneta vera e quello di una moneta finta, com'è possibile, attraverso una sola pesata su una normale bilancia ad un piatto, capire, se ci sono, quali sono i sacchi pieni di monete finte?
Ci sono n sacchi di monete d'oro. Ciascun sacco contiene un numero diverso, e non noto, di monete. C'è il sospetto che fra i sacchi ce ne siano alcuni che contengono solo monete finte. Conoscendo il peso di una moneta vera e quello di una moneta finta, com'è possibile, attraverso una sola pesata su una normale bilancia ad un piatto, capire, se ci sono, quali sono i sacchi pieni di monete finte?
Risposte
quote:
ti sarai accorto che il mio "poco più di mezzo euro" per i 10 sacchi di monete da 1 lira (18/04/2005 - 01:26:48) vale appunto circa 1023 lire [:)]
tony
yep! Cosa credi, con i soldi ci stò attento io!
In effetti ha ragione Pachito. Ingegneristicamente il problema è impossibile, oltre un certo numero di sacchi. Ma qui siamo in un forum di matematica, quindi in teoria ci è permesso risolverlo 
Mi pare che la soluzione l'abbiate trovata. In linea di principio le informazioni sono sufficienti, il problema, come evidenziato (io non c'avevo neanche pensato a dire il vero!) è solo logistico. L'hint di Thomas è corretto. Comunque forse è proprio questa la ragione per cui nell'indovinello iniziale c'era solo un sacco.
Mi pare che la soluzione l'abbiate trovata. In linea di principio le informazioni sono sufficienti, il problema, come evidenziato (io non c'avevo neanche pensato a dire il vero!) è solo logistico. L'hint di Thomas è corretto. Comunque forse è proprio questa la ragione per cui nell'indovinello iniziale c'era solo un sacco.
Mi pare si possa fare anche in un'altra maniera conoscendo, come si dice le testo:
"il peso di una moneta vera e quello di una moneta finta"
ma non lo so generalizzare.
Prendiamo come esempio i 10 sacchi suddetti e supponiamo che il peso di una moneta vera sia 100 e di una finta 99, allora mi bastano 45 monete.
WonderP.
"il peso di una moneta vera e quello di una moneta finta"
ma non lo so generalizzare.
Prendiamo come esempio i 10 sacchi suddetti e supponiamo che il peso di una moneta vera sia 100 e di una finta 99, allora mi bastano 45 monete.
WonderP.
quote:
Originally posted by Pachito
Il fatto che ogni sacco abbia un numero diverso di monete ci induce a pensare che ce n'è almeno uno con n monete, uno con n-1 e così via.
Scusa ma io non sono indotto a pensare questo. I sacchi sono n ma ciascuno contiene un numero non noto di monete, completamente arbitrario, o almeno questo si evince dal testo.
Continuo a pensare che questa versione del problema della singola pesata non ha soluzioni a meno che non si intervenga ponendo limiti al numero di sacchi, al numero di monete contenute o a qualsivoglia ulteriore parametro (è anche possibile riportare il testo alla versione originaria).
Più che altro io cercherei di capire se il problema espresso senza sapere il peso ha come sol che utilizza un minimo numero di monete (sul sacco che ne contiene di più) quella "dalla base 2" (qualcuno la scriva!). Per fare questo credo si debba dimostrare questa
CONGETTURA: scelto un insieme A di k elementi minori o uguali a [2^(k-1)-1], si possono sempre trovare due sottoinsiemi A1 ed A2 di A tali che la somma degli elementi di A1 sia uguale a quella degli elementi di A2.
a me pare vera, ma devo ancora trovare una dim... anzi se la sapete postatela, se trovate un contro-esempio, pure, così non perdo tempo
CONGETTURA: scelto un insieme A di k elementi minori o uguali a [2^(k-1)-1], si possono sempre trovare due sottoinsiemi A1 ed A2 di A tali che la somma degli elementi di A1 sia uguale a quella degli elementi di A2.
a me pare vera, ma devo ancora trovare una dim... anzi se la sapete postatela, se trovate un contro-esempio, pure, così non perdo tempo
Uh, Thomas, non ho la benché minima idea a cosa ti serva questa congettura! Anche io direi così a occhio che è vera, ma credo che tu voglia sottintendere che A1 e A2 devono costituire una partizione di A, o mi sbaglio?
WonderP, come fai con 45 monete??? Non credevo fosse possibile usarne meno che secondo il ragionamento della base 2: i casi possibili infatti sono 2^n (ognuno degli n sacchi può essere vero o falso)! Come hai fatto tu?
Anche io direi così a occhio che è vera, ma credo che tu voglia sottintendere che A1 e A2 devono costituire una partizione di A, o mi sbaglio?WonderP, come fai con 45 monete??? Non credevo fosse possibile usarne meno che secondo il ragionamento della base 2: i casi possibili infatti sono 2^n (ognuno degli n sacchi può essere vero o falso)! Come hai fatto tu?
Mi sembra che siamo tutti d'accordo sul metodo "della base 2".
Il problema è che per essere attuabile c'è bisogno di ipotesi aggiuntive che non vengono menzionate nel testo.
Il problema è che per essere attuabile c'è bisogno di ipotesi aggiuntive che non vengono menzionate nel testo.
quote:
"... Per esempio, sei sicuro che il prob sia risolvibile con 4 sacchi di 1,2,3,4 monete? "
Se per partizione di A intendi A1 U A2 = A (U=unione), no, intendo proprio due qualsiasi sottoinsiemi, senza alcuna restrizione (diversi dall'insieme vuoto però)...
(anche non disgiunti, ma considerarli disgiunti non cambia il problema dato che se due insiemi non disgiunti rispettano le condizioni, togliendo gli elementi comuni troviamo due insiemi disgiunti che rispettano le condizioni)
............
a cosa mi serve? Beh, per risolvere il problema io ho ragionato così. Ammettiamo che una moneta pesi 0 e l'altra 1 (il resto si modifica in fretta). Devo prendere quindi da ogni sacco un pò di monete. Con la bilancia saprò quante monete da 1 ho preso in totale. Quindi devo trovare un modo che associ ad ogni totale una serie diversa di sacchi. Prendere 1,2,4,8,16,... monete da ogni sacco rispetta le condizioni, dato che ad ogni totale basta associare la sua scrittura in base 2 (unica) e trovare quindi da quali sacchi si è preso.
Una sol deve fare lo stesso. Chiamati k1,k2,k3... le monete prese, se un totale risulta "nn ambiguo", ovvero ottenibile con una sola combinazione del k, siamo a posto... Qui entra in gioco la congettura per definire la mia come migliore sol... ma non mi pare facile...
(anche non disgiunti, ma considerarli disgiunti non cambia il problema dato che se due insiemi non disgiunti rispettano le condizioni, togliendo gli elementi comuni troviamo due insiemi disgiunti che rispettano le condizioni)
............
a cosa mi serve? Beh, per risolvere il problema io ho ragionato così. Ammettiamo che una moneta pesi 0 e l'altra 1 (il resto si modifica in fretta). Devo prendere quindi da ogni sacco un pò di monete. Con la bilancia saprò quante monete da 1 ho preso in totale. Quindi devo trovare un modo che associ ad ogni totale una serie diversa di sacchi. Prendere 1,2,4,8,16,... monete da ogni sacco rispetta le condizioni, dato che ad ogni totale basta associare la sua scrittura in base 2 (unica) e trovare quindi da quali sacchi si è preso.
Una sol deve fare lo stesso. Chiamati k1,k2,k3... le monete prese, se un totale risulta "nn ambiguo", ovvero ottenibile con una sola combinazione del k, siamo a posto... Qui entra in gioco la congettura per definire la mia come migliore sol... ma non mi pare facile...
Scusate se rispondo per WonderP. 45 come (ad esmpio): 1 del primo sacco + 2 del secondo + ... + 9 del nono.
Non credo ci siano problemi per la generalizzazione, sempre che ci sia un sacco con almeno n monete, uno con almeno n-1 monete, e così via.
Ciao
Non credo ci siano problemi per la generalizzazione, sempre che ci sia un sacco con almeno n monete, uno con almeno n-1 monete, e così via.
Ciao
Alice, credo che così non funzioni. Se prendiamo i monete dal sacco i-esimo e troviamo che abbiamo 3 monete false nella pesata, non possiamo sapere se il 3° sacco è falso, oppure lo sono il 1° e il 2°.
Secondo me il fatto è che dobbiamo costruire un'applicazione biiettiva che associ l'insieme dei casi possibili a un insieme finito. poiché il primo insieme ha cardinalità 2^n, occorrono 2^n numeri naturali distinti, ossia esattamente quanti se ne ottengono prendendo 2^(i-1) monete dal sacco i-esimo, per i = 1,...,n, e considerando il totale di monete false, che è un numero k che può andare da 0 a 2^n - 1, cioè assumere 2^n valori differenti. Di meno non si può, questo è sufficiente, dunque credo di aver dimostrato che è il procedimento meno dispendioso.
Quanto a Pachito, non ho capito che ipotesi aggiuntive occorrerebbero. Me le spiegheresti?
Secondo me il fatto è che dobbiamo costruire un'applicazione biiettiva che associ l'insieme dei casi possibili a un insieme finito. poiché il primo insieme ha cardinalità 2^n, occorrono 2^n numeri naturali distinti, ossia esattamente quanti se ne ottengono prendendo 2^(i-1) monete dal sacco i-esimo, per i = 1,...,n, e considerando il totale di monete false, che è un numero k che può andare da 0 a 2^n - 1, cioè assumere 2^n valori differenti. Di meno non si può, questo è sufficiente, dunque credo di aver dimostrato che è il procedimento meno dispendioso.
Quanto a Pachito, non ho capito che ipotesi aggiuntive occorrerebbero. Me le spiegheresti?
Thomas: ma se prendo A1 = A2?
Elijah82, avevo letto frettolosamente il testo e saltato diverse risposte. Chiedo scusa. Avevo perso l'ipotesi essenziale che "alcuni sacchi possono contenere monete false". Davo per scontato che fosse uno solo.
Bella variante!
Ciao
Bella variante!
Ciao
quote:
Originally posted by Elijah82
Ci sono n sacchi di monete d'oro. Ciascun sacco contiene un numero diverso, e non noto, di monete. C'è il sospetto che fra i sacchi ce ne siano alcuni che contengono solo monete finte.
Dunque è possibile che i sacchi (supponiamo 4) contengano 1,2,3,4 monete. In questo caso il problema è irrisolvibile.
Come ipotesi aggiuntiva dovresti dire che in un sacco ci sono almeno 2^n monete in un altro 2^(n-1) e così via.
Oppure altra ipotesi che aggiusterebbe tutto è nel dire :
"...C'è il sospetto che fra i sacchi ce ne sia uno che contenga solo monete finte."
Allora l'ipotesi "Ciascun sacco contiene un numero diverso, e non noto, di monete" è sufficiente alla soluzione del problema.
E' infatti possibile prendere una moneta da un sacco, due da un altro, n dall'ennesimo e poi pesare.
(Si potrebbe obiettare che non si conosce a priori il numero di monete
di ciascun sacco e magari nell'n-simo sacco non ci sono n monete, ma questo non è un gran problema...)
Io ho fatto il ragionamento che ha detto alice, ma ho letto male il problema infatti ci sono ALCUNI sacchi e non uno.
WonderP.
WonderP.
poco fa non c'erano questo ultimi post! Il mio PC sta dando i numeri, scusate l'intervento inutile.
WonderP.
WonderP.
Ok, Pachito. Poi, nel discorso, mi pare di aver aggiunto che supponiamo di avere abbastanza monete in ogni sacco
quote:
Originally posted by jack
piccolo scolio(ma si dice così?) al problema 1:
si potranno sempre far alloggiare tutte le persone che verranno?
ciao
be' è passato un po' di tempo (e sembra che l'attenzione sia stata calamitata dal problema 2) quindi propongo la mia soluzione
dal momento che le persone che verranno potranno sempre costituire al più un'infinità numerabile, sarà sempre possibile farle alloggiare, in quanto, attuando il ragionamento di ilyily, sono sempre libere le stanze dispari, che sono un insieme numerabile, e pertanto sono a sufficienza per ospitare tutti gli avventori.
quote:
Originally posted by Elijah82
Thomas: ma se prendo A1 = A2?
Forse non mi sono spiegato. Tu "prendi" l'insieme A.
A1 ed A2 sono due sottoinsiemi di A (che rispettano certe condizioni) di cui BISOGNA DIMOSTRARE l'esistenza... anzi no!, ora ho capito cosa intendi. Beh A1<>A2 è da aggiungere nelle ipotesi, altrimenti la congettura è banale...
quote:
Originally posted by Elijah82
quote:
Originally posted by jack
piccolo scolio(ma si dice così?) al problema 1:
si potranno sempre far alloggiare tutte le persone che verranno?
ciao
be' è passato un po' di tempo (e sembra che l'attenzione sia stata calamitata dal problema 2) quindi propongo la mia soluzione
dal momento che le persone che verranno potranno sempre costituire al più un'infinità numerabile, sarà sempre possibile farle alloggiare, in quanto, attuando il ragionamento di ilyily, sono sempre libere le stanze dispari, che sono un insieme numerabile, e pertanto sono a sufficienza per ospitare tutti gli avventori.
exactly [:)][:)]
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo