Tredici monete
Moderatori: Gianfranco, Bruno
Questo forum è una sezione del PORTALE DI BASE CINQUE
-
- Livello 4
- Messaggi: 154
- Iscritto il: mar apr 16, 2013 11:44 pm
Tredici monete
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
Nota: questo è il primo problema che ho inventato io, tanto tanto tempo fa.
Dani
-
- Livello 4
- Messaggi: 154
- Iscritto il: mar apr 16, 2013 11:44 pm
Re: Tredici monete
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
Dani
Re: Tredici monete
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?
-
- Livello 4
- Messaggi: 154
- Iscritto il: mar apr 16, 2013 11:44 pm
Re: Tredici monete
Ma quello che ho scritto in "altre tredici monete", nella dimostrazione del limite 13, il lemma, non lo ha letto nessuno?
Dani
Dani
Re: Tredici monete
sì, l'ho vista... ma il mio ragionamento ha un senso ?
-
- Livello 4
- Messaggi: 154
- Iscritto il: mar apr 16, 2013 11:44 pm
Re: Tredici monete
L'hai vista ma non hai capito una mazza. Altrimenti non faresti domande così cretine.
Dani
Dani
Re: Tredici monete
Non mi sarà di grande aiuto, ma ringrazio comunque per il " Cretino" !
-
- Livello 4
- Messaggi: 154
- Iscritto il: mar apr 16, 2013 11:44 pm
Re: Tredici monete
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
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
-
- Supervisore del sito
- Messaggi: 1720
- Iscritto il: ven mag 20, 2005 9:51 pm
- Località: Sestri Levante
- Contatta:
Re: Tredici monete
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...
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
Gianfranco
-
- Livello 4
- Messaggi: 122
- Iscritto il: lun ott 01, 2012 5:30 pm
Re: Tredici monete
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
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
-
- Supervisore del sito
- Messaggi: 1720
- Iscritto il: ven mag 20, 2005 9:51 pm
- Località: Sestri Levante
- Contatta:
Re: Tredici monete
Ciao Stefano,
Hai scritto
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.
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.
Hai scritto
Perfettamente d'accordo. Un problema interessante, alla fine deve insegnare qualcosa a ciascuno... secondo i rispettivi livelli di conoscenza....a me interessa capire se c'è una souzione più diretta, rapida ed intelligente che ci insegni qualcosa...
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.
Con simpatia: perché, non ti piace la pizza? A me piace, margherita, quattro stagioni, capricciosa, ai funghi, ..., sottile, spessa, purché fatta veramente bene!la forza bruta è una vera pizza.
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
- Messaggi: 1720
- Iscritto il: ven mag 20, 2005 9:51 pm
- Località: Sestri Levante
- Contatta:
Re: Tredici monete
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;
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;
A questo punto è facile 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 >>>
Pace e bene a tutti.
Gianfranco
Gianfranco
-
- Supervisore del sito
- Messaggi: 1720
- Iscritto il: ven mag 20, 2005 9:51 pm
- Località: Sestri Levante
- Contatta:
Re: Tredici monete
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?
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
Gianfranco
-
- Livello 4
- Messaggi: 154
- Iscritto il: mar apr 16, 2013 11:44 pm
Re: Tredici monete
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
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