Newsgroup: it.hobby.enigmi
Titolo: Monete false e pesate.

Ciao, spero non sia una FAQ:
Una nazione ha deciso di privatizzare il conio delle monete e ha 
affidato il lavoro a N zecche private.
Si sospetta che alcuni di questi coniatori per risparmiare forgino 
monete di peso diverso, ma non si sa quali e quanti sono.
Sapete che tutte le monete false, anche di zecche diverse, hanno lo 
stesso peso.
Avete a disposizione una moneta vera, una bilancia elettronica a un 
piatto che vi fornisce il peso accurato, e un numero illimitato di 
monete da ognuno dei coniatori.
Con tre (3) pesate dovete identificare i falsari.
ciao Dario

Scusate, ho dimenticato lo spoiler :(


Io farei così (non so se c'è un metoto + semplice):
1) peso la moneta vera (peso che chiamo p1)
2) peso N monete (1 da ogni zecca privata) (peso che chiamo p2)
3) peso 2^N - 1 monete (1 dalla prima zecca, 2 dalla seconda, 2^2 dalla
terza.... 2^(N-1) dalla N-esima) (visto che ne ho un numero illimitato ;))
(peso che chiamo p3)
pongo d1 = N*p1 - p2 (d può essere anche negativo);
pongo d2 = (2^N - 1)*p1 - p3;
a questo punto (spero di essere chiaro) considero un numero binario (che
chiamo x), lo pongo inizialmente uguale a 1 ed eseguo ricorsivamente, finchè
non trovo la soluzione (il che, se le ipotesi sono corrette, avverrà prima
che x diventi 2^N), i seguenti punti:
a)  divido x (convertito in decimale) per il numero di cifre di x pari a 1:
se il numero che ne risulta è pari a d2/d1 ho trovato la soluzione (se ad
es. in questo caso il numero binario fosse 100010 i falsari sarebbero la
seconda e la sesta zecca, considerate nell'ordine del punto 3), altrimenti
vado al punto b);
b) incremento x di 1 e torno al punto a);
spero di non aver detto cavolate :)
ciao

Aff wrote:

Allora mettiamo in pratica la tua soluzione e vediamo se funziona :-)
hai 9 coniatori,
la moneta vera pesa 1  (p1)
con la seconda pesata ottieni 8.79 (p2)
con la terza pesata ottieni 506.17 (p3)
chi sono i falsari?
ciao Dario

> Allora mettiamo in pratica la tua soluzione e vediamo se funziona :-)
come non detto :) (c'è + di una soluzione)
ci ripenso su :)
ciao

 ha scritto nel messaggio
news:10533381...@mull.uninsubria.it...

Immagino che il peso della moneta vera non si conosca a priori...
:-)
ciao
fulvio

 fulvio
Pero' te ne fornisco una. Se vuoi, come tenta di fare aff, puoi usare 
una delle tre pesate per pesarla....
ciao Dario

 ha scritto nel messaggio
news:10534294...@mull.uninsubria.it...

mmmhhhhhh   pensavo fosse proprio li' l' inghippo, ossia che non si
dovesse necessariamente pesare la moneta vera da sola, ci ripenso
su....
ciao
fulvio


.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
I falsari sono 5 ed esattamente 1, 2, 5, 6 e 7.
Il metodo potrebbe essere questo, utilizzando le pesate proposte da Aff.
Con la seconda pesata individuo la differenza in peso tra le monete buone e
quelle false, differenza però che va divisa per il numero dei falsari, che
ancora non conosco.
Es. nel tuo caso la differenza è 0.21. Se c'è un solo falsario, la moneta
falsa pesa proprio 0.21 in meno di quella vera. Se i falsari sono 2, peserà
0.105 e così via.
Con la terza pesata riesco a individuare la differenza tra il peso che
avrebbero le monete se fossero tutte vere e il peso realmente ottenuto. Nel
tuo caso 511 (se fossero tutte vere) - 506.17 = 4.83.
A questo punto ragiono così: se il falsario fosse uno solo, la moneta
peserebbe 0.21 in meno e quindi dovrei aver pesato 23 monete false
(4.83/0.21 = 23). Attraverso la rappresentazione binaria di 23 posso
risalire all'identificazione dei falsari (per come è stata predisposta la
terza pesata). 23 in binario è 10111, ma questo vorrebbe dire che il numero
di falsari è 4 (il numero di cifre 1 contenute in 10111) e questo contrasta
con la supposizione, quindi provo a considerare che i falsari siano due e
conseguentemente la moneta falsa abbia un peso dimezzato e così via.
Falsari    Peso di una moneta    Monete
1    0,21    23
2    0,105    46
3    0,07    69
4    0,0525    92
5    0,042    115
6    0,035    138
7    0,03    161
8    0,02625    184
9    0,023333    207
L'unico caso in cui il numero di monete espresso in binario contiene un
numero di cifre 1 pari al numero dei falsari è 115 cioè 1110011.
Ciao
Giorgio

 I falsari sono 5 ed esattamente 1, 2, 5, 6 e 7.
e perche' non 1,3 e 7 ? :-)


E già che ci siamo, anche 3, 4, 5 e 7 ! :-))
Ciao :-)
Giorgio

Giorgio Vecchi wrote:

Esattamente.
Quindi? come facciamo a scoprire i colpevoli?
Dove sono gli esperti di pesate del NG? Dario Uri soprattutto.....!
forse pensavano, dal titolo, che fosse il solito "12 monete una falsa 
bilancia a piatti" :-)
ciao Dario

bilancia a piatti" :-)
L'avevo pensato anche io... 
Per fare leggere i propri topic ci vuole un nome che attiri e
incuriosisca... 
tipo "Donne ignude" :D :D :D
ciao
Stark

 ci riprovo
spoiler
.
.
.
.
..
.
.
.
.
.
.
.
.
.
..
.
è qualcosa di devastante, per quanto riguarda l'uso di monete, ma dovrebbe
funzionare:
in pratica le prime due pesate sono identiche a quelle che avevo descritto
precedentemente; cambia la terza; riporto il tutto
1) peso la moneta vera (peso che chiamo p1)
2) peso N monete (1 da ogni zecca privata) (peso che chiamo p2)
3) peso N^N - 1 monete (1 dalla prima zecca, N dalla seconda, N^2 dalla
terza.... N^(N-1) dalla N-esima) (un po' surreale vero ;)) (peso che chiamo
p3)
pongo d1 = N*p1 - p2 = f*d (f = numero di falsari, d=differenza di peso tra
moneta vera e falsa);
pongo d2 = (N^N - 1)*p1 - p3 = x*d (d = vedi sopra, x numero intero della
forma: N^a + N^b + N^c + ..... con a, b e c posizioni, secondo l'ordine
della terza pesata, dei falsari);
facendo d2/d1 ottengo y = x/f che dovrebbe essere univoco per ogni
combinazione: y sarà un numero compreso tra N^(k-2) e N^(k-1) (dove k
rappresenta la posizione, sempre secondo l'ordine della terza pesata, del
falsario nella posizione + significativa).
Procedendo x tentativi trovo gli altri.
sicuramente c'è un metodo meno dispendioso, ma x adesso ho trovato questo
ciao

 sicuramente c'è un metodo meno dispendioso, ma x adesso ho trovato questo
devastante davvero :-) Non sono sicuro che sia corretta come soluzione, 
o che sia implementabile in pratica ;-)
ciao Dario

 o che sia implementabile in pratica ;-)
Effettivamente è un po' devastante :-)
Ne ho trovata un'altra meno devastante
1) peso la moneta vera (p1)
2) peso 2^N - 1 monete (2^0 dalla prima zecca, 2^1 dalla seconda... 2^(N-1)
dalla N-esima) (p2)
3) peso 4^N - 1 monete (4^0 dalla prima zecca, 4^1 dalla seconda... 4^(N-1)
dalla N-esima) (p3)
chiamo x = (2^N -1) * p1 - p2 = n1 * d (d= differenza di peso tra moneta
vera e moneta falsa, n1 numero che convertito in binario diventa del tipo
10001010, dove gli 1 indicano la posizione del falsario)
chiamo y = (4^N - 1) * p1 - p3 = n2 * d (D= vedi sopra, n2 numero che
convertito in base 4 diventa del tipo 10001010, dove gli 1 indicano la
posizione del falsario)
il numero k=y/x è un numero razionale del tipo a/b (con a e b interi);
quello che rimane da fare è trovare un numero k tale che, moltiplicando a e
b per k si ottiene che la rappresentazione in base 4 di a*k sia identica a
quella in base 2 di b*k
Adesso faccio un programmino x verificare l'univocità della soluzione :)
a presto
chiamo y=


Ciao
Davide

 Seconda pesata. Peso la moneta falsa...
E come la identifichi? C'e' scritto sopra: "moneta falsa"?  :o)))
Ciao!!!  ((^__^))'
Livio


SPOILER
.
.
.
.
.
.
.
.
.
.
.
.
.
..
.
.
Con la prima pesata trovo il peso della moneta buona che possiedo, peso che
chiamo PV (Peso moneta Vera).
Con la seconda pesata prendo dalle N zecche (identificate con i numeri 0, 1,
2, ... N-1) un numero di monete pari a N elevato al proprio numero di
identificazione.
Cosě prenderň:
  N^0 = 1 moneta dalla prima zecca
  N^1 = N monete dalla seconda zecca
  N^2 monete dalla terza zecca
  ...
  N^(N-1) monete dalla N-esima ed ultima zecca
Al peso totale tolgo il valore che avrebbe una pesata dello stesso numero di
monete tutte vere: chiamo tale differenza D1.
Con la terza pesata prendo una moneta da ogni zecca, e nuovamente al peso
totale tolgo il valore che avrebbe una pesata dello stesso numero di monete
tutte vere: chiamo questa differenza D2.
I due valori D1 e D2 sono entrambi negativi o positivi (a seconda che le
monete false pesino di meno oppure di piů rispetto a quelle vere).
Il risultato della divisione D1/D2 lo vado a ricercare in un foglio di Excel
appositamente preparato con tutte le 2^N combinazioni di monete vere e
false: infatti ogni combinazione di queste monete produce un quoziente D1/D2
diverso dalle altre combinazioni (ma che rimane sempre lo stesso anche se si
cambiano i pesi effettivi in grammi delle monete vere e false).
Una volta individuato questo quoziente, la riga di Excel mi indica da quali
zecche ho preso le monete vere e quelle false, e posso anche agilmente
individuare quanto pesa la moneta falsa (divido D2 per il numero di zecche
falsarie, e ottengo la differenza di peso di una moneta falsa rispetto a
quella vera).
Ciao,
  Daniele


Come fai a dirlo? il problema nel metodo di Aff all'inizio del thread 
era che il rapporto non era sempre univoco.
ciao S.

Qualcosa non mi torna:
Ognuna delle N ditte puo' essere un falsario o non esserlo.
Per specificare tutti i falsari sono dunque necessari (al piu') N bit.
Qualunque sia la strategia di pesate successive la quantita'
di informazione che ottengo con sole tre pesate sara' comunque
limitata.
Diverso e' magari se si diceva che si sa che (forse) uno solo
e' falsario e dunque bisogna identificarlo.


ho fatto un programmino in c# che fa il test fino a un massimo di 15 zecche,
e non ci sono duplicati (per un numero di zecche + elevato comincia a
diventare complicato fare il test)
appena ho tempo faccio un programmino che in base al risultato delle 3
pesate individua i falsari
a presto


CIao
Davide