21. Ancora monete false

[Federico II]

Siano $n$ e $k$ due numeri naturali tali che $n\geq3$ e $k\geq6$. Su un tavolo ci sono una bilancia a due piatti e $k$ monete, di cui una e una sola è falsa. Le monete vere hanno tutte lo stesso peso, mentre quella falsa ha un peso diverso, ma non si sa se tale peso è maggiore o minore di quello delle monete vere. La differenza di peso è molto inferiore al peso di una moneta, ma è comunque percettibile dalla bilancia. Si sa che, effettuando al più $n$ pesate con la bilancia a due piatti, è sempre possibile determinare univocamente la moneta falsa. Determinare, in funzione di $n$, il massimo valore che può assumere $k$.

[Toadino2]

Faccio un tentativo...

Testo nascosto:

Determiniamo tre insiemi: ad ogni pesata chiameremo S l'insieme delle monete poste sul piatto sinistro, D quello delle monete sul piatto destro ed M quello delle monete non pesate. Nessuna moneta può non stare in un insieme.

Ponendo per un attimo $n=1$ vediamo che il massimo k è 3, perché se ci fossero quattro monete, uno dei tre insiemi avrebbe più di 2 elementi, e se questo risultasse contenente la moneta falsa questa non sarebbe determinabile non essendo possibili ulteriori pesate.
Dunque, per N=2 un gruppo può contenere tre elementi al massimo, perché tutti potrebbero risultare incriminati dopo la prima pesata, e se un gruppo ne avesse più di 3 per quanto detto prima la moneta sarebbe irreperibile con una sola pesata. Dunque k=9.
Allo stesso modo se N=3 ogni insieme può contenere 9 elementi al massimo, dunque k=27.

Vediamo che ad ogni passaggio il k iniziale, 3, viene nuovamente moltiplicato per 3; dunque la formula cercata è $3^n=k$.

[Federico II]

Rileggi bene il testo: non si sa se la moneta falsa è più leggera o più pesante delle altre (altrimenti che cambiava dal problema 19 di questa staffetta a parte che questo è un caso generale?). Se fosse $n=1$ e $k=3$ (giusto riallacciandomi a quello che hai detto, le ipotesi restano comunque $n\geq3$ e $k\geq6$) non sarebbe sempre possibile trovare la moneta falsa: se i due piatti non sono in equilibrio quando pesi due monete non puoi sapere quale delle due sia incriminata perché non sai se deve essere più leggera o più pesante.

[Toadino2]

Ah, scusami, è vero

[Gerald Lambeau]

Se è

Testo nascosto:

[tex]k=2^{n-1}[/tex]

posto la soluzione.

[cip999]

Dovrebbe essere [tex]k = 2^n[/tex] (ormai andiamo a tentativi... ). Se è giusta, dopo cena posto il procedimento.

[Gerald Lambeau]

cip, hai considerato il caso peggiore in cui arrivi una pesata con una moneta per piatto e una situazione di non equilibrio?

[xXStephXx]

Non so se è così scontato perchè ad esempio

Testo nascosto:

Se hai una potenza di $3$ sprecando le prime due pesate si riesce a capire se la moneta falsa pesa di più o di meno, dopodichè si può trisecare ogni volta

[cip999]

Bah, io ho fatto un ragionamento di questo genere.

Supponiamo di avere [tex]2^n[/tex] monete, con [tex]n \geq 2[/tex]. Le dividiamo in [tex]4[/tex] gruppi da [tex]2^{n - 2}[/tex] monete ciascuno, ne prendiamo [tex]2[/tex] e li pesiamo. Ora possono presentarsi due casi: se la bilancia è in equilibrio, allora la moneta falsa si troverà tra le restanti [tex]2^{n - 1}[/tex]; viceversa, se la bilancia pende da un lato, la moneta falsa sarà in uno dei due gruppi pesati (non sappiamo in quale). In ogni caso, ci siamo ricondotti al caso con [tex]2^{n - 1}[/tex] monete.

Procedendo in questo modo, con [tex]2^{n - 1}[/tex] pesate riusciamo a isolare un gruppo di [tex]2[/tex] monete che contiene sicuramente quella falsa. Ne prendiamo una qualunque, e la confrontiamo con una di quelle scartate in precedenza (tanto [tex]n \geq 3[/tex] per ipotesi): se la bilancia è in equilibrio, la moneta falsa è l'altra; altrimenti, è quella pesata (e in questo caso possiamo anche sapere se differisce in difetto o in eccesso).

Ora non ci resta che mostrare che [tex]2^n[/tex] è effettivamente il massimo. Infatti, osserviamo che pesare due quantità diverse di monete non fornisce alcuna informazione significativa, dal momento che il peso della moneta falsa differisce da quello di una moneta non truccata di una quantità strettamente minore di esso.
Quindi, con ogni pesata riusciamo a determinare solo se la moneta truccata è tra quelle pesate o non lo è. Risulta evidente, a questo punto, che con [tex]2^n + 1[/tex] monete non siamo sempre in grado di riconoscere la moneta falsa con sicurezza, avendo a disposizione solo [tex]n[/tex] pesate.

[Gerald Lambeau]

Quindi dici che la soluzione è

Testo nascosto:

[tex]3^{n-1}[/tex]?

Mi sa che ha ragione Steph