Newsgroup: it.hobby.enigmi
Titolo: Un altro problema di pesate.

Pensavo che sull'argomento non ci fosse più nulla da dire, invece
nell'ultimo numero della rivista Archimede ne pubblicano uno che non
avevo mai visto... Premetto che non conosco la soluzione.
 
Sono date 1000 monete, ognuna delle quali ha come peso un numero intero
di grammi, e una bilancia a due piatti, che misura in grammi la
differenza di peso tra gli oggetti posti sui due piatti. La bilancia è
generalmente affidabile, ma per un difetto di costruzione si sa che al
più una volta nella sua vita può eventualmente fornire un risultato
sbagliato di esattamente un grammo.
Qual è il numero minimo di pesate che dobbiamo preventivare per essere
sicuri di poter determinare esattamente il peso di tutte le monete?
 
M.
 
-- 
Per rispondermi via e-mail togli l'ovvio.


.
.
.
.
.
.
spoiler
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
---------------------------------
Io intendo: determinare esattamente il peso di CIASCUNA moneta, giusto?
 
Supponiamo di avere una siffatta bilancia, ma senza difetti. A me sembra
che in tali condizioni occorrerebbero comunque 1000 pesate, in qualunque
modo si organizzino. Infatti, anche facendo delle combinazioni, dovremmo
comunque scrivere un sistema di 1000 equazioni per 1000 incognite, quindi
tanto vale pesarle una a una, con uno dei due piatti vuoto.
 
Cio' fatto, ora sappiamo che una potrebbe essere sbagliata. Per trovarla
o per verificare che son tutte giuste, dovrebbero essere sufficienti 10
pesate e un metodo dicotomico (2^10=1024). Se sono tutte esatte, l'errore 
non e' accaduto e quindi bastano 1010 pesate. Diversamente individuo
quella dubbia e mi occorre una ulteriore pesata per determinarne il valore.
Totale 1011 pesate. 
 
Fila?
 
Ciao
Livio
 

 Fila?
 
Per filare fila, solo che non sfrutti la peculiarità della bilancia di
misurare la differenza dei pesi sui piatti. Pensandoci un po' credo che
bastino 1001 pesate, però adesso non ho tempo di scrivere il mio metodo,
per cui vi lascio pensare ancora un po'.


 Pensandoci un po' credo che bastino 1001 pesate
 
Spoiler

All'inizio mettiamo tutte le monete sul primo piatto e la bilancia
segnerà p_0. Poi spostiamo la moneta 1 sul secondo piatto e la bilancia
segnerà p_1. Se la bilancia funziona normalmente, il peso della moneta 1
sarà dunque x_1 = (p_0 - p_1)/2. Poi facciamo la stessa cosa per le
monete 2, 3, ..., 999. Il peso della moneta 1000 si può ottenere per
differenza: x_1000 = p_0 - x_1 - x_2 - ... - x_999. In tutto abbiamo
fatto 1000 pesate.
 
Il vantaggio è che ad ogni passo la differenza fra p_n e p_(n+1) è un
numero pari: se ad un certo punto otteniamo un numero dispari sappiamo
che la bilancia su p_(n+1) ha sbagliato. Ovviamente anche la differenza
p_(n+1) - p_(n+2) è dispari, ma se alla fine facciamo una pesata
supplementare della moneta n+1 da sola possiamo ricostruire tutti i pesi
in modo corretto.
 
Ultima osservazione: se già p_0 - p_1 dà un numero dispari allora è
possibile che la bilancia abbia sbagliato o su p_0 o su p_1. Tuttavia la
parità di p_1 - p_2 ci permette di capire di quale caso si tratta ed
anche in questo caso pesando la moneta 1 da sola alla fine possiamo
ricostruire i numeri corretti.


Parity check! :-) Bello.