Provate a risolvere l'enigma:
Paperon de Paperoni ha dodici monete tra le quali una è falsa, si differenzia dalle altre dal peso, sa che è o più pesante o più leggera.
Ha a disposizione una bilancia con due piatti, con tre pesate (con le quali confronta tra di loro le monete) riesce a trovare la moneta falsa ed a stabilire se è più pesante o più leggera delle altre.
Come fa?
Il quesito fu pubblicato su un Focus di qualche anno fa, verrà riproposto nel numero che uscirà il 15 Aprile, quindi avrete circa un mesetto di tempo per risolverlo.
Buon divertimento.
Piero
P.S. Nel caso aveste il vecchio numero, allora siete pregati di astenervi dal dare la soluzione >:( (furbacchioni.........:D).
Premetto che non ho mai sentito il quesito e nemmeno la soluzione, ma non è difficile arrivarci:
- prendiamo le 12 monete e mettiamone 6 su un piatto e 6 sull'altro;
- uno dei due è sicuramente più pesante (perché contiene la moneta che pesa di più)
- di queste 6 monete ne mettiamo 3 su un piatto e 3 sull'altro;
- teniamo le 3 che pesano di più;
- ora mettiamo 1 moneta su un piatto e 1 sull'altro;
da quì: se una pesa di più abbiamo risolto il gioco, se pesano uguale la moneta che abbiamo in mano è quella più pesante...... [primo ]
.....Ho vinto qualche cosa? ;D ;D ;D
mvc76
P.S: e vi risparmio anche di aspettare 1 mese ::)
peccato che la moneta falsa possa essere anche più leggera e quindi essere tra quelle che hai scartato nella prima pesata...
Citazione di: mvc76 il Marzo 20, 2007, 19:35:00 PM
Premetto che non ho mai sentito il quesito e nemmeno la soluzione, ma non è difficile arrivarci:
- prendiamo le 12 monete e mettiamone 6 su un piatto e 6 sull'altro;
- uno dei due è sicuramente più pesante (perché contiene la moneta che pesa di più)
- di queste 6 monete ne mettiamo 3 su un piatto e 3 sull'altro;
- teniamo le 3 che pesano di più;
- ora mettiamo 1 moneta su un piatto e 1 sull'altro;
da quì: se una pesa di più abbiamo risolto il gioco, se pesano uguale la moneta che abbiamo in mano è quella più pesante...... [primo ]
.....Ho vinto qualche cosa? ;D ;D ;D
mvc76
P.S: e vi risparmio anche di aspettare 1 mese ::)
e no se e piu leggera? non ci siamo a questo ci avevo pensato anche io...
sono arrivato secondo ti ha gia risposto il web...
gianca charly
Quanto hai ragione! Mi sento particolarmente ignorante!
:botte: :botte: :botte:
....magari è ora che chiudo l'ufficio e vado a casa!
mvc76
Citazione di: Webmaster il Marzo 20, 2007, 19:40:17 PM
peccato che la moneta falsa possa essere anche più leggera e quindi essere tra quelle che hai scartato nella prima pesata...
questo giochino mi sta rendendo nervoso :angry2: ma me gusta... :)
gianca charly
Citazione di: gianca charly il Marzo 20, 2007, 19:52:55 PM
questo giochino mi sta rendendo nervoso :angry2: ma me gusta... :)
gianca charly
:D :D :D :D Io in cinque anni di saltuari tentativi, nei quali ho coinvolto a più riprese i miei colleghi d'ufficio, non sono mai riuscito a risolverlo in tre pesate (in quattro si, ma non conta)..........................................
in 4 tentativi ci sono riuscito anche io dividendole per 3 a 3
gianca charly
ragazzi, la risposta è matematica e molto complessa...
non per niente è stata oggetto di discussione di un matematico.
1 tentativo (gli altri arrivano)
forse ci sono,
-divide il gruppo di 12 in gruppetti da 4
- ne pesa due
-se il peso è uguale la moneta falsa è nel gruppo non pesato...
-- prende le 4 monete restanti e le divide in due gruppetti da 2
-- guarda da che parte pende la bilancia
-- poi scambia due monete a caso dai due piatti
-- se la moneta falsa è più pesante, la bilancia pende sempre dalla parte dove abbiamo messo o lasciato la moneta falsa
-- se la moneta è più leggera la bilancia alza il piatto della moneta falsa anche scambiando le monete
Citazione di: Crea il Marzo 20, 2007, 20:30:15 PM
-- poi scambia due monete a caso dai due piatti
-- se la moneta falsa è più pesante, la bilancia pende sempre dalla parte dove abbiamo messo o lasciato la moneta falsa
-- se la moneta è più leggera la bilancia alza il piatto della moneta falsa anche scambiando le monete
Questa è la
terza pesata.
-Se in quest'ultima hai scambiato due monete uguali, i piatti rimangono così come sono, quindi come fai a stabilire se la falsa pesa di più o di meno?
-Se scambi quella pesante con una normale, allora i piatti si invertiranno, ma come fai a dire che hai scambiato quella pesante? Potresti avere scambiato quella più leggera e il risultato sarebbe stato uguale, i piatti si sarebbero comunque invertiti.........quindi sarebbe necessaria una quarta pesata.
Il vostro errore è che dividete tutti in 2 gruppi, ma in realtà vanno divise in 3 gruppi, perchè la bilancia avendo 2 piatti può dare in realtà tre responsi... dopo cercherò di essere matematicamente più chiaro... ;)
Citazione di: RC30 il Marzo 20, 2007, 20:59:28 PM
Citazione di: Crea il Marzo 20, 2007, 20:30:15 PM
-- poi scambia due monete a caso dai due piatti
-- se la moneta falsa è più pesante, la bilancia pende sempre dalla parte dove abbiamo messo o lasciato la moneta falsa
-- se la moneta è più leggera la bilancia alza il piatto della moneta falsa anche scambiando le monete
Questa è la terza pesata.
-Se in quest'ultima hai scambiato due monete uguali, i piatti rimangono così come sono, quindi come fai a stabilire se la falsa pesa di più o di meno?
-Se scambi quella pesante con una normale, allora i piatti si invertiranno, ma come fai a dire che hai scambiato quella pesante? Potresti avere scambiato quella più leggera e il risultato sarebbe stato uguale, i piatti si sarebbero comunque invertiti.........quindi sarebbe necessaria una quarta pesata.
infatti sta notte mi sono svegliato n un lago di sudore sapendo che la risposta appena data è sbagliata...
... mi 'stà esplodendo il cervello!!!
Rc se ti prendo guarda.... :D
Con un numero n di monete pari a 3^0 (cioè con una moneta) il numero di pesate necessario a individuare la moneta anomala è 0 (notare la coincidenza tra il numero di pesate e l'esponente di 3)...
Con un numero di monete compreso tra 3^0+1 e 3^1 (un modo contorto per dire tra 2 e 3) il numero di pesate è 1 (notate ancora la coincidenza)...
Con un numero di monete compreso tra 3^1+1 e 3^2 (tra 4 e 9) il numero di pesate è 2 (i due numeri succitati continuano a coincidere)...
Con un numero di monete compreso tra 3^2+1 e 3^3 (tra 10 e 27) il numero di pesate è 3.
Quale sarà quindi il numero k di pesate quando il numero n di monete è compreso tra un generico 3^(k-1)+1 e 3^k ?
Ovviamente k!
Come faccio a ricavare k da n ?
Basta notare che k compare sempre a esponente di una potenza in base 3 e dunque per eplicitare k serve il logaritmo in base 3.
Poiché n non è per forza una potenza di 3, il logaritmo in base 3 di n non sarà sempre intero. Ecco quindi che quando tale logaritmo non è intero bisogna prendere l'intero successivo (che è quello che fa la funzione CEIL).
Perché continua a ricorrere il 3?
Perché l'algoritmo atto a individuare la moneta anomala è ricorsivo e si basa sul principio "divide et impera" ovvero prendo le monete, le suddivido in gruppi, peso per individuare il gruppo anomalo e ripeto il procedimento limitandomi al gruppo anomalo. Poco alla volta il gruppo anomalo si riduce alla sola moneta anomala.
Perché dividere in 3 gruppi e non in 2 o 4 o altro?
Perché la bilancia ha 2 piatti ma offre 3 responsi:
la bilancia pende verso un piatto, verso l'altro, verso nessuno dei due.
Quindi con una sola pesata posso distinguere non 2 ma 3 gruppi.
Con 4 o più gruppi non mi basta una singola pesata.
Con 2 gruppi non sfrutto appieno le possibilità della bilancia.
Poiché il procedimento consiste nella ripetuta suddivisione in 3 gruppi l'algoritmo ha efficenza massima quando un gruppo contiene monete in numero uguale a una potenza di 3...
Citazione di: gianpivr il Marzo 21, 2007, 08:11:30 AM
Poiché il procedimento consiste nella ripetuta suddivisione in 3 gruppi l'algoritmo ha efficenza massima quando un gruppo contiene monete in numero uguale a una potenza di 3...
Ottima spiegazione Giampi!
Come prova empirica, si potrebbe cercare la moneta di peso 'diverso' inclusa in un gruppo di 27 monete...
Bastano sempre 3 pesate :)
Ci sono riuscito! :)
Non per niente sono un genio! ;D (scherzo... ci mancherebbe)
Appena ho tempo spiego come!
MY
Per i sommi matematici che non sanno inpiegare il tempo in altri modi durante le giornate uggiose:
http://utenti.quipo.it/base5/introduz/topten.htm (http://utenti.quipo.it/base5/introduz/topten.htm)
Salut
P.S. Il nostro dovrebbe essere il 24
Citazione di: MartY il Marzo 21, 2007, 11:58:18 AM
Appena ho tempo spiego come!
MY
Basta che leggi nella pagina prima... ;)
gianpi, empiricamente ho provato con altre 2 modalità, ed il risultato è sempre lo stesso: 3 pesate e l'enigma si risolve :)
voi sommi matematici ci siete riusciti io mi sento un po ignorante... :( :P
gianca charly
Citazione di: gianpivr il Marzo 21, 2007, 12:51:47 PM
Citazione di: MartY il Marzo 21, 2007, 11:58:18 AM
Appena ho tempo spiego come!
MY
Basta che leggi nella pagina prima... ;)
Ma non c'è la spiegazione di come risolvere il problema, solo la dimostrazione della sua risolvibilità!
Sbrigo un cliente (maledetto) e poi mi dedico all'algoritmo!
MY
C è spiegato come risolverlo anche... ne pesi 8 e il resto vien da sè...
Cmq come detto da gnking ci sono altre vie: ad esempio posso pesare solo 10 monete; poi delle 5 toglierne 1 a caso e pesarne 4 e concludere come da dimostrazione di prima. Logico che la moneta potrebbe essere nelle 2 escluse subito o potrebbe essere quella tolta, ma una volta capito ciò tutto si risolve sempre con la terza pesata
Esatto: 10 + 2 è stata una delle mie prove! :)
Uhm... non mi convice, ma ci ho perso fin troppo tempo.
Cmq... hai considerato il fatto che la moneta falsa possa essere più leggera o più pesante delle altre? Hai considerato il caso peggiore (pesate sempre diverse?)
Per me 10+2 non funziona in 3 pesate!
Allora, il peso, in più o in meno, è indifferente nella partizione 4+4+4: l'importante è che ci sia una differenza 'relativa' rispetto a tutte le altre monete... :)
Nella 10 + 2 invece serve sapere se la moneta falsa è più pesante o più leggera delle altre...
Ipotizzando che la falsa sia + pesante, la 10 + 2 l'ho fatta così:
- Delle 12 monete ne prendi 10 a caso e le pesi (5 in ogni piatto): PRIMA PESATA.
- Se la bilancia resta in pari, allora prendi le 2 monete escluse e le pesi: troverai la falsa in SECONDA PESATA.
- Se la prima pesata indica un gruppo di 5 monete diverso dall'altro, prendi il gruppo più pesante e lo dividi 2+2+1 e fai una SECONDA PESATA con le 2 coppie...
- Idem come sopra: se bilancia in pari, la falsa è la '5a' moneta, se invece 2 monete sono + pesanti delle altre, allora si procede con la TERZA PESATA, per verificare la singola moneta più pesante...
:mattarello:
Invece di lanciarvi in spiegazioni matematiche sulla risolvibilità dell'enigma (il 90% degli utenti l'avete perso per strada già al numero "3^0".......), spiegate piuttosto in modo chiaro qual'è la soluzione, magari con uno schemino tipo:
PRIMA pesata.............
Esito A.........
Esito B.........
SECONDA pesata.........
Esito................eccetera, eccetera e ancora eccetera.............>:(
Citazione di: gbking il Marzo 21, 2007, 17:06:47 PM
.......Nella 10 + 2 invece serve sapere se la moneta falsa è più pesante o più leggera delle altre....
Il peso è un'incognita che influisce sul numero delle pesate.............
Citazione di: gbking il Marzo 21, 2007, 17:06:47 PM
Nella 10 + 2 invece serve sapere se la moneta falsa è più pesante o più leggera delle altre...
Ipotizzando che la falsa sia + pesante, la 10 + 2 l'ho fatta così:
- Delle 12 monete ne prendi 10 a caso e le pesi (5 in ogni piatto): PRIMA PESATA.
- Se la bilancia resta in pari, allora prendi le 2 monete escluse e le pesi: troverai la falsa in SECONDA PESATA.
- Se la prima pesata indica un gruppo di 5 monete diverso dall'altro, prendi il gruppo più pesante e lo dividi 2+2+1 e fai una SECONDA PESATA con le 2 coppie...
- Idem come sopra: se bilancia in pari, la falsa è la '5a' moneta, se invece 2 monete sono + pesanti delle altre, allora si procede con la TERZA PESATA, per verificare la singola moneta più pesante...
Sì, ma ipotizzi che sia più pesante in questa soluzione...
mvc76
Citazione di: mvc76 il Marzo 22, 2007, 09:45:33 AM
Citazione di: gbking il Marzo 21, 2007, 17:06:47 PM
Nella 10 + 2 invece serve sapere se la moneta falsa è più pesante o più leggera delle altre...
Sì, ma ipotizzi che sia più pesante in questa soluzione...
Già, l'ho scritto:
Citazione di: gbking il Marzo 21, 2007, 17:06:47 PM
Nella 10 + 2 invece serve sapere se la moneta falsa è più pesante o più leggera delle altre...
:)
Sì, ma metti che ipotizzi che sia più pesante e invece è più leggera....sei fregato ;D ;D ;D
Con questo non voglio mettere in dubbio che si possa risolvere anche con questa soluzione, ma è un sistema che prevede un'incertezza...se me ne spiegate uno che non prevede ipotesi vi offro una birra (anche 2), che sto giochino mi sta facendo innervosire :)
mvc76
Senza ipotesi c'è il metodo 4+4+4 :)
Citazione di: gbking il Marzo 22, 2007, 09:57:51 AM
Senza ipotesi c'è il metodo 4+4+4 :)
Cioé? Perchè se prendo 2 gruppi da quattro e il peso è diverso alla prima pesata, come faccio a stabilire qual'è il gruppo con la moneta diversa?
mvc76
Devi trovarti 2 gruppi con identico peso... procedere x esclusione :)
Perdonami, ma questa cosa non mi convince del tutto....
....e da bere te lo offro lo stesso
mvc76
Visto che dirla così come vorrebbe rc30 non è semplicissima mi aiuto con le lettere e una fotocopia che mi diede un prof che mi fece un corso di mate e calcolo probabilistico...
Supponiamo che le monete siano ABCDEFGHIJKL. Come primo tentativo, si confrontino ABCD e EFGH.
Si danno tre casi:
(1) ABCD = EFGH. Si confrontino allora IJ e KA.
Di nuovo tre casi:
(1.1) IJ = KA. La moneta diversa è L; la si confronti con A per saperese è piu` pesante o piu` leggera.
(1.2) IJ < KA. Si ha o (I<) o (J<) o (K>). Facciamo il confronto tra AB e IK.
(1.3) IJ > KA. Si ha o (I>) o (J>) o (K<). Procediamo come nel caso precedente a confontare AB e IK.
(2) ABCD > EFGH. La seconda pesata è tra ABE e CDF.
Si hanno di nuovo tre casi:
(2.1) ABE = CDF. Si ha o (G<) o (H<). Si confronti A con G.
(2.2) ABE > CDF. Si ha o (A>) o (B>) o (F<). Si confrontino AF e KL.
(2.3) ABE < CDF. Si ha o (E<) o (C>) o (D>). Si confrontino CE e KL.
(3) ABCD < EFGH. Si risolve come il caso (2)
Ora anche rc30 sarà contento così ha il suo schemino ;) :D :D :D
adesso cerco di capire... ::)
gianca charly
Citazione di: gianpivr il Marzo 22, 2007, 10:29:15 AM
Visto che dirla così come vorrebbe rc30 non è semplicissima mi aiuto con le lettere e una fotocopia che mi diede un prof che mi fece un corso di mate e calcolo probabilistico...
Supponiamo che le monete siano ABCDEFGHIJKL. Come primo tentativo, si confrontino ABCD e EFGH.
Si danno tre casi:
(1) ABCD = EFGH. Si confrontino allora IJ e KA.
Di nuovo tre casi:
(1.1) IJ = KA. La moneta diversa è L; la si confronti con A per saperese è piu` pesante o piu` leggera.
(1.2) IJ < KA. Si ha o (I<) o (J<) o (K>). Facciamo il confronto tra AB e IK.
(1.3) IJ > KA. Si ha o (I>) o (J>) o (K<). Procediamo come nel caso precedente a confontare AB e IK.
(2) ABCD > EFGH. La seconda pesata è tra ABE e CDF.
Si hanno di nuovo tre casi:
(2.1) ABE = CDF. Si ha o (G<) o (H<). Si confronti A con G.
(2.2) ABE > CDF. Si ha o (A>) o (B>) o (F<). Si confrontino AF e KL.
(2.3) ABE < CDF. Si ha o (E<) o (C>) o (D>). Si confrontino CE e KL.
(3) ABCD < EFGH. Si risolve come il caso (2)
Ora anche rc30 sarà contento così ha il suo schemino ;) :D :D :D
Alla prima occasione avanzi :birra: :birra: :birra:
mvc76
Ecco giampivr, ora ci siamo! :)
La mia soluzione prevedeva però di incrociare le monete dei 2 gruppi rimanenti dalla prima pesata e confrontare, ad esempio AB con EF.
Cmq la sostenza è la stessa!
Confermo che il metodo 10+2 non può funzionare.
Saluti, MY