21. Ancora monete false

Esercizi sulla verità delle proposizioni e problemi che non sembrano rientrare in nessun'altra categoria.

21. Ancora monete false

Messaggioda Federico II » 09/02/2015, 14:25

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$.
Il responsabile della sala seminari
Avatar utente
Federico II
 
Messaggi: 431
Iscritto il: 14/05/2014, 14:53

Re: 21. Ancora monete false

Messaggioda Toadino2 » 09/02/2015, 14:48

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$.
C'è chi ha definito ogni persona come una guerriera della vita... ed allora ogni matematico combatte una guerra eterna contro i numeri per conquistarli: e più saremo in tanti a combattere tali battaglie, prima la vinceremo. Cit.Me
Toadino2
 
Messaggi: 589
Iscritto il: 27/11/2014, 18:05

Re: 21. Ancora monete false

Messaggioda Federico II » 09/02/2015, 15:50

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.
Il responsabile della sala seminari
Avatar utente
Federico II
 
Messaggi: 431
Iscritto il: 14/05/2014, 14:53

Re: 21. Ancora monete false

Messaggioda Toadino2 » 09/02/2015, 18:02

Ah, scusami, è vero :)
C'è chi ha definito ogni persona come una guerriera della vita... ed allora ogni matematico combatte una guerra eterna contro i numeri per conquistarli: e più saremo in tanti a combattere tali battaglie, prima la vinceremo. Cit.Me
Toadino2
 
Messaggi: 589
Iscritto il: 27/11/2014, 18:05

Re: 21. Ancora monete false

Messaggioda Gerald Lambeau » 09/02/2015, 19:32

Se è
Testo nascosto:
[tex]k=2^{n-1}[/tex]
posto la soluzione.
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 899
Iscritto il: 07/01/2015, 18:18

Re: 21. Ancora monete false

Messaggioda cip999 » 09/02/2015, 19:52

Dovrebbe essere [tex]k = 2^n[/tex] (ormai andiamo a tentativi... :lol: ). Se è giusta, dopo cena posto il procedimento. ;)
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre.
Albert Einstein
cip999
 
Messaggi: 583
Iscritto il: 26/02/2014, 16:47

Re: 21. Ancora monete false

Messaggioda Gerald Lambeau » 09/02/2015, 20:03

cip, hai considerato il caso peggiore in cui arrivi una pesata con una moneta per piatto e una situazione di non equilibrio?
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 899
Iscritto il: 07/01/2015, 18:18

Re: 21. Ancora monete false

Messaggioda xXStephXx » 09/02/2015, 20:21

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
xXStephXx
 
Messaggi: 625
Iscritto il: 23/03/2013, 18:12

Re: 21. Ancora monete false

Messaggioda cip999 » 09/02/2015, 20:24

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.
Non so con quali armi si combatterà la Terza Guerra Mondiale, ma la Quarta sì: con bastoni e pietre.
Albert Einstein
cip999
 
Messaggi: 583
Iscritto il: 26/02/2014, 16:47

Re: 21. Ancora monete false

Messaggioda Gerald Lambeau » 09/02/2015, 20:29

Quindi dici che la soluzione è
Testo nascosto:
[tex]3^{n-1}[/tex]?
Mi sa che ha ragione Steph :D
"I matematici non realizzano nulla... semplicemente scoprono e dimostrano verità intrinseche riguardanti tutto ciò che esiste, ovvietà e banalità per una mente superiore, perfetta. Ed è quello il mio obiettivo!"
Cit. Marco (mio vero nome)
Gerald Lambeau
 
Messaggi: 899
Iscritto il: 07/01/2015, 18:18

Prossimo

Torna a Logica e Matematizzazione

Chi c’è in linea

Visitano il forum: Nessuno e 1 ospite