Problema delle 12 monete
www.ttdown.com
gruppo di quattro amici, mi propose il problema delle 12 monete.
Al termine della passeggiata dissi a quell'amico di aver tronato la
soluzione. Avevo impiegato poco più
di venti minuti.
Come è noto il problema consiste nell'individuare con solo tre pesate
la moneta falsa tra dodici monete di cui undici buone e dire se più
pesante o più leggera delle altre.
Immaginai una bilancia in cui ponevo quattro monete in un piatto e
quattro nell'altro.
Esaminai prima il caso più semplice e cioe' quello della bilancia in
equilibrio.Per la seconda pesata
pensai di mettere in un piatto della bilancia tre monete buone e
nell'altra tre di quelle non pesate.
Se anche questa volta la bilancia fosse rimasta in equilibrio allora
con la terza pesata mi sarebbe stato facile individuare l'ultima
rimasta confrontandola con una buona.
Se invece la bilancia fosse stata sbilanciata,intanto dal tipo di
sbilanciamento avrei saputo la pesantezza o leggerezza della
moneta.Avrei messo quindi, delle tre monete sospette, una in un piatto
e l'altra nell' altro con conseguente soluzione.....
Veniamo ora al caso più difficile e alla meravigliosa soluzione da me
intuita.
Immaginai di trovarmi di fronte alla bilancia sbilanciata e fuori a
destra della bilancia le quattro monete buone.
Allora pensai di fare una contemporanea traslazione verso sinistra ;
precisamente tre delle quattro monete del piatto di sinistra della
bilancia portate fuori a sinistra,tre delle quattro monete del piatto
di destra portate nel piatto di sinistra e tre delle quattro monete
buone, che si trovavano fuori a destra della bilancia, portate nel
piatto di destra.
La soluzione ora la si ha in pugno, infatti,qualunque delle tre
posizioni conseguentemente assunte dalla bilancia con un semplice
ragionamento logico e con la terza pesata si individua la moneta
falsa.
Le tre posizioni da esaminare sono:
1) posizione invariata ed allora una delle due monete che non sono
state spostate è quella falsa e basta pesare una della due.
2) la bilancia assume la posizione di equilibrio ed allora una delle
tre portate fuori a sinistra è quella falsa e conosco il tipo di
pesantezza o leggerezza e con la terza pesata mettendo una di queste
tre in un piatto e una nell ' altro in ogni caso trovo la falsa.
3)posizione squilibrata opposta, allora quella falsa si trova nelle
tre che dal piatto di destra sono passate a quello di sinistra. Si
prosegue come al caso precedente.
Cosimo
radicale.002
> Nel lontano 1956 un amico di liceo (classico),mentre si passeggiava in
> gruppo di quattro amici, mi propose il problema delle 12 monete.
Si, lo risolsi anch' io. Ma ci impiegai molto di piu' di 20 minuti :-)
Sono lento, e mi confondo facilmente mentre rifletto.
Solo che poi vado *oltre* (almeno con l' immaginazione) e dopo
30 secondi mi chiesi :
Data un bilancia a 2 piatti e tutte le condizioni del gioco,
avendo n monete, qual' e' il numero minimo p = f(n) ; (f : N ->N)
di pesate sufficienti per individuare la moneta diversa ?
Come e' fatta questa f(p) ? Che proprieta' ha ?
E come si puo' astrarre il problema ? Cioe', in realta',
qual' la vera *essenza* di questo algoritmo ?
Purtroppo, la fantasia non basta. Occorre anche la
competenza, e le domande sono cadute nel vuoto.
Eppure, percepisco che la sotto si celi qualcosa di
interessante.
superpollo
> On 11 Apr, 11:03, www.ttdown.com <cosimo_e...@libero.it> wrote:
>> Nel lontano 1956 un amico di liceo (classico),mentre si passeggiava in
>> gruppo di quattro amici, mi propose il problema delle 12 monete.
>
> Si, lo risolsi anch' io. Ma ci impiegai molto di piu' di 20 minuti :-)
> Sono lento, e mi confondo facilmente mentre rifletto.
>
> Solo che poi vado *oltre* (almeno con l' immaginazione) e dopo
> 30 secondi mi chiesi :
>
> Data un bilancia a 2 piatti e tutte le condizioni del gioco,
> avendo n monete, qual' e' il numero minimo p = f(n) ; (f : N ->N)
> di pesate sufficienti per individuare la moneta diversa ?
ho provato a risolvere il problema originariamente postato, nel caso di
2010 monete. ci sono riuscito in 8 pesate, ma mi manca lo spazio per
riportare qui la dimostrazione ;-)
Topo Logico
>> Data un bilancia a 2 piatti e tutte le condizioni del gioco,
>> avendo n monete, qual' e' il numero minimo p = f(n) ; (f : N ->N)
>> di pesate sufficienti per individuare la moneta diversa ?
>
> ho provato a risolvere il problema originariamente postato, nel caso di
> 2010 monete
e te pareva! Ma che ti ha fatto di cosě male 'sto 2010? :D
radicale.002
E ci credo, perche' questa cosa ha a che fare con la divisione in
gruppi,
per cui (GROSSISSIMO modo) e' del tipo 2^p = n, e p cresce quindi
molto lentamente all' aumetare di n.
superpollo
in effetti mi pare che p abbia proprio andamento logaritmico...
www.ttdown.com
Il numero di pesate per individuare la moneta falsa tra n monete è
dato da :
p = 12 * 3^(n-3) ma si può avere anche
p = log(in base 3) di 9/4 * n
radicale 004
>Il numero di pesate per individuare la moneta falsa
>tra n monete e' dato da :
>p = 12 * 3^(n-3)
Non credo proprio, visto che per n = 12
p = 12 * 3^(9) = 236.196
:-)
www.ttdown.com
wrote:
con n pesate si può individuare una moneta falsa tra
12 * 3^(n-3) monete (individuando anche se più leggera o più pesante).
Cosi, per esempio, con quattro pesate si può individuare la falsa tra
36 monete.
superpollo
secondo la tua espressione, quante pesate ci vogliono per 10000 monete?
come puoi esprimere 10000 mediante la tua espressione?
www.ttdown.com
wrote:
La formul è datA da : p = log(base 3) n*9/4
bisogna vedere se viene un numero intero , altrimenti avvicinarsi per
difetto e per eccesso e scegliere quella per eccesso.
superpollo
>>> 12 * 3^(n-3) monete (individuando anche se piů leggera o piů pesante).
>>> Cosi, per esempio, con quattro pesate si puň individuare la falsa tra
>>> 36 monete.
>> secondo la tua espressione, quante pesate ci vogliono per 10000 monete?
>> come puoi esprimere 10000 mediante la tua espressione?
> bisogna vedere se viene un numero intero , altrimenti avvicinarsi per
> difetto e per eccesso e scegliere quella per eccesso.
non concordo.
la tua formula fornisce 4.04 con n=38, pertanto ("scegliere quella per
eccesso") 5 pesate; a me risultano sufficienti 4 pesate.
www.ttdown.com
wrote:
>>>> con n pesate si può individuare una moneta falsa tra
>>>> 12 * 3^(n-3) monete (individuando anche se più leggera o più pesante).
>>>> Cosi, per esempio, con quattro pesate si può individuare la falsa tra
>>>> 36 monete.
>>> secondo la tua espressione, quante pesate ci vogliono per 10000 monete?
>>> come puoi esprimere 10000 mediante la tua espressione?
>> La formul è datA da : p = log(base 3) n*9/4
>> bisogna vedere se viene un numero intero , altrimenti avvicinarsi per
>> difetto e per eccesso e scegliere quella per eccesso.
>
>non concordo.
>
>la tua formula fornisce 4.04 con n=38, pertanto ("scegliere quella per
>eccesso") 5 pesate; a me risultano sufficienti 4 pesate.
Ti dispiace dirmi come fai a individuare una moneta falsa (e
specificare anche la sua pesantezza) tra 38 monete?
ciao
Cosimo
superpollo
se con "specificare anche la sua pesantezza" intendi specificare se la
falsa e' piu' pesante o piu' leggera delle vere, allora si', mi bastano
4 pesate. ora pero' non ho tempo :-( , stasera o domani ti posto la
procedura.
bye
radicale 001
>ora pero' non ho tempo :-(, stasera o domani ti posto
>la procedura.
Ma questa procedura puo' essere
descritta tramite un algoritmo che
dipende solo da n ?
p = f(n).
Come ? (aspetto stasera o domani). :-)
superpollo
in realta' mi bastano 4 pesate addirittura per *39* monete!
dividi le 39 monete in tre gruppi di 13: A B C.
occupiamoci dei gruppi A e B.
*prima* pesata: se A=B allora la falsa (MF) si trova in C.
usiamo una moneta buona (da A oppure B) come campione, chiamiamola MB.
dividiamo C in tre gruppi: D E F da 5 4 4.
*seconda* pesata: se D>E+MB allora MF si trova o in D oppure in E a
seconda che MF sia + pesante o + leggera di MB.
suddividiamo ora D in G H da 4 e 1, e E in I L da 2 2.
suddividiamo G in M N da 2 2, e I in P Q da 1 1.
*terza* pesata: se M+P>N+Q allora la falsa e' in M oppure e' in Q.
quindi rimangono 3 monete da controllare.
suddividiamo M in R S da 1 1.
*quarta* pesata: R=S oppure R>S oppure R<S e in ciascun caso determino
la MF e ovviamente stabilisco se MF>MB oppure MF<MB.
poi ci sono le varianti, ad esempio D<E+MB ma si svolgono analogamente.
bye
radicale.002
> dividi le 39 monete in tre gruppi di 13: A B C.
(omissis)
Ma questo risolve un caso particolare : n = 39
Sei in grado di sviluppare un *algoritmo* che dipende
solo da n ? (chiedo, eh ..)
superpollo
l'idea generale e' un'estensione del metodo che ho esposto, ma non ho
abbastanza competenze "informatiche" per sviluppare per filo e per segno
un algoritmo, intendo formalmente.
o meglio: forse ci riuscirei pure, ma ci perderei sicuramente tre
quattro giorni, che non ho.
www.ttdown.com
Io non credo che con tre sole pesate si possa individuare la moneta
falsa tra tredici monete dovendo individuare anche se leggera o
pesante.
Non ha senso dire che si conosce in partenza che la moneta falsa
sia più leggera (oppure più pesante) perchè questo presuppone
che ci sia stata una precedente pesata che non viene considerata.
Facendo riferimento alla dimostrazione da me riportata per le 12
monete, per avere una particolare formula generale, ho immaginato di
avere 12 sacchetti in ognuno dei quali ho messo tre monete.
Cosl le monete sono 36 .Dunque con tre pesate individuo il sacchetto
contenente tre monete e la sua leggerezza. Mi basta allora una
ulteriore pesata per individuare la moneta tra le 3 del sacchetto.
Continuando con lo stesso ragionamento , immagino ora di avere
dodici sacchi più grandi in ciascuno dei quali metto tre sacchetti
contenenti ciascuno tre monete e cosl avrò 12 * 3^2 = 108 monete
ed ora le pesate sono 3 + 2.
Continuando con il metodo delle scatole cinesi posso affermare che
per 12 * 3^n monete ho bisogno di 3 + n pesate .
Indicando con m il numero delle monete e con p il numero delle
pesate , posso scrivere:
m = 12 * 3^ (p-3)
e con facili passaggi :
m * 9/4 = 3^p
e passando a logaritmi di base 3
p = log(base 3) m*9/4
Ciao
Cosimo
F.M.Arouet
>
> dividi le 39 monete in tre gruppi di 13: A B C.
>
> occupiamoci dei gruppi A e B.
>
> *prima* pesata: se A=B allora la falsa (MF) si trova in C.
Manca la soluzione del caso A>B.
Ciao.Fabio.
superpollo
in tal caso ovviamente MF si trova in A oppure B. con al piu' altre tre
pesate la trovi: prova!
superpollo
> On Thu, 22 Apr 2010 11:33:18 -0700 (PDT), "radicale.002"
> <radica...@gmail.com> wrote:
>
>> On 22 Apr, 20:10, superpollo <ute...@esempio.net> wrote:
>>
>>> dividi le 39 monete in tre gruppi di 13: A B C.
>> (omissis)
>>
>> Ma questo risolve un caso particolare : n = 39
>> Sei in grado di sviluppare un *algoritmo* che dipende
>> solo da n ? (chiedo, eh ..)
>>
> Io non credo che con tre sole pesate si possa individuare la moneta
> falsa tra tredici monete dovendo individuare anche se leggera o
> pesante.
infatti ce ne vogliono quattro (o per lo meno: *io* non riesco in meno
di quattro).
radicale 001
> poi ci sono le varianti, ad esempio D<E+MB ma si svolgono analogamente.
Gia !
Per ogni numero n dato di monete, esiste una suddivisione
particolarmente "paracula" che minimizza il numero di pesate.
Il problema e' che per ogni n bisogna trovarla a naso !
superpollo
no, credo che ci sia il modo di "sistematizzare" la scelta, ma come gia'
detto me ne manca il tempo.
bye
radicale 001
> no, credo che ci sia il modo di "sistematizzare" la scelta, ma come gia'
> detto me ne manca il tempo.
Beh, intendevo : allo stato attuale delle conoscenze ... :-)
F.M.Arouet
> in tal caso ovviamente MF si trova in A oppure B. con al piu' altre tre
> pesate la trovi: prova!
Io non ci riesco. Ti va di spiegare come fai tu?
Ciao.Fabio.
www.ttdown.com
wrote:
Per 10000 monete secondo la formula " m = 12 * 3^(p-3) " dovrebbero
bastare 10 pesate ma è difficile dire come procedere mentre con dodici
pesate ti posso dire come fare.Infatti per 10 monete bastano 3 pesate
e disponendo di dieci sacchi in ciascuno dei quali metto dieci
sacchetti con dentro altri dieci sacchettini in ciascuno dei quali
metto dieci monete avrò sistemato in tutto 10000 monete.
Con tre pesate individuo il sacco più grosso e indiniduo pure la
leggerezza o pesantezza. Poi procedo con altre tre perate per
individuare in sacchetto di seconda grandezza e poi altre tre
pesate per il sacchettino e poi altre tre per le dieci monete. In
totale 12 pesate.
La tua dimostrazione delle tredici monete non è completa.
Manca il caso A>B.
ciao.
Cosimo.
superpollo
si anch'io credo che 10 pesate siano sufficienti.
> pesate ti posso dire come fare.Infatti per 10 monete bastano 3 pesate
> e disponendo di dieci sacchi in ciascuno dei quali metto dieci
> sacchetti con dentro altri dieci sacchettini in ciascuno dei quali
> metto dieci monete avrò sistemato in tutto 10000 monete.
> Con tre pesate individuo il sacco più grosso e indiniduo pure la
> leggerezza o pesantezza. Poi procedo con altre tre perate per
> individuare in sacchetto di seconda grandezza e poi altre tre
> pesate per il sacchettino e poi altre tre per le dieci monete. In
> totale 12 pesate.
> La tua dimostrazione delle tredici monete non è completa.
> Manca il caso A>B.
si lo so. sto cercando pero' di trovare un algoritmo generale, piuttosto
che risolvere i casi particolari... mi ci vuole tempo, almeno un mesetto
:-) perche' ci lavoro nei ritagli di tempo (poco) che ho. :-(
bye