Newsgroup: it.hobby.enigmi
Titolo: Memory

Abbiamo un certo numero di coppie (cioè uguali a due a due) di carte coperte
di cui non conosco la disposizione (un po come nel gioco Memory). Ogni turno
giro due carte, se queste sono uguali vengono rimosse, se sono diverse
vengono rigirate (messe cioè di nuovo in posizione coperta) e rimesse nella
loro posizione originaria.
Supponendo di avere una memoria perfetta (di ricordare cioè la posizione di
tutte le carte girate e non eliminate, in pratica è come se una volta
scoperte le carte e non ottenuta la coppia rimettessi le carte nella loro
posizione originaria NON capovolte) e di addottare una strategia ottimale in
quanti turni sono necessari in media per scoprire 10 carte (5 coppie)????
E' possibile una generalizzazione per n coppie?
Es: suppongo di avere due coppie (1,1,2,2) casualmente disposte
Il PRIMO TURNO posso sceglire 1,1 o 2,2 o 1,2. Nei primi due casi rimuovo la
coppia scoperta e al SECONDO TURNO scelgo le altre due carte (2,2) o (1,1) e
finisco il gioco in due turni. Se scelgo 1,2 al SECONDO TURNO scopro una
delle due carte non ancora scoperte e trovo  un 1 o un 2 che accoppio con la
carta corrispondente di cui conosco la posizione già dopo il primo turno. In
questo caso sarà necessario un TERZO TURNO per rimuovere la la seconda
coppia.
In media al primo turno giro una coppia (1,1 o 1,2) 1 volta su 3 e giro due
carte spaiate (1,2) 2 volta su 3.
Finisco in media dunque ogni 2*1/3 + 3*2/3 = 2.66 circa.
Saluti a tutti Paolo (Sperando di essere stato abbastanza chiaro).

(Tieni conto che questa soluzione e' stata partorita alle 08.40, con gli
annebbiamenti del caso)
VV
VV
VV
VV
VV
VV
VV
VV
VV
VV
VV
Beh, sicuramente possiamo calcolare i casi-limite.
Con n coppie, se mi va di culo (ma di bruttobruttobrutto 8-)), ad ogni coppia
girata becco una coppia effettiva, e quindi con n girate sono a posto; se invece
non ne azzecco una, con n-1 girate individuo la posizione di tutte le carte (
dovrei fare n girate, ma alla fine ho lo stesso caso di due coppie (quattro
carte coperte, di cui due note), e la posizione viene individuata per
esclusione), e con altre n girate becco tutte le coppie
Quindi la media deve essere compresa tra n e 2n-1
Scusa, ma a calcolare la media esatta a quest'ora proprio non ce la faccio, devo
aspettare che tutti i neuroni abbiano completato la procedura di connessione..
%-\
Massimo 8-]
P.S. Spero di non aver detto troppe castronerie...


 ha scritto nel messaggio
news:8cil9u$quv$1...@nslave1.tin.it...

Catene di Markov!
Dato che le carte sono disposte casualmente e ragioniamo in media, penso
proprio che la scelta della carta da girare tra quelle coperte mai girate
sia ininfluente, quindi decido di girare le carte in sequenza, dalla prima
all'ultima. Al limite posso anche pensare di tenere il mazzo in mano e
girare le carte sul tavolo una dopo l'altra, lasciandole scoperte se non ho
realizzato una coppia, oppure togliendole dal tavolo quando la realizzo.
Girando la prima carta di un nuovo tentativo, possono succedere due cose:
(A) la sua gemella e' gia' sul tavolo: aggiungo 1 al numero di tentativi,
tolgo le due carte e ricomincio con un altro tentativo;
(B) la sua gemella non e' sul tavolo: giro la seconda carta. A questo punto
ci sono tre casi:
(B1) la seconda e' uguale alla prima: aggiungo 1 al numero di tentativi e
tolgo le due carte dal tavolo;
(B2) la seconda e' uguale ad una carta precedentemente girata: aggiungo 2 al
numero di tentativi (perche' mi servira' un tentativo in piu' per girare la
coppia palesemente scoperta) e tolgo le due carte uguali dal tavolo;
(B3) la seconda e' una carta mai uscita: aggiungo 1 al numero dei tentativi
e vado avanti con una nuova coppia.
Una fase qualsiasi del solitario e' completamente caratterizzato da una
quadrupla di informazioni: <G=carte girate, T=tentativi fatti, C=coppie
formate, N=numero di carte girate nel tentativo in corso (0 oppure 1)>.
Si parte da <0,0,0,0>, si finisce in <2n,x,n,0>, dove x e' il numero di
tentativi fatti per risolvere il solitario, n e' il numero totale di coppie
(10 nell'esempio). Ora bisogna solo calcolare le probabilita' di transizione
da uno stato all'altro, e poi si puo' mettere in moto la catena di Markov
per i calcoli.
(A) <g,t,c,0> -> <g+1,t+1,c+1,0>
Se la prima carta di un tentativo e' gia' sul tavolo allora abbiamo usato
una sola carta (g+1) per un tentativo (t+1) che realizza una coppia (c+1).
Le carte ancora da girare prima del nostro tentativo erano 2n-g, quelle sul
tavolo g-2c (tutte diverse!), per cui la probabilita' di girare una delle
carte sul tavolo era (g-2c)/2n-g). Facciamo un esempio. Dopo aver girato 9
carte con una sola coppia su 10 individuata, girando la prima carta di un
tentativo avremo (9-2)/(20-9)=7/11 possibilita' che questa sia gia' presente
sul tavolo.
le altre probabilita' da calcolare sono:
(B)  <g,t,c,0> -> <g+1, t , c ,1> (la prima del tentativo e' nuova)
(B1) <g,t,c,1> -> <g+1,t+1,c+1,0> (ho girato una coppia)
(B2) <g,t,c,1> -> <g+1,t+2,c+1,0> (al prossimo tentativo ho una coppia
facile)
(B3) <g,t,c,1> -> <g+1,t+1, c ,0> (tentativo infruttuoso)
...e le lascio fare a voi, cosi' ho una conferma dei calcoli che faro'
anch'io. Poi ci sara' da fare il programma che calcola la probabilita'
maedia, ma credo sia abbastanza semplice (per chi conosce le catene di
Markov, ovviamente ;)
Ciao, Silv:o)

 Tav=15.6217
Concordo in pieno. Il programma l'ho fatto in VB, ecco i risultati.
T=10  p=1,52734965564609E-09
T=11  p=5,04025346409288E-07
T=12  p=5,94749876703782E-05
T=13  p=2,96413910522871E-03
T=14  p=5,84219033303599E-02
T=15  p=0,359613604359785
T=16  p=0,474138988741219
T=17  p=0,102363866511105
T=18  p=2,43588714818548E-03
T=19  p=1,56095124232973E-06
Tav=15,6216489570834
Ciao, Silv:o)