esercizio con le monete
Moderatore: tutor
Ecco un problema non troppo difficile con le monete:
<BR>sono date m monete e una bilancia a 2 piatti. Tra queste monete, tutte identiche nell\'aspetto, ce n\'è un che ha un peso diverso da tutte le altre, che invece pesano uguali.
<BR>Si hanno a disposizione n pesate e la strategia da seguire nel fare le pesate deve essere decisa prima di iniziare e non si può cambiare a seconda del risultato ottenuto durante le varie pesate. Dire qual\'è il massimo m, per il quale si può trovare la moneta, in funzione di n.
<BR>Good luck,
<BR>Alessio
<BR>sono date m monete e una bilancia a 2 piatti. Tra queste monete, tutte identiche nell\'aspetto, ce n\'è un che ha un peso diverso da tutte le altre, che invece pesano uguali.
<BR>Si hanno a disposizione n pesate e la strategia da seguire nel fare le pesate deve essere decisa prima di iniziare e non si può cambiare a seconda del risultato ottenuto durante le varie pesate. Dire qual\'è il massimo m, per il quale si può trovare la moneta, in funzione di n.
<BR>Good luck,
<BR>Alessio
Io il problema l\'ho risolto considerando che la moneta di peso diverso abbia un peso maggiore delle altre...
<BR>Poi sono andato a rileggere il tuo testo e dicevi \"peso diverso\"...
<BR>E\' voluta l\'ambiguità, oppure c\'è un errore di formulazione(in quanto sapendo se il peso diverso è maggiore o minore staremmo già un bel passo avanti)...
<BR>attendo chiarimenti
<BR>MELLON
<BR>Poi sono andato a rileggere il tuo testo e dicevi \"peso diverso\"...
<BR>E\' voluta l\'ambiguità, oppure c\'è un errore di formulazione(in quanto sapendo se il peso diverso è maggiore o minore staremmo già un bel passo avanti)...
<BR>attendo chiarimenti
<BR>MELLON
"Vecchia piccola borghesia per piccina che tu sia,
non so dire se fai più rabbia, pena, schifo o malinconia..." (Claudio Lolli)
non so dire se fai più rabbia, pena, schifo o malinconia..." (Claudio Lolli)
azzardo:
<BR>(3/2 n)+1 se n è pari
<BR>(3/2)(n+1) se n è dispari
<BR>spiegazione
<BR>peso (1°,2°),(2°,3°),(4°,5°),(5°,6°),(7°,8°),(8°,9°)...
<BR>in questo modo dalle pesate senza equilibrio posso sempre risalire alla moneta diversa. aggiungo una moneta che non peso con nessun altra e se tutte le pesate mantengono l\'equilibrio quella moneta è la \"diversa\".
<BR>e facile interpretare la distinzione n pari, n dispari...
<BR>(3/2 n)+1 se n è pari
<BR>(3/2)(n+1) se n è dispari
<BR>spiegazione
<BR>peso (1°,2°),(2°,3°),(4°,5°),(5°,6°),(7°,8°),(8°,9°)...
<BR>in questo modo dalle pesate senza equilibrio posso sempre risalire alla moneta diversa. aggiungo una moneta che non peso con nessun altra e se tutte le pesate mantengono l\'equilibrio quella moneta è la \"diversa\".
<BR>e facile interpretare la distinzione n pari, n dispari...
- Antimateria
- Messaggi: 651
- Iscritto il: 01 gen 1970, 01:00
- Località: Vergate sul Membro
-
- Messaggi: 49
- Iscritto il: 01 gen 1970, 01:00
Concordo con la tua interpretazione, ma a rigore alefig avrebbe dovuto dire \"la <!-- BBCode Start --><I>successione</I><!-- BBCode End --> delle pesate\". Una <!-- BBCode Start --><I>strategia</I><!-- BBCode End --> è, per definizione, una funzione dall\'insieme delle situazioni possibili all\'insieme delle azioni possibili: qualcosa che dipende dall\'andamento del gioco, insomma.
[img:2sazto6b]http://digilander.iol.it/daniel349/boy_math_md_wht.gif[/img:2sazto6b]
2^n. Non di più, perché con n pesate si hanno n bit d\'informazione. D\'altra parte con n pesate si può sempre trovare la moneta diversa confrontando n volte mucchietti di 2^(n-2) monete che abbiano uno 0 nella stessa posizione nella rappresentazione in base 2 (se numeriamo le monete da 0 a 2^n-1). Immaginiamo di confrontare prima due mucchietti di monete che hanno lo 0 in n-esima posizione partendo da destra, poi quelle che ce l\'hanno in (n-1)-esima posizione e così via fino a quelle che terminano per 0. Se scriviamo 1 ogni volta che la bilancia è in equilibrio e 0 ogni volta che non lo è otteniamo la rappresentazione in base 2 del numero che avevamo assegnato alla moneta diversa.[addsig]
[img:2sazto6b]http://digilander.iol.it/daniel349/boy_math_md_wht.gif[/img:2sazto6b]
- Antimateria
- Messaggi: 651
- Iscritto il: 01 gen 1970, 01:00
- Località: Vergate sul Membro
-
- Messaggi: 50
- Iscritto il: 01 gen 1970, 01:00
Effettivamente m (con n=3+k (k>0))
<BR>>=12((3)^k).
<BR>Da notare che m>= 12(3)^k anche se bisogna pure determinare se esiste tale moneta falsa, ovvero se si riformula il problema nei seguenti termini:Si sa che SE esiste una moneta falsa essa ha un peso differente rispetto alle altre.
<BR>Determinare (date n pesate) MAX m in modo che si possa stabilire con certezza tra le m monete se esiste una moneta falsa e se esiste quale è.
<BR>Au revoir
<BR>>=12((3)^k).
<BR>Da notare che m>= 12(3)^k anche se bisogna pure determinare se esiste tale moneta falsa, ovvero se si riformula il problema nei seguenti termini:Si sa che SE esiste una moneta falsa essa ha un peso differente rispetto alle altre.
<BR>Determinare (date n pesate) MAX m in modo che si possa stabilire con certezza tra le m monete se esiste una moneta falsa e se esiste quale è.
<BR>Au revoir
Luca Tassinari
-
- Messaggi: 50
- Iscritto il: 01 gen 1970, 01:00
Se n= 3k m>=12^k
<BR> n=3k+1 m>=2(12)^k
<BR> n=3k+2 m>=4(12)^k
<BR>(Se k>=1)
<BR>(Per ambedue i tipi di problemi)
<BR>Se n=0,1 m=1
<BR>Se n=2 m=4 (Per il problema originale proposto da Alessio Figalli)
<BR> m=3 (Per la piccola modifica da me introdotta)
<BR>A questo punto ritengo che per n=3k m=12^k costituisca effettivamente il massimo valore ottenibile.
<BR> n=3k+1 m>=2(12)^k
<BR> n=3k+2 m>=4(12)^k
<BR>(Se k>=1)
<BR>(Per ambedue i tipi di problemi)
<BR>Se n=0,1 m=1
<BR>Se n=2 m=4 (Per il problema originale proposto da Alessio Figalli)
<BR> m=3 (Per la piccola modifica da me introdotta)
<BR>A questo punto ritengo che per n=3k m=12^k costituisca effettivamente il massimo valore ottenibile.
Luca Tassinari
-
- Messaggi: 50
- Iscritto il: 01 gen 1970, 01:00