Newsgroup: it.hobby.enigmi
Titolo: 20merendine20

Per chi non l'avesse mai sentito, ecco il famoso problema delle 20
merendine:
Una famosa ditta (di cui taccio il nome per non fare pubblicita'), tuttora
allega ad ogni pacco delle sue merendine una sorpresina. L'intera collezione
di sorpresine e' composta da 20 esemplari diversi. Il mio grande sogno
sarebbe possedere l'intera collezione, per poterla sfoggiare con smisurato
orgoglio agli amici, in occasioni mondane.
  Percio' ogni giorno compero un pacco di disgustose merendine, finche'
avro' l'intera collezione (Uao!). Dopo il 19mo giorno, per ogni giorno che
passa la probabilita' di finire la collezione sale. Quando sara' piu' del
50%?
MF

50%?
Solo nel momento in cui sara' del 100%
La probabilita' non varia con continuita', ma a gradini, da zero a 5% a
100%.
Finche' hai 18 pezzi diversi (o meno di 18), la probabilita' che il prossimo
ti permetta di finire la collezione e' zero.
Quando hai trovato il 19.mo (non necessariamente dopo 19 giorni), la
probabilita' e' 5%.
Quando hai trovato il 20.mo,  la probabilita' e 100%.
ciao
Paolo

Paolo
Mi sono espresso male. Definiamo p(n) la probabilita' che, avendo comprato n
marendine, si sia in possesso dell'intera collezione ( o grazie all'n-esimo
acquisto o gia' da prima).
- con 0<n<20, p(n)=0.
- p(20) e' veramente molto bassa (circa 2 su 100.000.000 )
- lim p(n)=1 , per n -> inf
Qual e' il piu' piccolo n tale che p(n)>0.5?
ciao
MF

E' un problema piu' difficile di quanto possa sembrare a prima vista, ma
credo (o meglio, spero) di esserci arrivato. Dovrebbe essere 67 : se e'
giusto posto anche il ragionamento (che e' un po' lunghetto).
Fammi sapere, ciao.
--
Automatic posted from 
mail.tin.it
 [194.243.154.49]
via Mailgate Server - 
http://www.mailgate.org

 superiore al 50%.
Domenico, non ho mica capito bene come fai a ricavare il numero dei casi
favorevoli (quelli che contengono almeno 20 pezzi differenti), perche'
funziona? fammi qualche esempio con 22 o 23 acquisti in modo che mi
possa orientare.
La formula che ho postato nel rispondere a questo problema l'ho copiata
da un libro di matematica, ma da valori diversi dai tuoi.
La soluzione delle patate e' OK!!
ciao

possa orientare.
cerca "Markov" su matenigmici su mclink, Dario...
Dopo zero acquisti, hai zero premi. Allora P(0,0)=1,
e P(n,0)=0 per n>0 (n e' il numero di premi).
Ok... p(n,g) cosa sara'? (la probabilita' di avere n premi dopo g
giorni).
Beh, ieri dove stavamo? O avevamo lo stesso numero di premi, e abbiamo
comprato un premio gia' visto, O avevamo un premio in meno, e abbiamo
trovato un premio nuovo.
con che probabilita' avevamo n premi anche ieri? p(n,g-1). e con che
probabilita' siamo passati da quello stato in quello di oggi? n/20, visto
che il nostro premio scelto a caso dai 20 disponibili era uno degli n
gia' posseduti.
con che probabilita' avevamo n-1 premi ieri? p(n-1, g-1). e con che
probabilita' siamo passati da quello stato in quello di oggi?
(20-(n-1))/20, visto che il premio era fra i (20-(n-1)) non ancora trovati
all'epoca.
allora...
p(n,g) = p(n,g-1)*n/20 + p(n-1,g-1)*(20-(n-1))/20
Questo tipo di cosa si puo' benissimo fare con uno spreadsheet...
cerchiamo il primo g tale che p(20,g)>0.5
Possiamo anche calcolare il tempo medio necessario per prendere i 20 premi.
chiamiamo T(a,b) il tempo medio necessario per ottenere b premi in totale,
cominciando con a premi. ovviamente T(b,b)=0
altrimenti:
t(a,b)= 1 (perche' un giorno passera' comunque)
        +T(a,b)*(prob di comprare un premio gia' visto)
        +T(a+1,b)*(prob di comprare un premio nuovo)
      = 1 + T(a,b) * a/20 + T(a+1,b)* (20-a)/20
E allora possiamo calcolare T(0,20) cominciando con T(20,20) e calcolando
T(19,20), T(18,20) e cosi' via all'indietro.
-- 
Adam Atkinson (
gh...@mistral.co.uk
)
ZOOGE

67 giorni, secondo il mio spreadsheet.
-- 
Adam Atkinson (
gh...@mistral.co.uk
)
Anvedi oh che roba!

 cerca "Markov" su matenigmici su mclink, Dario...
Grazie Adam,
queste catene di Markov fanno miracoli, ma bisogna saperle adoperare,
dovro' studiarle meglio.

 wrote:
% cerca "Markov" su matenigmici su mclink, Dario...
Buon zio Markov (e aggiungerei anche zio Viterbi, perche` quello che hai
scritto tu e` in pratica un trellis).
.mau.

dovro' studiarle meglio.
eh si'. sono un'arma potentissima.
-- 
Adam Atkinson (
gh...@mistral.co.uk
)
Man is a giddy thing, and this is my conclusion.
(Much Ado About Nothing)


Ora se andate a vedere alla pagina:
http://freespace.virgin.net/ashley.england/Maths%20Puzzles%20Index.htm
sito che propone parecchi puzzles matematici, troverete che l'autore,
come risposta al problema 74, lo stesso delle merendine, dimostra che se
la probabilita' di un evento e' p, il numero di prove per ottenerlo e'
1/p. Seguendo questo ragionamento l'attesa media e' la somma di:
sorpresa    num.acquisti x ottenerla
1           1/(20/20)
2           1/(19/20)
3           1/(18/20)
.....
19          1/(2/20)
20          1/(1/20)
Con 3 righe di programma trovo che la somma e': 71.954793....
Ora capisco come e' stata ricavata la formula che avevo riportata nella
prima risposta.
dario

Con 3 righe di programma trovo che la somma e': 71.954793....
Certo. Anch'io trovo questo per l'attesa media, ma ci era stato chiesto di
trovare il primo giorno in cui c'era una probabilita' maggiore di 50%. :-)
-- 
Adam Atkinson (
gh...@mistral.co.uk
)
Volemo er verde!