Newsgroup: it.hobby.enigmi
Titolo: Pesate e monete

Ciao a tutti!
sono nuovo del gruppo, scusate se non mi sono presentato prima.
Mi e` venuto in mente questo problemino, variazione di uno dei problemi sulle
pesate e le monete.
Abbiamo 5 sacchi di monete: 
in un sacco ci sono solo monete che pesano 10g
in un altro, monete che pesano 20 g,
uno con monete da 30,
uno da 40,
ed uno da 50.
Non sappiamo, pero`, quale e` il sacco da 10, quale da 20, ...
Ora, noi abbiamo una bilancia (ad un solo piatto) con una lancetta che indica il
peso in grammi; come fate a distinguere i 5 sacchi in una sola pesata?
Qual e` il numero minimo di monete da mettere sul piatto?
(Beh, io ho pensato un modo, poi magari ce n'e` uno migliore)
Ciao ciao,
Marco
-- 
http://www.ing.unife.it/docenti/MarcoGavanelli

 Qual e` il numero minimo di monete da mettere sul piatto?\
Non so se questo problema e' nellle FAQ ...
-
.
.
S
P
O
I
L
E
R
.
.
-
indico con (a,b,c,d,e) i pesi in decagrammi di ciascuna moneta presa 
rispettivamente dai sacchi (A,B,C,D,E), ossia una permutazione incognita 
di (1,2,3,4,5). Metto sulla bilancia:
1   moneta dal sacco d
5   monete dal sacco c
25  monete dal sacco b
125 monete dal sacco a
La conversione del peso in decagrammi letto sulla bilancia in base 5 mi 
da' proprio abcd; ("e" si ottiene ovviamente per esclusione).
In questo modo ho utilizzato 156 monete, ma forse si puo' fare meglio.
Dade :)

 Dade :)
Piccola svista:
Prima della conversione in base 5 bisogna sottrarre al peso in 
decagrammi letto sulla bilancia proprio 156. Questo perche' in pesi 
delle monete in decagrammi sono le cifre 0,1,2,3,4 della base 5 
aumentate di 1. Dopo la conversione  in base 5 bisogna aggiungere 1 ad 
agni cifra ottenuta.
Dade :)

Qual e` il numero minimo di
monete da mettere sul piatto?
.
.
.
.
.
.
.
.
.
.
.
.
Si
tratta di individuare la permutazione tra le 5!=120 permutazioni possibili.
E' chiaro che basta prelevare le monete da 4 dei 5 sacchi, il quinto sara'
determinato per esclusione. Siano k1,k2,k3,k4 il numero delle monete da
prelevare da ciascuno dei primi 4 sacchi, occorre che la pesata sia diversa
per ciascuna delle 120 permutazioni, in modo da risalire alla specifica
permutazione ad esempio tramite una tabella. Davide sceglie i coefficienti
*pesati* di 1,5,25,125 per un totale di 156 monete. Va bene ma
probabilmente e' ridondante perche' funzionerebbe per 5^4=625 combinazioni.
Io ho trovato 6,7,23,95 per un totale di 131 monete. Li ho trovati con la
mia Darwin Machine, quindi sono *evoluti* ma non e' detto che siano
ottimali. Non ho trovato nessun metodo analitico.
.
Ciao  :o)
Livio
--------------------------------
Inviato via 
http://usenet.iol.it
 

Li ho trovati
con la mia Darwin Machine, quindi sono *evoluti* ma non e' detto che siano
ottimali. 
.
.
.
Infatti nella pausa pranzo i coefficienti sono
ulteriormente evoluti in 2,5,21,91 per un totale di sole 119 monete. Questo
credo che sia l'ottimo. Per vs. verifica cerco di mettere in calce un
concentrato di tabella con le 120 permutazioni e le relative pesate tutte
diverse.
.
Ciao  :o)
Livio
.
.
Tabella:
439_12345 530_12354
369_12435 551_12453 390_12534 481_12543 423_13245 514_13254 283_13425
556_13452 304_13524 486_13542 337_14235 519_14253 267_14325 540_14352
309_14523 400_14532 342_15234 433_15243 272_15324 454_15342 293_15423
384_15432 436_21345 527_21354 366_21435 548_21453 387_21534 478_21543
404_23145 495_23154 194_23415 558_23451 215_23514 488_23541 318_24135
500_24153 178_24315 542_24351 220_24513 402_24531 323_25134 414_25143
183_25314 456_25341 204_25413 386_25431 417_31245 508_31254 277_31425
550_31452 298_31524 480_31542 401_32145 492_32154 191_32415 555_32451
212_32514 485_32541 229_34125 502_34152 159_34215 523_34251 222_34512
313_34521 234_35124 416_35142 164_35214 437_35241 206_35412 297_35421
328_41235 510_41253 258_41325 531_41352 300_41523 391_41532 312_42135
494_42153 172_42315 536_42351 214_42513 396_42531 226_43125 499_43152
156_43215 520_43251 219_43512 310_43521 236_45123 327_45132 166_45213
348_45231 187_45312 278_45321 330_51234 421_51243 260_51324 442_51342
281_51423 372_51432 314_52134 405_52143 174_52314 447_52341 195_52413
377_52431 228_53124 410_53142 158_53214 431_53241 200_53412 291_53421
233_54123 324_54132 163_54213 345_54231 184_54312 275_54321



Bravissimo, complimenti!!!
No, non era nelle FAQ, ci avevo guardato. La piu` simile e` la n.13, che pero`
e` piu` semplice.
Ciao,
Marco
-- 
http://www.ing.unife.it/docenti/MarcoGavanelli


Bellissima modellizzazione del problema! Ammetto che avevo pensato alla stessa
soluzione di Davide. Cerchero` di trovare la soluzione ottima con un metodo
completo.
A presto,
Marco
-- 
Marco Gavanelli

 determinato per esclusione.
Questa affermazione e` senz'altro vera nel caso si usino come coefficienti le
potenze del 5, ma pensi che sia vera in generale?
Io ho provato ad usare monete da tutti e 5 i sacchi: ho ottenuto la soluzione 
[1, 3, 6, 22, 92], con costo 124, che non e` poi cosi` malvagia (e` la soluzione
ottima, imponendo l'ulteriore vincolo che nessuno dei numeri sia zero). Forse
usando un numero diverso di sacchi puo` convenire usare monete da tutti e non
escluderne uno.


 credo che sia l'ottimo. 
Si`, era l'ottimo, l'ho provato con ECLiPSe.
Ecco la parte finale dell'output:
....
[3, 27, 31, 98]Found a solution with cost 159
[4, 26, 29, 93]Found a solution with cost 152
[3, 24, 28, 89]Found a solution with cost 144
[11, 16, 23, 93]Found a solution with cost 143
[6, 15, 23, 97]Found a solution with cost 141
[12, 14, 23, 89]Found a solution with cost 138
[7, 12, 23, 89]Found a solution with cost 131
[9, 11, 23, 86]Found a solution with cost 129
[6, 7, 23, 89]Found a solution with cost 125
[3, 5, 22, 94]Found a solution with cost 124
[2, 5, 21, 95]Found a solution with cost 123
[2, 5, 21, 94]Found a solution with cost 122
[2, 5, 21, 93]Found a solution with cost 121
[2, 5, 21, 91]Found a solution with cost 119
L = [2, 5, 21, 91]
Yes (53050.07s cpu)
Ancora complimenti!
Marco
--
http://www.ing.unife.it/docenti/MarcoGavanelli