Bilancia a piatti

[ngshya]

Con una bilancia a piatti e un certo numero di pesi si vogliono pesare oggetti di peso inferiore a $ \displaystyle k $ grammi con un errore non superiore a un grammo. Non si possono mettere pesi nel piatto su cui si poggia l'oggetto. Dire qual è il minimo numero $ \displaystyle n $ di pesi, in funzione di $ \displaystyle k $, sufficiente a tale scopo.

SNS 1961-1962 n°4*

Buon lavoro!

[io.gina93]

ma non è che te l'hanno posto quelli del diderot??
se sì ho l'impressione che lo faranno fare anche a me! (quindi evita di postarli, per favore..)
abbiamo quasi lo stesso programma!

cmq non ne sono sicura...
suppongo che i pesi siano diversi e che li posso scegliere io...
i pesi avranno come peso $ 2^k $ grammi... (cioè 1,2,4,8,16...)
se k è dispari gli sottraggo uno, scrivo la forma binaria di k-1 e conto quanti 1 ci sono... (e qui l'errore sarà di un grammo)
se k pari, scrivo la forma binaria di k e conto quanti 1 ci sono.

ma forse non ho capito cosa vuole il problema...

[ngshya]

No, è un problema di ammissione alla Normale, leggermente modificato, che avevo letto stamattina e che mi è piaciuto.

Come fai a dire che il numero di pesi che prendi è il minimo? E poi quando conti gli uni che ci sono nella rappresentazione binaria di k, come fai a essere sicura di non aver escluso potenze di 2 che magari ti servono per comporre altri pesi? Comunque, sei sulla buona strada.

[io.gina93]

credo di aver capito...
non devo usare pesi da $ 2^k $ grammi bensì da $ 3^k $
succede che posso dividere i numeri naturali in gruppi da tre: quelli congrui 1,0,-1 modulo 3 e perciò qualunque oggetto può essere pesato con un errore non superiore ad un grammo...

[ngshya]

Scusa, sarà perché sono ormai troppo vecchio, ma non ci sto capendo granché. Puoi scrivere per bene tutti i passaggi della tua dimostrazione?

[<enigma>]

Se la memoria non mi fa difetto è un vecchio problema di Bachet oppure uno che gli assomiglia molto.

[io.gina93]

no, scusami te...
ho scritto male io.. le dimostrazioni sono il mio tallone d'achille (o come dicono oggi da killer.. )

quello che dicevo prima, (che non e' soluzione del problema) era di usare il linguaggio in base 3.
ho usato le congruenze solo per evitare i pesi di 3^0 grammi..
cioe' se ho 19 grammi da pesare utilizzo 2 pesi da 9 (errore di -1 grammo)
se ne ho 20 uso 2 pesi da 9 e uno da 3 (errore di +1 grammo)

pero' e' meglio in base 2
perche' se k fosse 100 i pesi a disposizione in base 2 sono (escudiamo 2^0, per i numeri dispari come ho spiegato prima): 2,4,8,16,32,64 totale 6
in base 3 sono(escudiamo 3^0, per i numeri non congrui a 0 mod 3 come ho spiegato prima): 3(per 2), 9(per 2), 27(per 2),81 totale 7

[ngshya]

Se la memoria non mi fa difetto è un vecchio problema di Bachet oppure uno che gli assomiglia molto.

ops, non pensavo che fosse così famoso

[<enigma>]

Se la memoria non mi fa difetto è un vecchio problema di Bachet oppure uno che gli assomiglia molto.

ops, non pensavo che fosse così famoso

Infatti non sapevo neanche fosse un problema di un test SNS, non lo conoscevo per quello... ora vado a spulciare la mia biblioteca per vedere se lo trovo.

[Sonner]

Ma quello che non capisco è: affinchè l'oggetto di peso $ i $ sia misurabile serve che io possa ottenere uno a scelta tra $ i-1 $ e $ i+1 $ o servono tutti e 2?

[io.gina93]

credo che i pesi siano di 2,5,10,20,40,80,160.... $ 2^m \cdot 10 $ grammi

allora 1-2-3 grammi li potrei pesare con un peso da 2 g
il 4-5-6 con uno da 5g
con 2g e 5g posso pesare oggetti di peso inferiore o uguale a 8g

il 9 lo peserei con uno da 10g
con 2g, 5g, 10g posso pesare oggetti di peso inferiore o uguale a 18g

il 19 lo peserei con uno da 20g
con 2g, 5g, 10g, 20g posso pesare oggetti di peso inferiore o uguale a 38g

e così via...
quindi se devo pesare oggetti inferiori a 78g ho i pesi:2,5,10,20,40 totale 5
mentre col linguaggio binario:2,4,8,16,32,64 totale 6

direi che c'è qualche miglioramento...
(qui l'errore è di +1g o -1g)

[<enigma>]

Se la memoria non mi fa difetto è un vecchio problema di Bachet oppure uno che gli assomiglia molto.

Pardon, mi sbagliavo: il problema di Bachet non aveva l'ipotesi dell'errore bensì era di pesare esattamente.

[<enigma>]

EDIT: capito meglio il testo ora.

[ngshya]

credo che i pesi siano di 2,5,10,20,40,80,160.... $ 2^m \cdot 10 $ grammi

allora 1-2-3 grammi li potrei pesare con un peso da 2 g
il 4-5-6 con uno da 5g

Se ottieni che un oggetto pesa meno di 5 ma più di 2?

@Sonner
Tutti e due.

[io.gina93]

il 3 lo peso con 2g, e il 4 con 5g...
a questo punto credo di non aver capito tanto il problema...