Le monete di Paperone

[RC30]

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.........).

[mvc76]

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...... 

.....Ho vinto qualche cosa? 


mvc76

P.S: e vi risparmio anche di aspettare 1 mese 

[Webbo]

peccato che la moneta falsa possa essere anche più leggera e quindi essere tra quelle che hai scartato nella prima pesata...

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...... 

.....Ho vinto qualche cosa? 


mvc76

P.S: e vi risparmio anche di aspettare 1 mese 

[gianca charly]

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

[mvc76]

Quanto hai ragione! Mi sento particolarmente ignorante!


....magari è ora che chiudo l'ufficio e vado a casa!


mvc76

peccato che la moneta falsa possa essere anche più leggera e quindi essere tra quelle che hai scartato nella prima pesata...

[gianca charly]

questo giochino mi sta rendendo nervoso   ma me gusta...
gianca charly

[RC30]

questo giochino mi sta rendendo nervoso   ma me gusta...
gianca charly

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)..........................................

[gianca charly]

in 4 tentativi ci sono riuscito anche io dividendole per 3 a 3
gianca charly

[Webbo]

ragazzi, la risposta è matematica e molto complessa...
non per niente è stata oggetto di discussione di un matematico.

[Crea]

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 

[RC30]

-- 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.

[gianpivr]

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... 

[Crea]

-- 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....

[gianpivr]

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...

[gbking]

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