Il resto al supermercato
ciao ragazzi, vi ricordate di me?
mi e' stato proposto un problema simile al seguente:
Io da rozzo fisico so risolvere il problema brute-force (10 linee di codice, 1mln di tentativi finche la media non converge a poco piu' di 0.15)
Credete esista una soluzione analitica per un problema simile?
Vi mostro il mio goffo tentativo... Potete pure dirmi se e' tutto da rifare!
mi e' stato proposto un problema simile al seguente:
Immagina di essere al supermercato, e devi pagare 1E. Estrai dalla tasca una moneta alla volta finche' non raggiungi la somma da pagare. Qual e' il resto che otterrai in media? Assumiamo di avere monete da 5,10,20,50 centesimi e che esse abbiano sempre la stessa probabilita' di uscire dalla tua tasca
Io da rozzo fisico so risolvere il problema brute-force (10 linee di codice, 1mln di tentativi finche la media non converge a poco piu' di 0.15)
Credete esista una soluzione analitica per un problema simile?
Vi mostro il mio goffo tentativo... Potete pure dirmi se e' tutto da rifare!
Risposte
Se valutiamo quale possa essere stata l'ultima moneta estratta, possiamo dire che:
se è uscita il 5 cent, il resto è 0.
se è uscita il 10 cent, il resto è 0, oppure 5 cent
... e cosi' via...
otteniamo, 17 possibili situazioni con un totale di 260 cents di resto, per una media pari a 15,29411.
se è uscita il 5 cent, il resto è 0.
se è uscita il 10 cent, il resto è 0, oppure 5 cent
... e cosi' via...
otteniamo, 17 possibili situazioni con un totale di 260 cents di resto, per una media pari a 15,29411.
bravo, hai ragione. e' piu' facile ragionando al "contrario"
Mi permetto di dissentire.
Vero che ci sono 17 possibili situazioni di resto, ma non tutte sono equipropabili.
Anzi, a dir la verità abbiamo 10 resti diversi possibili: 0-5-10-15-20-25-30-35-40-45.
Dando per scontato che su 80 "resti", tutti escano con la probabilità dovuta, abbiamo:
0 - 37 volte = 0
5 - 17 volte = 85
10 - 7 volte = 70
15 - 7 volte = 105
20 - 2 volte = 40
25 - 2 volte = 50
30 - 2 volte = 60
35 - 2 volte = 70
40 - 2 volte = 80
45 - 2 volte = 90
Per un totale di resti pari a 650. Da cui $650/80=8,125$
Vero che ci sono 17 possibili situazioni di resto, ma non tutte sono equipropabili.
Anzi, a dir la verità abbiamo 10 resti diversi possibili: 0-5-10-15-20-25-30-35-40-45.
Dando per scontato che su 80 "resti", tutti escano con la probabilità dovuta, abbiamo:
0 - 37 volte = 0
5 - 17 volte = 85
10 - 7 volte = 70
15 - 7 volte = 105
20 - 2 volte = 40
25 - 2 volte = 50
30 - 2 volte = 60
35 - 2 volte = 70
40 - 2 volte = 80
45 - 2 volte = 90
Per un totale di resti pari a 650. Da cui $650/80=8,125$
Possiamo provare a scendere nell'argomento in profondità.
Il mio ragionamento nasce dall'idea che l'ultima moneta estratta possa essere un 5, un 10 un 20 un 50 cents.
Ed ognuna di essa può generare un resto, come mostrato nella tabella.
Dando lo stesso peso (e qui ci sta un piccolo margine di errore), alle varie situazioni, ottengo la soluzione.
Ho fatto anche io una simulazione, ed il mio risultato finale è un po meno di 15 (wedge diceva un pò di più...), ma è molto lontana dal tuo 8,...
... a dopo per i risultati ...
Il mio ragionamento nasce dall'idea che l'ultima moneta estratta possa essere un 5, un 10 un 20 un 50 cents.
Ed ognuna di essa può generare un resto, come mostrato nella tabella.
Dando lo stesso peso (e qui ci sta un piccolo margine di errore), alle varie situazioni, ottengo la soluzione.
Ho fatto anche io una simulazione, ed il mio risultato finale è un po meno di 15 (wedge diceva un pò di più...), ma è molto lontana dal tuo 8,...
... a dopo per i risultati ...
Secondo me, per un calcolo preciso è necessario ricostruire tutti i casi possibili che si possono presentare, da dopo due estrazioni (entrambe da 50 cents, resto = 0) a fino dopo 20 estrazioni tutte da 5 cents (e resto = 0).
In pratica:
1 estrazione: $ 1/4 $ probabilità di avere 5 o 10 o 20 o 50 cents
2 estrazione: $ 1/16 $ probabilità di avere 10 o 20 o 40 o 100 cents e $ 1/8 $ probabilità di avere 15 o 25 o 30 o 55 o 60 o 70 cents
3 estrazione: $ 1/64 $ probabilità di avere 15 cents, $ 1/32 $ probabilità di avere 105 o 110 o 120 cents, $ 3/64 $ probabilità di avere 20 o 25 o 40 o 45 o 50 o 70 o 90 cents, $ 1/16 $ probabilità di avere 30 o 60 cents e $ 3/32 $ probabilità di avere 35 o 65 o 75 o 80 cents.
4 estrazione: .......................................
..........................................................
20 estrazione: $ (1/4)^20 $ probabilità di avere 100 cents
A questo punto si moltiplicano il numero dei valori dei resti oltre i 100 cents per la loro probabilità e si fa la somma.
In pratica:
1 estrazione: $ 1/4 $ probabilità di avere 5 o 10 o 20 o 50 cents
2 estrazione: $ 1/16 $ probabilità di avere 10 o 20 o 40 o 100 cents e $ 1/8 $ probabilità di avere 15 o 25 o 30 o 55 o 60 o 70 cents
3 estrazione: $ 1/64 $ probabilità di avere 15 cents, $ 1/32 $ probabilità di avere 105 o 110 o 120 cents, $ 3/64 $ probabilità di avere 20 o 25 o 40 o 45 o 50 o 70 o 90 cents, $ 1/16 $ probabilità di avere 30 o 60 cents e $ 3/32 $ probabilità di avere 35 o 65 o 75 o 80 cents.
4 estrazione: .......................................
..........................................................
20 estrazione: $ (1/4)^20 $ probabilità di avere 100 cents
A questo punto si moltiplicano il numero dei valori dei resti oltre i 100 cents per la loro probabilità e si fa la somma.
Ho fatto i calcoli (come indicato nel messaggio precedente) con un foglio excel e il risultato è 14,66111415 centesimi.
Forse mi sono espresso male....
Per Umby.
L'ultima moneta può essere da 5 cents. Probabilità $1/4$. Resto 0.
L'ultima moneta può essere da 10 cents. Probabilità $1/4$.Resto 0 $1/8$ Resto 5 $1/8$
L'ultima moneta può essere da 20 cents. Probabilità $1/4$, Resto 0 $1/32$ Resto 5 $1/32$ Resto 10 $1/32$ Resto 15 $1/32$
L'ultima moneta può essere da 50 cents. Probabilità $1/4$. Resto 0 $1/40$ Resto 5 $1/40$ Resto 10 $1/40$ Resto 15 $1/40$
Resto 20 $1/40$ Resto 25 $1/40$ Resto 30 $1/40$ Resto 35 $1/40$ resto 40 $1/40$ Resto 45 $1/40$
Sommando il tutto si arriva al mio conteggio precedente in ottantesimi.
Spero vi renderete conto che il resto 0 non si presenta in 4 casi su 17, ma in 37 casi su 80. Ovvero quasi il 50% (46,25% per l'esattezza).
Per Nino.
Non sono in grado di fare i calcoli. Uso una calcolatrice da tavolo. E a $4^20$ la mia calcolatrice non ci arriva...E con excel non ho dimestichezza...
Però una cosa. Non è detto che se arrivi alla ventesima estrazione, questa sia 5. Potrebbe anche essere 10-20-50.
E del resto $0$, hai tenuto conto?
Voglio dire: hai probabilità $1/16$ di fare 100 in due "pescate". Hai probabilità $3/64$ di fare 100 in quattro "pescate". $81/1024$ di farlo in cinque. Etc...
Per Umby.
L'ultima moneta può essere da 5 cents. Probabilità $1/4$. Resto 0.
L'ultima moneta può essere da 10 cents. Probabilità $1/4$.Resto 0 $1/8$ Resto 5 $1/8$
L'ultima moneta può essere da 20 cents. Probabilità $1/4$, Resto 0 $1/32$ Resto 5 $1/32$ Resto 10 $1/32$ Resto 15 $1/32$
L'ultima moneta può essere da 50 cents. Probabilità $1/4$. Resto 0 $1/40$ Resto 5 $1/40$ Resto 10 $1/40$ Resto 15 $1/40$
Resto 20 $1/40$ Resto 25 $1/40$ Resto 30 $1/40$ Resto 35 $1/40$ resto 40 $1/40$ Resto 45 $1/40$
Sommando il tutto si arriva al mio conteggio precedente in ottantesimi.
Spero vi renderete conto che il resto 0 non si presenta in 4 casi su 17, ma in 37 casi su 80. Ovvero quasi il 50% (46,25% per l'esattezza).
Per Nino.
Non sono in grado di fare i calcoli. Uso una calcolatrice da tavolo. E a $4^20$ la mia calcolatrice non ci arriva...E con excel non ho dimestichezza...
Però una cosa. Non è detto che se arrivi alla ventesima estrazione, questa sia 5. Potrebbe anche essere 10-20-50.
E del resto $0$, hai tenuto conto?
Voglio dire: hai probabilità $1/16$ di fare 100 in due "pescate". Hai probabilità $3/64$ di fare 100 in quattro "pescate". $81/1024$ di farlo in cinque. Etc...
"superpippone":
Forse mi sono espresso male....
Per Umby.
A parte che non concordo sul tuo ragionamento, e poi ti spiego il perchè, dovresti rifare i tuoi calcoli, perchè dovresti considerare per la moneta di 20 cents, $1/16$ e non $1/32$.
Perchè non concordo, è presto detto:
Se io ti chiedessi: "Vinci un premio, se mi dici quale è l'ultima moneta estratta". Dal tuo ragionamento, mi aspetto che tu mi risponda "una qualsiasi delle 4 monete [visto che parti da 1/4 pero ognuna]".
Io invece ti risponderei "la moneta da 50 cents", ed intuitivamente direi che il ragionamento è abbastanza semplice. Questa moneta infatti ha circa (dico circa) 10 volte la p. di quella da 5 cents. Quindi, il rapportare le 17 possibilità ad 1/4 non è corretto.
A dopo per i dati....(che chiariscono in modo più preciso il tutto..)
"nino_":
Ho fatto i calcoli (come indicato nel messaggio precedente) con un foglio excel e il risultato è 14,66111415 centesimi.
Ho qualche millesimo di differenza... (ma la mia è una simulazione, dove sono state elaborati il 99% dei casi...)
Quindi, direi, che siamo arrivati allo stesso risultato..
"superpippone":
Non sono in grado di fare i calcoli. Uso una calcolatrice da tavolo. E a $4^20$ la mia calcolatrice non ci arriva...E con excel non ho dimestichezza...
Però una cosa. Non è detto che se arrivi alla ventesima estrazione, questa sia 5. Potrebbe anche essere 10-20-50.
E del resto $0$, hai tenuto conto?
Voglio dire: hai probabilità $1/16$ di fare 100 in due "pescate". Hai probabilità $3/64$ di fare 100 in quattro "pescate". $81/1024$ di farlo in cinque. Etc...
Certo, mi sono espresso male.
Volevo solo dire che 20 è certamente l'ultima estrazione possibile, perché, male che vada, alla ventesima estrazione si arriva a raggiungere o superare il traguardo di 100.
Infatti, con probabilità $ (1/4)^20 $ , il resto che si può ottenere è di 0, o 5, o 15, o 45 cents.
La procedura che ho adottato con un foglio excel è concettualmente semplice.
Ad ogni estrazione n da 1 a 20 (venti righe), cui è associata la probabilità $ (1/4)^n $ , calcolo il numero dei valori in cents che mano a mano si totalizzano (sommandosi).
Se si mettono questi valori (numero dei casi che possono verificarsi) in 29 colonne (da 5 a 145 cents, con passo 5 cents), il calcolo si può fare in modo ricorsivo, copiando semplicemente in ogni cella la somma dei contenuti nelle celle -1 (se si estraggono 5 cents), -2 (se si estraggono 10 cents), -4 (se si estraggono 20 cents) e -10 (se si estraggono 50 cents) della riga estrazione precedente.
Con l'avvertenza di interrompere le somme, eliminando l'addendo (o gli addendi) corrispondente (i), qualora nella riga precedente si sia giunti dopo la somma di 100 cents.
A titolo di curiosità, riporto i casi totali possibili, che, per ogni resto, sono:
0 = 48.007
5 = 36.419
10 = 16.047
15 = 28.218
20 = 1.623
25 = 2.853
30 = 5.019
35 = 8.825
40 = 15.522
45 = 27.296
Invece le probabilità di trovarsi con i vari resti sono:
0 = 0,266521
5 = 0,155526
10 = 0,127003
15 = 0,096976
20 = 0,075502
25 = 0,056527
30 = 0,063616
35 = 0,050481
40 = 0,058582
45 = 0,049267
Il resto atteso (14,66111415) si ottiene semplicemente sommando i prodotti dei valori del resto per la relativa probabilità di conseguirlo.
Un po di dati della simulazione, attendibili al 99.99%.
Nel riquadro in blue, i "17 resti", nella colonna "%" la p. che il resto si verifichi (mi sembra che coincidano con quelli di nino),
in basso a destra il "resto medio".
@Pippone: come vedi da questa tabella su 268M di lanci, ben 166M terminano con il resto da 50 cents, e soli 13M con la moneta da 5 cents.
Nel riquadro in blue, i "17 resti", nella colonna "%" la p. che il resto si verifichi (mi sembra che coincidano con quelli di nino),
in basso a destra il "resto medio".
@Pippone: come vedi da questa tabella su 268M di lanci, ben 166M terminano con il resto da 50 cents, e soli 13M con la moneta da 5 cents.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo