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?"
Pesate
Re: Pesate
Non lo conoscevo, penso si possa risolvere in parecchi modi, questo è quello a cui ho pensato io:Nouth ha scritto: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?"
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.
Re: Pesate
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.Nouth ha scritto: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?"
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.