Solitario e probabilita' di riuscita

293 visualizzazioni
Passa al primo messaggio da leggere

El Filibustero

da leggere,
30 ago 2004, 06:28:2330/08/04
a
On Mon, 31 Dec 2001 09:58:07 GMT, Emanuele wrote:

>un classico mazzo di carte da 40 (quelle da scopa per intenderci), si
>mescola, e poi si inizia a scoprire le carte una ad una. Contemporaneamente
>si conta da uno a dieci dicendo un numero per ogni carta uscita, quindi in
>totale di dovrebbe contare 4 volte fino a 10. Il solitario termina (e non
>riesce) se nello scoprire le carte, il valore della carta uscita
>corrisponde a quello pronunciato (fante=8 cavallo=9 re=10).
>...
>qual è la probabilità di riuscita del gioco? Dopo un po'
>di prove si vede che il solitario riesce MOLTO MOLTO raramente, ma, volendo
>calcolare precisamente la probabilità in questione, nonostante ripetuti
>tentativi, non ci sono riuscito.

la probabilita' e' di circa 0.01562 =

12745876601159747423747978302388220527929982976 casi favorevoli sui
40! possibili

i casi favorevoli sono stati calcolati esaustivamente da un processo
iniziato il 1 Gen 2002 e terminato oggi. Scherzi a parte, salvo
errori, i casi favorevoli sono dati da s(10,40) dove s e' la funzione
ricorsiva s(N=numero di valori per seme, k=Numero di carte con valore
diverso da quello pronunciato) per mazzi a 4 semi:

s(1,0) = 4!; s(N,k)=0 per ogni k<0 e ogni k>4N;

s(N,k) = s(N-1,k) * 4! +
s(N-1,k-1) * 4!4(k-1) +
s(N-1,k-2) * [4!4(4N-k-2) + 72(k-2)(k-3)] +
s(N-1,k-3) * [144(4N-k-1)(k-3) + 16(k-3)(k-4)(k-5)] +
s(N-1,k-4) * [72(4N-k)(4N-k-1) + 48(4N-k)(k-4)(k-5) +
(k-4)(k-5)(k-6)(k-7)] +
s(N-1,k-5) * [48(4N-k+1)(4N-k)(k-5) +
4(4N-k+1)(k-5)(k-6)(k-7)] +
s(N-1,k-6) * [16(4N-k+2)(4N-k+1)(4N-k) +
6(4N-k+2)(4N-k+1)(k-6)(k-7)] +
s(N-1,k-7) * 4(4N-k+3)(4N-k+2)(4N-k+1)(k-7) +
s(N-1,k-8) * (4N-k+4)(4N-k+3)(4N-k+2)(4N-k+1)

Questa formula e' stata testata per N=2 e N=3 mediante ricerca
esaustiva dei casi favorevoli nelle rispettive 8! e 12! permutazioni.
Penso che la verifica esaustiva per N=4 sia gia' proibitiva. Ciao

ticonzero

da leggere,
30 ago 2004, 18:12:4130/08/04
a
El Filibustero ha scritto:

> On Mon, 31 Dec 2001 09:58:07 GMT, Emanuele wrote:
>
>> un classico mazzo di carte da 40 (quelle da scopa per intenderci), si
>> mescola, e poi si inizia a scoprire le carte una ad una.
>> Contemporaneamente si conta da uno a dieci dicendo un numero per
>> ogni carta uscita, quindi in totale di dovrebbe contare 4 volte fino
>> a 10. Il solitario termina (e non riesce) se nello scoprire le
>> carte, il valore della carta uscita corrisponde a quello pronunciato
>> (fante=8 cavallo=9 re=10). ...
>> qual è la probabilità di riuscita del gioco?...

> la probabilita' e' di circa 0.01562 =
>
> 12745876601159747423747978302388220527929982976 casi favorevoli sui
> 40! possibili
>

Ciao. Complimenti!!! Mi sembra un problema decisamente molto difficile.
Casualmente, un annetto fa, mi sono imbattuto in un sito dove c'era un
articolo che riportava una formula chiusa per calcolare la probabilità di
questo tipo di solitari.

Innanzitutto la formula:
casi possibili: 40!/(4!)^10
casi favorevoli:
somme (-1)^(i1+...+i10)*(4 su i1)* ...*(4 su i10)*
*(40-i1....-i10)!/((4-i1)!*...*(4-i10)!)

dove con (a su b) e' il coefficiente binomiale e
le somme vanno fatte sui dieci indici i1, i2, ..., i10 che vanno da 1 a 4.

Con questa formula si trova
P=201028342764877992289387752167601/12868639981414579848070084500000000
che è identico al tuo
12745876601159747423747978302388220527929982976/40!

Purtroppo non sono riuscito a ritrovare il sito in questione,
provo quindi, dagli appunti che avevo preso, a ricostruirne la spiegazione
o quello che ne avevo capito... in effetti alcuni passaggi non mi sono del
tutto chiari.

Per ragioni affettive do la versione con un mazzo di carte napoletane e con
la conta fatta fino a tre (io lo facevo cosi'!).

P = 1 - P(errore)
= 1 - P(1 err. U 2 err. U ...U 12 err.)
(al massimo sono possibili 4*3=12 errori)
= 1- [P(1 err.) - P(2 err.) + P(3 err.)- ... - P(12 err.)]

questo per il "principio di inclusione-esclusione"
(http://mathworld.wolfram.com/Inclusion-ExclusionPrinciple.html)

= 1-[A(1) - A(2) + A(3)- ...+(-1)^(n-1)A(n) + ... - A(12)]/A
= [A - A(1) + A(2) - A(3)- ...+(-1)^(n)A(n) + ... + A(12)]/A

dove A è il numero di casi possibili e A(n) e' il numero di casi in cui si
possono verificare n errori.

Siccome nel girare le carte contando fino a tre si arriva a chiamare 13
volte l'asso, 12 il due e 12 il tre il numero di casi possibili e'
A=40!/(13!*12!*12!) (si puo' pensare, in modo equivalente, di avere un mazzo
in un dato ordine e di chiamare una qualunque permutazione di 13 assi, 12
due e 12 tre).

Indichiamo con A(i,j,k) il numero di modi in cui i assi, j due e k tre
sono in posizioni specifiche (quelle di errore):
A(i,j,k)=(4 su i)*(4 su j)*(4 su k)*(40-i-j-k)!/((13-i)!*(12-j)!*(12-j)!)

Allora A(0,0,0)=40!/(13!*12!*12!)=A i casi possibili,
e per ottenere A(n) (con n>1):
A(n)=Sum_{i+j+k=n} A(i,j,k)
(la somma e' su tutti gli i,j,k tali che i+j+k=n)

mettendo tutto insieme nella formula per P, ci si rende conto che si puo'
riscrivere la sommatoria come:

P = Sum_i Sum_j Sum_k (4 su i)*(4 su j)*(4 su k)*(-1)^(i+j+k)*
*(40-i-j-k)!/((13-i)!*(12-j)!*(12-j)!)/(40!/(13!*12!*12!))
dove le tre somme sono libere e i rispettivi indici vanno da 0 a 4.

Valutando questa espressione per il solitario dell'uno-due-tre si trova
2005028661108720/241365994493904000 circa 0.0083
che è ancora minore della probabilita' per il solitario con la conta fino a
dieci.

ciao ciao

orso del kispios

da leggere,
31 ago 2004, 16:48:3531/08/04
a
El Filibustero ha scritto:

> la probabilita' e' di circa 0.01562 =
>
> 12745876601159747423747978302388220527929982976 casi favorevoli sui
> 40! possibili
>
> i casi favorevoli sono stati calcolati esaustivamente da un processo
> iniziato il 1 Gen 2002 e terminato oggi. Scherzi a parte, salvo
> errori, i casi favorevoli sono dati da s(10,40) dove s e' la funzione
> ricorsiva s(N=numero di valori per seme, k=Numero di carte con valore
> diverso da quello pronunciato) per mazzi a 4 semi:
>
> s(1,0) = 4!; s(N,k)=0 per ogni k<0 e ogni k>4N;
>
> s(N,k) = s(N-1,k) * 4! +
> s(N-1,k-1) * 4!4(k-1) +
> s(N-1,k-2) * [4!4(4N-k-2) + 72(k-2)(k-3)] +
> s(N-1,k-3) * [144(4N-k-1)(k-3) + 16(k-3)(k-4)(k-5)] +
> s(N-1,k-4) * [72(4N-k)(4N-k-1) + 48(4N-k)(k-4)(k-5) +
> (k-4)(k-5)(k-6)(k-7)] +
> s(N-1,k-5) * [48(4N-k+1)(4N-k)(k-5) +
> 4(4N-k+1)(k-5)(k-6)(k-7)] +
> s(N-1,k-6) * [16(4N-k+2)(4N-k+1)(4N-k) +
> 6(4N-k+2)(4N-k+1)(k-6)(k-7)] +
> s(N-1,k-7) * 4(4N-k+3)(4N-k+2)(4N-k+1)(k-7) +
> s(N-1,k-8) * (4N-k+4)(4N-k+3)(4N-k+2)(4N-k+1)
>
> Questa formula e' stata testata per N=2 e N=3 mediante ricerca
> esaustiva dei casi favorevoli nelle rispettive 8! e 12! permutazioni.
> Penso che la verifica esaustiva per N=4 sia gia' proibitiva. Ciao
>


Beh, premetto che non sarei stato in grado di calcolare quel valore di
probabilità (1.56% circa), però mi sembra che con poco ragionamento si
possano calcolare prob. min. e max. Gradirei il vostro parere.
L'illuminazione è venuta quando, a proposito di questo solitario, mi stavo
ponendo le domande:
1) quale disposizione di carte dà al giocatore la max. probabilità di
vittoria?
2) quale, invece, la min.?


1)
Per spiegarmi meglio fingiamo di prendere un mazzo nuovo (appena comprato)
con le 40 carte ben ordinate dall'Asso di Cuori al Re di Picche. Ora
prendiamo la prima carta (l'Asso di Cuori, appunto) e poniamola in fondo al
mazzo (cioè dopo il Re di Picche). E cominciamo il solitario (quello
pronunciando in sequenza i dieci numeri da 1 a 10).
Con tale disposizione di carte le probabilità favorevoli ad ogni giro di
carta sono:
-------
36/40 per l'Asso alla prima carta (ma esce il Due)
36/39 per il Due alla seconda carta (ma esce il Tre)
35/38 per il Tre alla terza carta (ma esce il Quattro)
34/37 etc.
...
29/30 etc.
28/31 per il Re alla decima carta (ma esce l'Asso)
-------
27/30 per l'Asso all'11ma carta (ma esce il Due)
27/29 per il Due alla 12ma carta (ma esce il Tre)
26/28 per il Tre alla 13ma carta (ma esce il Quattro)
25/27 etc.
...
20/22 etc.
19/21 per il Re alla 20ma carta (ma esce l'Asso)
-------
18/20 per l'Asso alla 21ma carta (ma esce il Due)
18/19 per il Due alla 22ma carta (ma esce il Tre)
17/18 per il Tre alla 23ma carta (ma esce il Quattro)
16/17 etc.
...
11/12 etc.
10/11 per il Re alla 30ma carta (ma esce l'Asso)
-------
9/10 per l'Asso alla 31ma carta (ma esce il Due)
9/9 per il Due alla 32ma carta (ma esce il Tre)
8/8 per il Tre alla 33ma carta (ma esce il Quattro)
7/7 etc.
...
2/2 etc.
1/1 per il Re alla 40ma carta (ma esce l'Asso)
-------

Quindi la probabilità di vittoria si riduce a (9*18*27*36)*36!/40!, cioè
(9^4)*4!*36!/40! ovvero, semplificando: 6561/91390, pari al 7,18% circa.

2)
La probabilità min. è (ovviamente?): (1*10*19*28)*36!/40!, pari a 7/2886,
ovvero lo 0.24% circa, e corrisponde alla seguente disposizione iniziale di
carte:
Re, Asso, Due, Tre, ..., Otto, Nove, Re, Asso, etc., che si ottiene, come la
precedente, da un mazzo nuovo, semplicemente ponendo l'ultima carta (il Re
di Picche) sopra alla prima (l'Asso di Cuori).


Curioso, non trovate?
C'è un legame tra la prob. max, la min. e quella da voi calcolata (1.56%)?
Quale?
E soprattutto, perché tanto divario tra la prob. max. e quella calcolata)?


* * *


Ora propongo una variante al solitario.
Quando il giocatore, girando le carte sul tavolo, incontra la carta che fa
perdere, invece di rimescolare il mazzo, deve ricomporlo disponendo le carte
già girate sotto al mazzo di carte coperte che gli rimane ancora in mano
(senza mescolarle!). Quindi il solitario ricomincia (contando da 1,
ovviamente).

Sotto tali condizioni (non ancora stanco...) mi sono posto due domande:
A) Quale disposizione iniziale di carte fa sì che il giocatore perda ogni
volta?
B) Quale lo fa vincere sempre?

Propongo due soluzioni (ma a parte le ovvie simmetrie o traslazioni
operabili sul mazzo, non so se ve ne siano altre). Per comodità Asso=1,
Due=2, ..., Re=10.

A) Se il mazzo è 1,1,1,1,2,2,2,2,3,3,3,3,...,10,10,10,10 si perde sempre.

B) Se il mazzo 2,3,...,10,1,2,3,...,10,...,1,2,3,...,10,1 si vince sempre.

Vi sembrano esserci altre soluzioni?

Saluti,
l'orso.

--------------------------------
Inviato via http://arianna.libero.it/usenet/

El Filibustero

da leggere,
1 set 2004, 06:49:3301/09/04
a
On Tue, 31 Aug 2004 00:12:41 +0200, ticonzero wrote:

>Innanzitutto la formula:
>casi possibili: 40!/(4!)^10
>casi favorevoli:
>somme (-1)^(i1+...+i10)*(4 su i1)* ...*(4 su i10)*
> *(40-i1....-i10)!/((4-i1)!*...*(4-i10)!)

>...


>questo per il "principio di inclusione-esclusione"
>(http://mathworld.wolfram.com/Inclusion-ExclusionPrinciple.html)

la formula generale ricorsiva s(N,k) che ho trovato e' molto piu'
complicata, non impiegando il principio di inclusione-esclusione:

c: numero di semi nel mazzo
N: numero di valori per seme
k: numero di errori (carte con valore diverso dal pronunciato)

s(1,0) = c!

s(N,k) = sum{h=0..2c} s(N-1,k-h)*
sum{i0,i1,i2|i0+i1+i2=c; i1+2*i2=h}
[(c su i0)(c-i0 su i1)*prod{j0=1..i0}(c-j0+1)*
*prod{j1=1..i1}(k-h-j1+1)*
*prod{j2=1..i2}(c(N-1)-(k-h)-j2+1)
]

ma forse la logica sottostante e' piu' semplice. Supponiamo di avere
un mazzo con N-1 valori per ognuno dei c semi disposto in uno dei
possibili s(N-1,k-h) modi con k-h errori e di voler ottenere un mazzo
con N valori e k errori, introducendo nuovi h errori. Aggiungiamo le c
carte con valore N nelle loro posizioni corrette (ad esempio, partendo
da un mazzo a 4 semi e 9 valori, aggiungere i quattro Re in posizioni
10,20,30 e 40) e vediamo in che modi possono essere permutate con
altre carte. Ci sono 3 possibili insiemi di posizioni dove ciascuna di
queste c carte puo' finire:

I0: Rimanere nelle loro c posizioni corrette. Ad esempio, un Re rimane
nella sua posizione o viene scambiato con un altro Re. Questo scambio
non fa aumentare il numero di errori

I1: errori nel mazzo a N-1 valori. Le nuove carte vengono scambiate
con vecchie carte in posizione errata (che sono k-h) nel mazzo a N-1
valori. Ogni carta scambiata in questo modo aumenta di 1 il numero di
errori: infatti la vecchia carta minore di N in posizione errata
rimane fuori posto andando in N-esima posizione, e la nuova carta di
valore N va fuori posto andando in una posizione minore di N.

I2: carte corrette nel mazzo a N-1 valori. Ogni carta nuova scambiata
con una carta a posto nel vecchio mazzo (che sono c(N-1)-(k-h) )
aumenta di 2 il numero di errori, poiche' entrambe le carte scambiate
vanno fuori posto.

i0,i1 e i2 rappresentano rispettivamente il numero di carte nei tre
insiemi I0, I1, I2. Cosi' aggiungendo le c carte di valore N si devono
avere h=i1+2*i2 nuovi errori rispetto ai precedenti: h puo' andare da
0 (tutte le nuove carte in I0) ad un eventuale massimo di 2c (tutte le
nuove in I2). Ecco perche'

- la somma su h va da 0 a 2c
- nella somma su i0, i1, i2 ci sono i vincoli:
i0+i1+i2=c (ci sono c nuove carte di valore N)
i1+2*i2=h

l'espressione in [] da' il numero di disposizioni corrispondenti a una
ripartizione con i0, i1, e i2 assegnati. (c su i0)(c-i0 su i1) da' il
numero di possibili scelte di quali delle c nuove carte mettere in I0
e I1 (e di conseguenza in I2); ognuno dei prodotti seguenti calcola il
numero di disposizioni possibili di una carta all'interno di ciascun
insieme. Ciao

ticonzero

da leggere,
1 set 2004, 18:27:5601/09/04
a
El Filibustero ha scritto:

> la formula generale ricorsiva s(N,k) che ho trovato e' molto piu'
> complicata, non impiegando il principio di inclusione-esclusione:
[...]
> ma forse la logica sottostante e' piu' semplice..

Quello che non e' semplice e' passare dalla logica sottostante alle formule!
:-)
Bella idea quella di aumentare via via il mazzo. Complimenti di nuovo.
ciao


Rispondi a tutti
Rispondi all'autore
Inoltra
0 nuovi messaggi