21. Ancora monete false
Re: 21. Ancora monete false
O non sto vedendo qualcosa di semplice o sospetto che non sia semplice
Arrivati a questo punto con qualche considerazione si può dire che deve esserci una moneta che non pesi mai (e vabbè) e poi che ad ogni pesata vanno messe $\frac{3^{n-1}-1}{2}$ monete su ogni piatto. Ora o hai un metodo facile e meccanico che riesci ad applicare sempre (ma che magari non si nota facilmente), oppure ci sarebbe da costruire una tabella che associa un codice di $k$ cifre ad ogni moneta contata due volte (sia quando è falsa e pesa di più sia quando è falsa e pesa di meno), in modo da riuscire a creare una biezione con le pesate. Anche qui andrebbero rispettate condizioni scomodissime da controllare
Boh... dicci tu xD
Arrivati a questo punto con qualche considerazione si può dire che deve esserci una moneta che non pesi mai (e vabbè) e poi che ad ogni pesata vanno messe $\frac{3^{n-1}-1}{2}$ monete su ogni piatto. Ora o hai un metodo facile e meccanico che riesci ad applicare sempre (ma che magari non si nota facilmente), oppure ci sarebbe da costruire una tabella che associa un codice di $k$ cifre ad ogni moneta contata due volte (sia quando è falsa e pesa di più sia quando è falsa e pesa di meno), in modo da riuscire a creare una biezione con le pesate. Anche qui andrebbero rispettate condizioni scomodissime da controllare
Boh... dicci tu xD
- Federico II
- Messaggi: 449
- Iscritto il: 14/05/2014, 14:53
Re: 21. Ancora monete false
Hint
Secondo hint (da leggere solo dopo il primo)
Testo nascosto:
Testo nascosto:
Il responsabile della sala seminari
Re: 21. Ancora monete false
Ok, o sono impedito io e mi sfugge l'ovvietà, o con $13$ monete e $3$ pesate non si può determinare la moneta falsa con certezza.
Diventa possibile, invece (e vale nel caso generale, quindi con $\displaystyle \frac{3^n - 1}{2}$ monete e $n$ pesate) se posso disporre di una moneta "ausiliaria" che so per certo essere autentica. E in tal caso posso dimostrare che il massimo è effettivamente quello.
Se è così dimmelo, così posto la soluzione.
Altrimenti devo pensarci meglio...
Diventa possibile, invece (e vale nel caso generale, quindi con $\displaystyle \frac{3^n - 1}{2}$ monete e $n$ pesate) se posso disporre di una moneta "ausiliaria" che so per certo essere autentica. E in tal caso posso dimostrare che il massimo è effettivamente quello.
Se è così dimmelo, così posto la soluzione.
Altrimenti devo pensarci meglio...
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre.
Albert Einstein
Albert Einstein
- Federico II
- Messaggi: 449
- Iscritto il: 14/05/2014, 14:53
Re: 21. Ancora monete false
Ti sbagli, esiste un modo per trovare tra $13$ monete quella falsa con $3$ pesate, e in generale esiste anche un modo per trovare tra $\frac{3^n-1}{2}$ monete quella falsa, senza servirsi di alcuna moneta ausiliaria. Il metodo inizia così:
Testo nascosto:
Il responsabile della sala seminari
Re: 21. Ancora monete false
Ok, hai ragione, l'ho capito un paio d'ore fa...
Allora, vediamo il caso generale.
Ora mi manca da dimostrare che quello è effettivamente il massimo, ma forse è meglio che lo scriva Steph e poi vada avanti lui, come è giusto che sia.
Allora, vediamo il caso generale.
Testo nascosto:
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre.
Albert Einstein
Albert Einstein
Re: 21. Ancora monete false
No vabbè, non ho letto ma se è giusta vai tu Io non avrei manco tempo.
Per dimostrare che non si possono mettere altre monete si può vederla in questo modo. Ad ogni pesata associamo una lettera che ne indica l'esito. E sarà tipo $S$ se la bilancia pende a sinistra, $D$ se prende a destra e $C$ se è equilibrata. Dopo aver fatto $n$ pesate mettendo insieme i risultati si otterrà una parola tipo $SCCD...D$ (per esempio) di $n$ caratteri a seconda dei risultati delle pesate. Presa una parola di queste dobbiamo essere in grado di individuare univocamente la moneta falsa. Quindi ad ogni parola deve corrispondere una moneta. Le parole totali sono $3^n$, ma la moneta falsa occupa due parole diverse. Infatti se una certa moneta è falsa allora può generare le parole $DCCS...S$ o $SCCD...D$ (la sua inversa) a seconda che pesa di più o di meno. Da cui si ottiene il $\frac{3^n-1}{2}$
Ci sarebbe da giustificare il fatto che $CCCC...C$ avendo l'inversa uguale potrebbe consentire una moneta in più, ma in realtà bisogna per forza escludere una parola diversa da $CCCC...C$ (e di conseguenza pure la sua inversa), altrimenti alla prima pesata non si riuscirebbe a mettere lo stesso numero di monete su entrambi i bracci. Ok, questo forse l'ho scritto malissimo al limite lo chiarirò dopo
Per dimostrare che non si possono mettere altre monete si può vederla in questo modo. Ad ogni pesata associamo una lettera che ne indica l'esito. E sarà tipo $S$ se la bilancia pende a sinistra, $D$ se prende a destra e $C$ se è equilibrata. Dopo aver fatto $n$ pesate mettendo insieme i risultati si otterrà una parola tipo $SCCD...D$ (per esempio) di $n$ caratteri a seconda dei risultati delle pesate. Presa una parola di queste dobbiamo essere in grado di individuare univocamente la moneta falsa. Quindi ad ogni parola deve corrispondere una moneta. Le parole totali sono $3^n$, ma la moneta falsa occupa due parole diverse. Infatti se una certa moneta è falsa allora può generare le parole $DCCS...S$ o $SCCD...D$ (la sua inversa) a seconda che pesa di più o di meno. Da cui si ottiene il $\frac{3^n-1}{2}$
Ci sarebbe da giustificare il fatto che $CCCC...C$ avendo l'inversa uguale potrebbe consentire una moneta in più, ma in realtà bisogna per forza escludere una parola diversa da $CCCC...C$ (e di conseguenza pure la sua inversa), altrimenti alla prima pesata non si riuscirebbe a mettere lo stesso numero di monete su entrambi i bracci. Ok, questo forse l'ho scritto malissimo al limite lo chiarirò dopo
- Federico II
- Messaggi: 449
- Iscritto il: 14/05/2014, 14:53
Re: 21. Ancora monete false
Ma qui non è andato avanti nessuno??
Re: 21. Ancora monete false
Em , e qui ?
Chi lotta con i mostri deve star attento a non diventare un mostro. E se guarderai a lungo un abisso, l'abisso finirà per guardare in te
Re: 21. Ancora monete false
Credo sia il caso che qualcuno posti un nuovo problema ...
Chi lotta con i mostri deve star attento a non diventare un mostro. E se guarderai a lungo un abisso, l'abisso finirà per guardare in te