Solitario del carcerato ancora senza soluzione- by whiles

[robbstark]

Mi sembra che il problema è equivalente a cercare la probabilità che:
"Non esca un asso nelle prime 14 carte E non esca un due nelle successive 13 carte E non esca un tre nelle successive 13 carte"
Il primo faticoso passo è contare il numero di modi in cui si possono distribuire i 2 e i 3, dividendo il calcolo in 36 configurazioni diverse. Poi il numero di casi che realizzano ciascuna di queste 36 configurazioni, va moltiplicato per il numero di modi in cui possono essere disposti gli assi nei posti rimanenti. Infine vanno sommati i risultati e si moltiplica tutto per il numero di modi in cui possono essere disposte le rimanenti 28 carte nelle 28 posizioni, cioè 28!.
Chi ha voglia può cimentarsi...

[markowitz]

Riprendendo il mio ragionamento e procedendo nel caso con 3 carte, diventa relativamente comodo rappresentare la situazione. La
probabilità di perdere il solitario è:
$P(E_1 uu E_2 uu E_3)=P(E_1)+ P(E_2)+ P(E_3)- P(E_1 uu E_2)- P(E_1 nn E_3)- P(E_2 nn E_3)+ P(E_1 nn E_2 nn E_3)=$$= P(E_1)+ P(E_2)+ P(E_3)- P(E_1 | E_2)P(E_2)- P(E_1 | E_3)P(E_3)- P(E_2 | E_3)P(E_3)+ P(E_1 nn E_2 nn E_3)$
Faccio notare che
$P(E_1 | E_2)P(E_2)= P(E_1 | E_3)P(E_3)= P(E_2 | E_3)P(E_3)=1/2*1/3=1/6$
$P(E_1 nn E_2 nn E_3)=1/3*1/2=1/6$
Per cui
$P(E_1)+ P(E_2)+ P(E_3)- P(E_1 | E_2)P(E_2)- P(E_1 | E_3)P(E_3)- P(E_2 | E_3)P(E_3)+ P(E_1 nn E_2 nn E_3)=1/3*3-1/6*3+1/6=2/3$

In questo caso è facile verificare il risultato, i possibili casi sono:
A23 *
A32 *
3A2
32A *
2A3 *
23A
I casi asteriscati sono quelli in cui si perde.
In questo caso è chiaro che era conveniente contare tutti i casi possibili (modo sempre valido in questi esercizi) invece di sfruttare il metodo di inclusione/esclusione. Se generalizziamo conviene usare il metodo o contare i casi? Non lo so, ma credo siano follie entrambe.

Se l’obbiettivo dell’autore (che ha postato un problema per niente SEMPLICE) era di trovare uno schema teorico di riferimento, penso che questo funzioni e dia una certa generalità. Algoritmi comodi credo proprio che non esistano.

Se invece si invece vuoi un numero penso che debba armarti di computer e programmare
- O un programma che faccia i conti in automatico col principio di inclusione/esclusione, ma la vedo proprio dura
- Oppure ci si da alla simulazione, si programma un codice che “giochi” e con la definizione frequentista di probabilità se ne trova una stima.

[Rggb]

Allora dopo averci un po' rimuginato su, direi si può fare nel modo seguente (ma non ho trovato soluzione più semplice ). Considero di contare i casi favorevoli.

Nomenclatura: indico con $A$, $D$, $T$ le carte asso, due, tre e con [1], [2], [3] le posizioni che tali carte devono "evitare". Ho rispettivamente 14, 13 e 13 posizioni.

Ho contato cinque differenti modi di disporre le carte $A$, $D$ e $T$ di modo che occupino le posizioni che portano alla vittoria:
- quattro $A$ in [2], quattro $D$ in [3], quattro $T$ in [1]
- quattro $A$ in [3], quattro $D$ in [1], quattro $T$ in [2]
- tre $A$ in [2] e uno in [3], tre $D$ in [3] e uno in [1], tre $T$ in [1] e uno in [2]
- tre $A$ in [3] e uno in [2], tre $D$ in [1] e uno in [3], tre $T$ in [2] e uno in [1]
- due $A$ in [2] e due in [3], due $D$ in [1] e due in [3], due $T$ in [1] e due in [2]
sempre che non abbia fatto errori e/o mi sia sfuggito qualcosa (probabili anche refusi, sto copiando da scarabocchi carta e penna ).

Ora per ognuno di questi modi, ho sempre una disposizione di quattro carte differenti (4 A, oppure 3 A e un T, eccetera) in una combinazione di 13 "posti" (o 14 nel caso di [1]), e tutti i modi portano a disposizioni differenti: non ci sono doppioni. Per le combinazioni che usano una sola carta c'è un solo modo di scegliere le carte e $4!$ modi di disporle, per le combinazioni che usano due carte differenti sono $((4),(3))*((4),(1))$ (tre assi un due, tre due un tre...) oppure $((4),(2))*((4),(2))$ (due assi due tre...), ma comunque sempre $4!$ modi per disporle.

Quindi per ogni modo posso disporre in $4!$ modi le carte in $((14),(4))$ modi di occupare le posizioni [1], analogamente in $((13),(4))$ le rimanenti [2] e [3]. Una volta ottenuta una disposizioni di assi, due e tre, rimangono le altre carte da disporre in $28!$ modi, ottenendo il numero di disposizioni vincenti:

$v=[ 2*(4!*((13),(4))*4!*((13),(4))*4!*((14),(4))) + $
$+ 2*(((4),(3))*((4),(1))*4!*((13),(4))*((4),(3))*((4),(1))*4!*((13),(4))*((4),(3))*((4),(1))*4!*((14),(4))) +$
$+ ((4),(2))*((4),(2))*4!*((13),(4))*((4),(2))*((4),(2))*4!*((13),(4))*((4),(2))*((4),(2))*4!*((14),(4)) ] *28!$

che ho semplificato:

$v=10^2*11^3*12^3*13^3*14*(2+2*16^3+36^3)*28!$

La probabilità di vincita risulta quindi

$P=v/(40!)=~0,144994748

Chi ha voglia di controllare?

@markowitz: per questo, mi è bastata la calcolatrice. Comunque è vero, a me non è sembrato un problema banale.

[cenzo]

C'è qualcosa che non torna.

Ho contato cinque differenti modi di disporre le carte $A$, $D$ e $T$ di modo che occupino le posizioni che portano alla vittoria:
- quattro $A$ in [2], quattro $D$ in [3], quattro $T$ in [1]
- quattro $A$ in [3], quattro $D$ in [1], quattro $T$ in [2]
- tre $A$ in [2] e uno in [3], tre $D$ in [3] e uno in [1], tre $T$ in [1] e uno in [2]
- tre $A$ in [3] e uno in [2], tre $D$ in [1] e uno in [3], tre $T$ in [2] e uno in [1]
- due $A$ in [2] e due in [3], due $D$ in [1] e due in [3], due $T$ in [1] e due in [2]
sempre che non abbia fatto errori e/o mi sia sfuggito qualcosa (probabili anche refusi, sto copiando da scarabocchi carta e penna ).

Mi sembra che manchino diversi casi, ad esempio quattro $A$ in [2], quattro $T$ in [2], quattro $D$ in [1].

***
Ho provato a calcolare la probabilità di vittoria introducendo alcune approssimazioni.

Scelgo la posizione degli $A$. Posso scegliere 4 posti tra 26 possibilità (13 [2] + 13 [3]): $((26),(4))*4!$.

Devo scegliere ora la posizione dei $D$ tenendo conto della scelta fatta per gli $A$.
Introduco una approssimazione: ipotizzo che la scelta dei 4 $A$ sia fatta (in media? ) prendendo 2 $A$ dalle posizioni [2] e 2 $A$ dalle posizioni [3].
Pertanto restano disponibili ancora 14 [1], 11 [2], 11[3].
Scelgo la posizione dei $D$. Posso scegliere 4 posti tra 25 possibilità (14 [1] + 11 [3]): $((25),(4))*4!$.

Devo scegliere ora la posizione dei $T$ tenendo conto della scelta fatta per gli $A$ e i $D$.
Seconda ipotesi semplificativa: ipotizzo che la scelta dei 4 $D$ sia fatta prendendo 2 $D$ dalle posizioni [1] e 2 $D$ dalle posizioni [3].
Pertanto restano disponibili ancora 12 [1], 11 [2], 9[3].
Scelgo la posizione dei $T$. Posso scegliere 4 posti tra 23 possibilità (12 [1] + 11 [2]): $((23),(4))*4!$.

Infine devo scegliere i posti per le rimanenti 28 carte: $28!$

La probabilità di vincere il gioco è allora: $(((26),(4))*4!*((25),(4))*4!*((23),(4))*4!*28!)/(40!)\approx 0.00865$

Il mio risultato, con le approssimazioni fatte, è sensibilmente più basso del tuo.

Ho provato quindi con una simulazione in R, di cui questo è il codice.

Testo nascosto, fai click qui per vederlo

> carcerato<-function(prove) {
+ unopos<-c(1,4,7,10,13,16,19,22,25,28,31,34,37,40)
+ duepos<-unopos+1;duepos<-duepos[-14];trepos<-duepos+1
+ succ<-0
+ for (i in 1:prove) {
+ x<-sample(40)
+ if (max ((x[unopos]==1) | (x[unopos]==2) | (x[unopos]==3) | (x[unopos]==4))==0) {
+ if(max ((x[duepos]==5) | (x[duepos]==6) | (x[duepos]==7) | (x[duepos]==8))==0) {
+ if(max ((x[trepos]==9) | (x[trepos]==10) | (x[trepos]==11) | (x[trepos]==12))==0) {
+ succ<-succ+1 } } }
+ }
+ succ/prove
+ }
> carcerato(2000000)
[1] 0.0083015
> carcerato(10000000)
[1] 0.0083584

Il risultato ottenuto è un po' più basso di quello teorico con l'approssimazione.

Concordo che il problema non è per nulla banale

[Rggb]

C'è qualcosa che non torna.
...
Mi sembra che manchino diversi casi, ad esempio quattro $A$ in [2], quattro $T$ in [2], quattro $D$ in [1].
...
Il mio risultato, con le approssimazioni fatte, è sensibilmente più basso del tuo.

"Uhm uhm". C'è un evidente errore di calcolo (e di metodo: l'ho appena notato), il risultato era molto alto e lì per lì non me ne sono accorto.

Comunque non mi arrendo

[cenzo]

Uso la stessa nomenclatura di Rggb. Tento di contare i casi favorevoli.

Scegliamo prima le posizioni dei 4 assi. Abbiamo 5 differenti modi:
1) 4 $A$ in [2]
2) 3 $A$ in [2] + 1 $A$ in [3]
3) 2 $A$ in [2] + 2 $A$ in [3]
4) 1 $A$ in [2] + 3 $A$ in [3]
5) 4 $A$ in [3]

In corrispondenza di ciascuna di queste 5 scelte abbiamo 5 scelte per la posizione dei 4 $D$:
1) 4 $D$ in [1]
2) 3 $D$ in [1] + 1 $D$ in [3]
3) 2 $D$ in [1] + 2 $D$ in [3]
4) 1 $D$ in [1] + 3 $D$ in [3]
5) 4 $D$ in [3]

In corrispondenza di ciascuna delle precedenti $5*5=25$ scelte abbiamo 5 scelte per la posizione dei 4 $T$:
1) 4 $T$ in [1]
2) 3 $T$ in [1] + 1 $T$ in [2]
3) 2 $T$ in [1] + 2 $T$ in [2]
4) 1 $T$ in [1] + 3 $T$ in [2]
5) 4 $T$ in [2]

In totale abbiamo quindi "solamente" $5*5*5=125$ possibilità.

Si tratta allora di calcolare i casi favorevoli per ognuna di queste 125 possibilità, e sommare.
Allo scopo ho utilizzato un foglio di calcolo.

Faccio un esempio.
Supponiamo la scelta degli $A$ sia: 1 $A$ in [2] + 3 $A$ in [3]
Supponiamo la scelta dei $D$ sia: 3 $D$ in [1] + 1 $D$ in [3]
Supponiamo la scelta dei $T$ sia: 2 $T$ in [1] + 2 $T$ in [2]
Casi favorevoli: $[((13),(1))((13),(3))]*[((14),(3))((10),(1))]*[((11),(2))((12),(2))]*(4!)^3$

Per avere il numero totale dei casi favorevoli occorre poi tenere conto delle permutazioni delle rimanenti 28 carte.

In definitiva mi risulta $P("vittoria")=(1608107296510*(4!)^3*28!)/(40!)\approx0.008307$

La probabilità di vincere al solitario del carcerato risulta quindi di circa 1 su 120.
Non è poi così bassa... il carcerato in questione ha una condanna abbastanza leggera..

[Rggb]

125, bravo mi hai anticipato, il risultato è corretto (a meno che entrambi non abbiamo fatto svarioni); hai fatto pure il calcolo, mi ripromettevo di farlo lunedì ma a 'sto punto... se vuoi posso farlo per verifica, ma è in linea con la tua simulazione, che è corretta.

L'idea era quella, solo che quando ho calcolato la prima volta ho sbagliato a contare i gruppi; ora se ci si volesse prendere qualche sfizio si potrebbe cercare di generalizzare a formula, ma anche questa non mi sembra banale (sopratutto a causa della non-simmetria del numero delle posizioni, 14/13/13)... boh, ci penserò su.

[cenzo]

@ Rggb
Scusami se ti ho anticipato... non ho resistito
In fin dei conti ho fatto solo i calcoli (spero senza errori), ma l'idea era tua

La generalizzazione la intendi riferita ai dati del problema, quindi qualcosa tipo una tripla sommatoria (di prodotti di combinazioni) con indici opportuni ?
O pensi di estenderla anche al caso di un mazzo di $n$ carte ? (magari con gruppi di assi, due tre e quattro, etc..)

[Rggb]

Esattamente, partendo dal cercare una formula per generalizzare il problema mazzo 40 (o 52) a 3 carte, poi a $k$ carte e poi a mazzo $n$ carte.

Ho poco tempo fra lavoro, studio e famiglia, ma la combinatoria m'intruppa e la risoluzione di problemi mi appassiona (è evidente, sennò non sarei su un forum di matematica a quest'ora )

[Umby]

La probabilità di vincere al solitario del carcerato risulta quindi di circa 1 su 120.

Gran bel lavoro...
Difficilmente ci sarà qualcuno che ti smentirà i tuoi calcoli.
Valutavo l'idea di raggiungere il risultato percorrendo una strada diversa, ma la vedo difficile.