esercizio con le monete

[alefig]

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

[gandalf]

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

[alefig]

No, il testo è giusto e il peso è \"diverso\", non si sa se maggiore o minore...altrimenti sarebbe troppo facile! <IMG SRC="images/splatt_forum/icons/icon_wink.gif">
<BR>

[alberto]

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...

[Antimateria]

Ehm... alefig in persona afferma che la soluzione qui sopra è errata (ma non può dirvelo direttamente, perché è troppo occupato a studiare, quindi ha delegato me).

[Laurentius]

Invece di pesare ogni moneta con la successiva, potrei pesarle ognuna una volta (1° e 2°, 3° e 4°, ecc), e nel caso due monete non siano uguali pesarne una sola con un\'altra.
<BR>Quindi:
<BR>se n pari = n/2+1
<BR>se n dispari = (n+1)/2

[alberto]

ma questo va contro la regola: \"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\".
<BR>io ho interpretato che tutte le pesate vanno decise a priori

[DD]

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.

[alefig]

Salve a tutti.
<BR>Innanzitutto confermo quanto ha detto Alberto e mi scuso con DD per il poco rigore.
<BR>Vi dico poi che le soluzioni scritte finora sono molto sottostimate..si può fare di meglio. <IMG SRC="images/splatt_forum/icons/icon_wink.gif">
<BR>

[DD]

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]

[Antimateria]

DD, le pesate possono dare 3 informazioni diverse: sinistra, centro, destra, e quindi 3^n possibilità. Ed il fatto che la bilancia penda da una parte o dall\'altra può essere effettivamente sfruttato per migliorare quel 2^n.[addsig]

[Tassinari_Luca]

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

[Tassinari_Luca]

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.

[Tassinari_Luca]

se n=3+h m>=12(3)^h
<BR>(per entrambi gli esercizi proposti)
<BR>Da notare che se si considera l\' esercizio originale(quello proposto da Figalli)
<BR>m=12(3)^h non costituisce il limite massimo in quanto<IMG SRC="images/forum/icons/icon_razz.gif">er n=3 m=13.

[DD]

OK, come si fa?