Tredici monete

Il forum di Base5, dove è possibile postare problemi, quiz, indovinelli, rompicapo, enigmi e quant'altro riguardi la matematica ricreativa e oltre.

Moderatori: Gianfranco, Bruno

Rispondi
Dani Ferrari
Livello 4
Livello 4
Messaggi: 154
Iscritto il: mar apr 16, 2013 11:44 pm

Tredici monete

Messaggio da Dani Ferrari »

Avete 13 monete, esteriormente identiche. Due di queste sono false, e pertanto hanno un peso minore delle altre (e uguale fra loro). Con una bilancia a due piatti e senza pesi, in quattro pesate trovare le due monete false.

Nota: questo è il primo problema che ho inventato io, tanto tanto tempo fa.

Dani

Dani Ferrari
Livello 4
Livello 4
Messaggi: 154
Iscritto il: mar apr 16, 2013 11:44 pm

Re: Tredici monete

Messaggio da Dani Ferrari »

Ehi, siete tutti morti? Non è un problema semplice semplice, ma certamente non è neppure fra quelli tremendi. Per metterci in moto le rotelline, vi do un altro problema simile, ma molto più facile.

Dani

Carola
Livello 2
Livello 2
Messaggi: 36
Iscritto il: mer giu 19, 2013 1:58 pm

Re: Tredici monete

Messaggio da Carola »

Forse si può risolvere togliendo 3 monete dalle 13 totali, ottenendo in questo modo due gruppi uno da tre ( che tengo in disparte) e uno da 10, che suddivido in due gruppi ulteriori da 5 monete ciascuno per poi ragionare su questi ultimi?

Dani Ferrari
Livello 4
Livello 4
Messaggi: 154
Iscritto il: mar apr 16, 2013 11:44 pm

Re: Tredici monete

Messaggio da Dani Ferrari »

Ma quello che ho scritto in "altre tredici monete", nella dimostrazione del limite 13, il lemma, non lo ha letto nessuno?

Dani

Carola
Livello 2
Livello 2
Messaggi: 36
Iscritto il: mer giu 19, 2013 1:58 pm

Re: Tredici monete

Messaggio da Carola »

sì, l'ho vista... ma il mio ragionamento ha un senso ?

Dani Ferrari
Livello 4
Livello 4
Messaggi: 154
Iscritto il: mar apr 16, 2013 11:44 pm

Re: Tredici monete

Messaggio da Dani Ferrari »

L'hai vista ma non hai capito una mazza. Altrimenti non faresti domande così cretine.

Dani

Carola
Livello 2
Livello 2
Messaggi: 36
Iscritto il: mer giu 19, 2013 1:58 pm

Re: Tredici monete

Messaggio da Carola »

Non mi sarà di grande aiuto, ma ringrazio comunque per il " Cretino" !

Dani Ferrari
Livello 4
Livello 4
Messaggi: 154
Iscritto il: mar apr 16, 2013 11:44 pm

Re: Tredici monete

Messaggio da Dani Ferrari »

Poiché questo problema resta a dormire, vi do una spinta. Anzitutto prendete (come vi ho già detto di fare) "Altre 13 monete e una bilancia", leggetevi la dimostrazione del limite di 13 monete (non ce l'ho messa per fare una dimostrazione, ce l'ho messa perché voi impariate qualcosa), e cacciatevi bene in testa il lemma.
Tornando ora al problema attuale:
- quante sono inizialmente le soluzioni possibili (SP)?
- a quante si devono ridurre con la prima pesata?
- quale deve essere per conseguenza la prima pesata?
- a quante si debbono ridurre le SP con la seconda pesata?
- ci sono varie seconde pesate possibili: trovatene una per ciascuno dei due esiti possibili della prima pesata (piatti pari o sbilanciati).

Se riuscite a fare questo (e a capire bene quello che fate), poi le SP si riducono a una manciata, facile trattarle - potete anche lasciar perdere. Ma solo se avete capito bene come funziona questa baracca.

Dani

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Tredici monete

Messaggio da Gianfranco »

Ci sono C(13,2) = 78 distinte sequenze di 13 monete con 11 buone + 2 false.
Ogni pesata della bilancia mi dà tre possibili risposte: <, =, >.

Con 1 pesata ho 3 possibili risposte.
Con 2 pesate ho 9 possibili risposte.
Con 3 pesate ho 27 possibili risposte.
Con 4 pesate ho 81 possibili risposte.
...
Poiché 81>78, immagino che 4 pesate diano informazioni sufficienti per trovare le monete false.

La situazione è questa:
1 : 0011111111111
2 : 0101111111111
3 : 0110111111111
4 : 0111011111111
5 : 0111101111111
6 : 0111110111111
7 : 0111111011111
8 : 0111111101111
9 : 0111111110111
10 : 0111111111011
11 : 0111111111101
12 : 0111111111110
13 : 1001111111111
14 : 1010111111111
15 : 1011011111111
16 : 1011101111111
17 : 1011110111111
18 : 1011111011111
19 : 1011111101111
20 : 1011111110111
21 : 1011111111011
22 : 1011111111101
23 : 1011111111110
24 : 1100111111111
25 : 1101011111111
26 : 1101101111111
27 : 1101110111111
28 : 1101111011111
29 : 1101111101111
30 : 1101111110111
31 : 1101111111011
32 : 1101111111101
33 : 1101111111110
34 : 1110011111111
35 : 1110101111111
36 : 1110110111111
37 : 1110111011111
38 : 1110111101111
39 : 1110111110111
40 : 1110111111011
41 : 1110111111101
42 : 1110111111110
43 : 1111001111111
44 : 1111010111111
45 : 1111011011111
46 : 1111011101111
47 : 1111011110111
48 : 1111011111011
49 : 1111011111101
50 : 1111011111110
51 : 1111100111111
52 : 1111101011111
53 : 1111101101111
54 : 1111101110111
55 : 1111101111011
56 : 1111101111101
57 : 1111101111110
58 : 1111110011111
59 : 1111110101111
60 : 1111110110111
61 : 1111110111011
62 : 1111110111101
63 : 1111110111110
64 : 1111111001111
65 : 1111111010111
66 : 1111111011011
67 : 1111111011101
68 : 1111111011110
69 : 1111111100111
70 : 1111111101011
71 : 1111111101101
72 : 1111111101110
73 : 1111111110011
74 : 1111111110101
75 : 1111111110110
76 : 1111111111001
77 : 1111111111010
78 : 1111111111100

Quale pesata fare per prima?

PRIMA PESATA
Poiché dopo averla fatta, me ne rimangono 3, dev'essere una pesata che mi riduca il numero di casi da esaminare a N<27.

Vediamo, se ne confronto 4+4 ho (con un po' di calcolo combinatorio):
a) bilancia = in 26 casi;
b) bilancia > in 26 casi;
c) bilancia < in 26 casi;
OK, per un pelo!
Il primo confronto da fare è 4+4.

Per esempio, supponiamo che la bilancia sia =
Dobbiamo allora esaminare i seguenti casi:


4 : 0111011111111 *
5 : 0111101111111 *
6 : 0111110111111 *
7 : 0111111011111 *
15 : 1011011111111 *
16 : 1011101111111 *
17 : 1011110111111 *
18 : 1011111011111 *
25 : 1101011111111 *
26 : 1101101111111 *
27 : 1101110111111 *
28 : 1101111011111 *
34 : 1110011111111 *
35 : 1110101111111 *
36 : 1110110111111 *
37 : 1110111011111 *
69 : 1111111100111 *
70 : 1111111101011 *
71 : 1111111101101 *
72 : 1111111101110 *
73 : 1111111110011 *
74 : 1111111110101 *
75 : 1111111110110 *
76 : 1111111111001 *
77 : 1111111111010 *
78 : 1111111111100 *

Per l'eventuale seconda pesata, aspetto un segno...
Pace e bene a tutti.
Gianfranco

modulocomplicato
Livello 4
Livello 4
Messaggi: 122
Iscritto il: lun ott 01, 2012 5:30 pm

Re: Tredici monete

Messaggio da modulocomplicato »

Per la prima volta vedo che i toni escono dai binari e me ne rammarico perchè diversamente dal sito dei saccentoni di matematicament.... i toni erano sempre stati sempre cordiali verso tutti... anche verso gli ignorantoni come me...

I problemi non hanno quasi mai una unica soluzione complicata e quando si sa che ce l'hanno a me interessa capire se c'è una souzione più diretta, rapida ed intelligente che ci insegni qualcosa... la forza bruta è una vera pizza.

Ciao
Stefano

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Tredici monete

Messaggio da Gianfranco »

Ciao Stefano,
Hai scritto
...a me interessa capire se c'è una souzione più diretta, rapida ed intelligente che ci insegni qualcosa...
Perfettamente d'accordo. Un problema interessante, alla fine deve insegnare qualcosa a ciascuno... secondo i rispettivi livelli di conoscenza.
Per me effettivamente questo problema è difficile, ma ci sto pensando. Non troppo, perché devo anche lavorare per sbarcare il lunario.
L'ho affidato all'inconscio e ogni tanto vado a vedere se ha scoperto qualcosa.

Hai scritto.
la forza bruta è una vera pizza.
Con simpatia: perché, non ti piace la pizza? A me piace, margherita, quattro stagioni, capricciosa, ai funghi, ..., sottile, spessa, purché fatta veramente bene! :D
A parte gli scherzi, sono sicuro che anche i matematici più puristi, in certi casi gustano la pizza.
La pizza li aiuta a esplorare varie situazioni, il che può essere utile nei problemi combinatori.
Poi, però, quando comunicano i loro risultati finali, -giustamente- presentano la ricetta più bella, per esempio Salmone in guazzetto di vongole e zucchine.
Pace e bene a tutti.
Gianfranco

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Tredici monete

Messaggio da Gianfranco »

Lo so che questo post è quasi insopportabile, ma vorrei concludere.
Devo trovare una pesata che divida i 26 possibili casi in 3 parti formate da non più di 9 casi ciascuna.

Per esempio confrontare 6+6 non va bene perché i risultati possibili sono:
a) bilancia = in 8 casi;
b) bilancia > in 10 casi; (NO!!!)
c) bilancia < in 8 casi;

Invece, confrontando: 3, 5, 7, 9 con 2, 4, 10, 13 si ottiene:
a) bilancia = in 9 casi;
b) bilancia > in 9 casi;
c) bilancia < in 8 casi;

Codice: Seleziona tutto

 4 :   0  1  1  1  0  1  1  1  1  1  1  1  1  <<<
 5 :   0  1  1  1  1  0  1  1  1  1  1  1  1  ===
 6 :   0  1  1  1  1  1  0  1  1  1  1  1  1  <<<
 7 :   0  1  1  1  1  1  1  0  1  1  1  1  1  ===
 15 :  1  0  1  1  0  1  1  1  1  1  1  1  1  ===
 16 :  1  0  1  1  1  0  1  1  1  1  1  1  1  >>>
 17 :  1  0  1  1  1  1  0  1  1  1  1  1  1  ===
 18 :  1  0  1  1  1  1  1  0  1  1  1  1  1  >>>
 25 :  1  1  0  1  0  1  1  1  1  1  1  1  1  <<<
 26 :  1  1  0  1  1  0  1  1  1  1  1  1  1  <<<
 27 :  1  1  0  1  1  1  0  1  1  1  1  1  1  <<<
 28 :  1  1  0  1  1  1  1  0  1  1  1  1  1  <<<
 34 :  1  1  1  0  0  1  1  1  1  1  1  1  1  ===
 35 :  1  1  1  0  1  0  1  1  1  1  1  1  1  >>>
 36 :  1  1  1  0  1  1  0  1  1  1  1  1  1  ===
 37 :  1  1  1  0  1  1  1  0  1  1  1  1  1  >>>
 69 :  1  1  1  1  1  1  1  1  0  0  1  1  1  ===
 70 :  1  1  1  1  1  1  1  1  0  1  0  1  1  <<<
 71 :  1  1  1  1  1  1  1  1  0  1  1  0  1  <<<
 72 :  1  1  1  1  1  1  1  1  0  1  1  1  0  ===
 73 :  1  1  1  1  1  1  1  1  1  0  0  1  1  >>>
 74 :  1  1  1  1  1  1  1  1  1  0  1  0  1  >>>
 75 :  1  1  1  1  1  1  1  1  1  0  1  1  0  >>>
 76 :  1  1  1  1  1  1  1  1  1  1  0  0  1  ===
 77 :  1  1  1  1  1  1  1  1  1  1  0  1  0  >>>
 78 :  1  1  1  1  1  1  1  1  1  1  1  0  0  >>>

Esaminiamo per esempio i 9 casi in cui la bilancia è >
 16 :  1  0  1  1  1  0  1  1  1  1  1  1  1  >>>
 18 :  1  0  1  1  1  1  1  0  1  1  1  1  1  >>>
 35 :  1  1  1  0  1  0  1  1  1  1  1  1  1  >>>
 37 :  1  1  1  0  1  1  1  0  1  1  1  1  1  >>>
 73 :  1  1  1  1  1  1  1  1  1  0  0  1  1  >>>
 74 :  1  1  1  1  1  1  1  1  1  0  1  0  1  >>>
 75 :  1  1  1  1  1  1  1  1  1  0  1  1  0  >>>
 77 :  1  1  1  1  1  1  1  1  1  1  0  1  0  >>>
 78 :  1  1  1  1  1  1  1  1  1  1  1  0  0  >>>
 

Alla prossima pesata (la 3°) dovrei ridurre il numero di casi a 3.
Confronto 4, 8, 10 con 2, 11, 13
a) bilancia = in 3 casi;
b) bilancia > in 3 casi;
c) bilancia < in 3 casi;

Codice: Seleziona tutto

 16 :  1  0  1  1  1  0  1  1  1  1  1  1  1  >>>
 18 :  1  0  1  1  1  1  1  0  1  1  1  1  1  ===
 35 :  1  1  1  0  1  0  1  1  1  1  1  1  1  <<<
 37 :  1  1  1  0  1  1  1  0  1  1  1  1  1  <<<
 73 :  1  1  1  1  1  1  1  1  1  0  0  1  1  ===
 74 :  1  1  1  1  1  1  1  1  1  0  1  0  1  <<<
 75 :  1  1  1  1  1  1  1  1  1  0  1  1  0  ===
 77 :  1  1  1  1  1  1  1  1  1  1  0  1  0  >>>
 78 :  1  1  1  1  1  1  1  1  1  1  1  0  0  >>>
A questo punto è facile concludere.
Pace e bene a tutti.
Gianfranco

Gianfranco
Supervisore del sito
Supervisore del sito
Messaggi: 1708
Iscritto il: ven mag 20, 2005 9:51 pm
Località: Sestri Levante
Contatta:

Re: Tredici monete

Messaggio da Gianfranco »

CONCLUSIONE
Il ragionamento in sintesi, senza forza bruta.
Il problema è il seguente:
Date 12 monete di cui 2 false (più leggere), individuare le 2 monete false con 4 pesate in una bilancia a bracci uguali.

Ci sono C(13,2) = 78 distinte sequenze di 13 monete con 11 buone + 2 false.
Ogni pesata della bilancia mi dà 3 possibili risposte: <, =, >.

Perciò con $n$ pesate posso ottenere $3^n$ risposte distinte.
In particolare, con 4 pesate: $3^4=81$

Poiché 81>78, immagino che 4 pesate diano informazioni sufficienti per trovare le monete false.

Con la prima pesata confronto 4+4 monete.
Il calcolo combinatorio mi dice che avrò i possibili risultati:
a) bilancia = in 26 casi;
b) bilancia > in 26 casi;
c) bilancia < in 26 casi;

Mi rimangono 3 pesate.

Poiché $3^3=27>26$, posso farcela.

Con la seconda pesata, scegliendo opportunamente 4+4 monete, posso ottenere:
a) bilancia = in 9 casi;
b) bilancia > in 9 casi;
c) bilancia < in 8 casi;
Mi rimangono 2 pesate e la scelta fra 8 o 9 casi. OK

Poiché $3^2=9>=9>8$, posso farcela.

Alla terza pesata, confronto opportunamente 3+3 monete ottenendo
a) bilancia = in 3 casi;
b) bilancia > in 3 casi;
c) bilancia < in 3 casi;

La scelta per la quarta pesata è immediata.

Sara corretto?
Boh?
Pace e bene a tutti.
Gianfranco

Dani Ferrari
Livello 4
Livello 4
Messaggi: 154
Iscritto il: mar apr 16, 2013 11:44 pm

Re: Tredici monete

Messaggio da Dani Ferrari »

Si, Gianfranco, il ragionamento è proprio questo. Prima di fare una pesata, si sa già come deve ripartire le soluzioni possibili; si prova, se le ripartisce come richiesto è corretta, altrimenti se ne prova un'altra.
Per la seconda pesata, conviene chiamare A le monete su un piatto, B quelle sull'altro, C le 5 lasciate a terra. Se i piatti sono pari, restano 16 soluzioni AB e 10 sol. CC; se un piatto sale, diciamo A, restano 6 soluzioni AA e 20 AC. Di seconde pesate che funzionano ce ne sono parecchie; se ne prova una, si conta, e si sa subito se è giusta o no.

Dani

Rispondi