Pesate

[Nouth]

non so se in volta per il sito sia gia presente ma voglio proporlo ugualmente: penso che tutti conoscano il classico problema :
"Ci sono 10 sacchetti con 50 monete ognuno in uno dei sacchetti ci sono tuute monete false; negli altri tutte monete vere, sapendo che le monete vere pesano 10gr e quelle false 9gr come si fa con una sola pesata (bilancia digitale) a trovare quale sacchetto contiene le monete false?"

ora uno che conosco mi ha proposto questa versione:
"soliti 10 sacchetti , le monete vere pesano sempre 10 gr e quelle false 9, ma questa volta ci sono 2000 monete per sacchetto e non si sa quanti quali sacchetti contengano le monete false, come si può, sempre in una sola pesata digitale, individuare quanti a e quali sacchetti contengono monete false?"

[Boll]

non so se in volta per il sito sia gia presente ma voglio proporlo ugualmente: penso che tutti conoscano il classico problema :
"Ci sono 10 sacchetti con 50 monete ognuno in uno dei sacchetti ci sono tuute monete false; negli altri tutte monete vere, sapendo che le monete vere pesano 10gr e quelle false 9gr come si fa con una sola pesata (bilancia digitale) a trovare quale sacchetto contiene le monete false?"

Non lo conoscevo, penso si possa risolvere in parecchi modi, questo è quello a cui ho pensato io:

Prendiamo un sacchetto e chiamiamolo $ x_0 $, ora chiamiamo gli altri 9 sacchetti $ x_1,x_2,x_3,...,x_9 $, mettiamo in $ x_0 $ una moneta da $ x_1 $, 2 da $ x_2 $ e così via. Ora, poichè le monete vere sono zeri modulo 10, la congruenza modulo 10 del peso del sacchetto ora dipenderà solo dal sacchetto "fallato". Precisamente se la congruenza a modulo 10 del peso tolale è $ k $ il sacchetto con le monete false sarà il $ k $-esimo.

[Nouth]

la soluzione piu semplice e veloce per il primo è quella data da boll, il problema e la seconda versione, che non richiede conoscenza avanzate, voglio confrontare la mia soluzione (che daro piu in avanti per non influenzare gli altrui ragionamenti) con quelle che troverete.

[Loth]

ora uno che conosco mi ha proposto questa versione:
"soliti 10 sacchetti , le monete vere pesano sempre 10 gr e quelle false 9, ma questa volta ci sono 2000 monete per sacchetto e non si sa quanti quali sacchetti contengano le monete false, come si può, sempre in una sola pesata digitale, individuare quanti a e quali sacchetti contengono monete false?"

Allora, chiamati i sacchi $ x_0,x_1,...,x_9 $, prendiamo dal sacco di indice k $ 2^k $ monete (notando che con 10 sacchi ne basterebbero 512 per sacco) e pesiamole.

Se tutte le monete pesassero 10 grammi avremmo come peso totale 10230 grammi, invece, essendocene alcune false, avremo un ammanco: se il sacco k contiene monete false, provoca un ammanco di $ 2^k $ grammi (uno per moneta).

Visto che ogni intero e' esprimibile in modo unico come somma di potenze di 2, si puo' calcolare quali erano i sacchi con monete false.
Ad esempio, osservando scrittura in base 2 dell'ammanco, se la cifra in posizione z (da destra) e' uno, allora il sacco $ x_{z-1} $ contiene monete false.

[Nouth]

stessa soluzione a cui sono giunto io!!!