21. Ancora monete false

[xXStephXx]

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

[Federico II]

Hint

Testo nascosto:

Provate a trovare una soluzione con $n=3$ e $k=\frac{3^n-1}{2}=13$, magari poi è generalizzabile a tutti gli $n$... per la soluzione con $n=3$ se proprio non ci riuscite c'è un altro hint sotto.

Secondo hint (da leggere solo dopo il primo)

Testo nascosto:

Nella prima pesata quante monete potete pesare al massimo così da non lasciarvi troppe monete in caso di equilibrio? Poi con quelle monete se avete l'informazione che un gruppo pesava di meno e uno di più come procedete?

[cip999]

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

[Federico II]

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:

Mettiamo $4$ monete su ogni piatto. Se sono in equilibrio ce ne restano $5$ tra cui può stare quella falsa, e possiamo usare le altre $8$ come ausiliarie. Se non sono in equilibrio, possiamo distinguere un insieme di $4$ palline tali che, se la moneta falsa è tra quelle, allora è più leggera, e un altro analogo con più pesante...

[cip999]

Ok, hai ragione, l'ho capito un paio d'ore fa...

Allora, vediamo il caso generale.

Testo nascosto:

Lemma: È sempre possibile determinare la moneta falsa in un insieme di $\displaystyle \frac{3^n + 1}{2}$ monete in al più $n$ pesate, avendo a disposizione $3^{n - 1}$ monete che sappiamo con certezza essere autentiche.
Dimostrazione: Vero per $n = 0$ (ho una sola moneta). Ora supponiamo sia vero per $n$ e dimostriamolo per $n+ 1$. Pesiamo $3^n$ monete con quelle ausiliarie; possono ora presentarsi due casi:

1. La bilancia non è in equilibrio. In questo caso, sappiamo che la moneta falsa deve trovarsi tra quelle pesate, e sappiamo anche se pesa di più o di meno. Possiamo dunque trisecare $n$ volte con le pesate che ci restano, e vinciamo.
2. I piatti sono in equilibrio. Allora la moneta falsa si trova tra le restanti $\displaystyle \frac{3^{n + 1} + 1}{2} - 3^n = \frac{3^n + 1}{2}$, e sappiamo per ipotesi induttiva che possiamo riuscirci.

Adesso torniamo al problema iniziale. Pesiamo $3^{n - 1} - 1$ monete, e abbiamo anche qui due casi:

1. I piatti sono in equilibrio. Allora, il lemma ci assicura che riusciamo a individuare la moneta fasulla tra le restanti $\displaystyle \frac{3^{n - 1} + 1}{2}$ con sole $n - 1$ pesate (le monete ausiliarie possiamo prenderle in prestito da quelle appena pesate, che sono certamente buone).
2. Un gruppo di monete è più pesante dell'altro. Procediamo in questo modo: togliamo dalla bilancia $3^{n - 2}$ monete ($\displaystyle \frac{3^{n - 2} - 1}{2}$ da un piatto e $\displaystyle \frac{3^{n - 2} + 1}{2}$ dall'altro). Poi prendiamo dal piatto che contiene meno monete un gruppo di $\displaystyle \frac{3^{n - 2} - 1}{2}$ e lo mettiamo sull'altro; allo stesso modo, trasportiamo $\displaystyle \frac{3^{n - 2} + 1}{2}$ monete dal secondo piatto al primo. Infine mettiamo sul piatto che è in difetto una moneta di quelle non pesate (che sono sicuramente vere).
   In questo modo riusciamo sempre a isolare un gruppo di (al più) $3^{n - 2}$ monete, delle quali $\displaystyle \frac{3^{n - 2} - 1}{2}$ sono più leggere e le restanti più pesanti (o viceversa). Così possiamo andare avanti trisecando sempre allo stesso modo, riuscendo quindi a trovare la moneta falsa con le rimanenti $n - 2$ pesate.

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.

[xXStephXx]

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

[Federico II]

Avanti pure col prossimo

[matematto]

Ma qui non è andato avanti nessuno??

[Ale99]

Em , e qui ?

[Ale99]

Credo sia il caso che qualcuno posti un nuovo problema ...