Solitario del carcerato ancora senza soluzione- by whiles
Sposto qui un problema proposto da whiles nella zezione statistica, che, a dispetto della sua apparente semplicità, ad oggi non ha ottenuto alcuna risposta.
Confido possiate fornirne una plausibile e magari solo dopo spostarlo in una sezione diversa
. Grazie
--------------------------------------------
Ciao ragazzi,
ho un piccolo problema di statistica che probabilmente per voi è banale ma a me tormenta da un sacco di tempo
Praticamente c'è un gioco di carte, basato completamente sulla casualità, chiamato il solitario del carcerato. Praticamente si prende il mazzo di carte napoletane, si mischia ed ad una ad una si girano le carte dicendo il numero uno per la prima carta, due per la seconda, tre per la terza, e poi ricominciando: uno per la quarta, due per la quinta.. insomma.. uno due tre, uno due tre, uno due tre.. e così via (spero di essere stato chiaro!).
Se la carta che si sta girando ha il valore del numero che si sta pronunciando, il solitario viene perso, insomma, insomma, non bisogna azzeccare nessun numero.
Ho provato a calcolare con metodi ripetitivi e semplici per ogni operazione ma farlo per 40 carte è veramente un'impresa.
Avete idea di come fare per calcolare la probabilità di vincita di questo strano solitario?
Grazie mille, vi seguo da tempo senza scrivere niente e devo dire che da questo forum c'è un sacco da imparare
Confido possiate fornirne una plausibile e magari solo dopo spostarlo in una sezione diversa
. Grazie--------------------------------------------
Ciao ragazzi,
ho un piccolo problema di statistica che probabilmente per voi è banale ma a me tormenta da un sacco di tempo
Praticamente c'è un gioco di carte, basato completamente sulla casualità, chiamato il solitario del carcerato. Praticamente si prende il mazzo di carte napoletane, si mischia ed ad una ad una si girano le carte dicendo il numero uno per la prima carta, due per la seconda, tre per la terza, e poi ricominciando: uno per la quarta, due per la quinta.. insomma.. uno due tre, uno due tre, uno due tre.. e così via (spero di essere stato chiaro!).
Se la carta che si sta girando ha il valore del numero che si sta pronunciando, il solitario viene perso, insomma, insomma, non bisogna azzeccare nessun numero.
Ho provato a calcolare con metodi ripetitivi e semplici per ogni operazione ma farlo per 40 carte è veramente un'impresa.
Avete idea di come fare per calcolare la probabilità di vincita di questo strano solitario?
Grazie mille, vi seguo da tempo senza scrivere niente e devo dire che da questo forum c'è un sacco da imparare
Risposte
Una formula per esprimere la somma dei binomiali relativi ai precedenti 125 casi potrebbe essere questa:
$\sum_{i=0}^{4}\sum_{j=0}^{4}\sum_{k=0}^{4}((14),(0))((13),(i))((13),(4-i))*((14-0),(j))((13-i),(0))((13-4+i),(4-j))*((14-0-j),(k))((13-i-0),(4-k))((13-4+i-4+j),(0))$
che ovviamente poi semplificherei così:
$\sum_{i=0}^{4}\sum_{j=0}^{4}\sum_{k=0}^{4}((13),(i))((13),(4-i))*((14),(j))((9+i),(4-j))*((14-j),(k))((13-i),(4-k))$
Ho provato ad implementarla in R per verificare se esce lo stesso coefficiente ottenuto "a mano" col foglio di calcolo:
Il conto torna.
In definitiva la probabilità di vincere il solitario è esprimibile in questo modo:
$([\sum_{i=0}^{4}\sum_{j=0}^{4}\sum_{k=0}^{4}((13),(i))((13),(4-i))*((14),(j))((9+i),(4-j))*((14-j),(k))((13-i),(4-k))]*(4!)^3*28!)/(40!)$
L'estensione al caso di un mazzo di $n$ carte (a parità di altre condizioni) mi sembra abbastanza agevole.
$\sum_{i=0}^{4}\sum_{j=0}^{4}\sum_{k=0}^{4}((14),(0))((13),(i))((13),(4-i))*((14-0),(j))((13-i),(0))((13-4+i),(4-j))*((14-0-j),(k))((13-i-0),(4-k))((13-4+i-4+j),(0))$
che ovviamente poi semplificherei così:
$\sum_{i=0}^{4}\sum_{j=0}^{4}\sum_{k=0}^{4}((13),(i))((13),(4-i))*((14),(j))((9+i),(4-j))*((14-j),(k))((13-i),(4-k))$
Ho provato ad implementarla in R per verificare se esce lo stesso coefficiente ottenuto "a mano" col foglio di calcolo:
> coeff_carcerato<-function() {
+ sum<-0
+ for (i in 0:4) {
+ for (j in 0:4) {
+ for (k in 0:4) {
+ sum<-sum+choose(13,i)*choose(13,4-i)*choose(14,j)*choose(9+i,4-j)*choose(14-j,k)*choose(13-i,4-k)
+ }
+ }
+ }
+ sum
+ }
> coeff_carcerato()
[1] 1.608107e+12
> format(coeff_carcerato(),,12)
[1] "1608107296510"Il conto torna.
In definitiva la probabilità di vincere il solitario è esprimibile in questo modo:
$([\sum_{i=0}^{4}\sum_{j=0}^{4}\sum_{k=0}^{4}((13),(i))((13),(4-i))*((14),(j))((9+i),(4-j))*((14-j),(k))((13-i),(4-k))]*(4!)^3*28!)/(40!)$
L'estensione al caso di un mazzo di $n$ carte (a parità di altre condizioni) mi sembra abbastanza agevole.
"cenzo":
Sarebbe interessante vedere una strada alternativa
Dopo aver letto l'ultimo tuo intervento mi sembra inutile illustrarti la mia "strada", anche perchè piu' che strada mi sembra un vicoletto (sperando che non sia cieco
).Diciamo che mi chiedevo:
quale è la probabilità che si verifica l'evento alla prima carta ? $(n-1) !$ ma visto che ci sono $4$ assi:
$p(1)$ = $(n-1) ! * 4$
la seconda ?
Sempre (n-1) ma dobbiamo eliminare (n-2) del primo turno, quindi
$p(2)$ = $[(n-1) ! * 4] - [(n-2) ! * 16]$
e cosi via....
$p(3)$ = $[(n-1) ! * 4] -2 [(n-2) ! * 4^2] + [(n-3) ! * 4^3]$
Un vicoletto un po tortuoso, che temo che non mi porti molto lontano !|!!
"cenzo":
Una formula per esprimere la somma dei binomiali relativi ai precedenti 125 casi potrebbe essere questa:
$\sum_{i=0}^{4}\sum_{j=0}^{4}\sum_{k=0}^{4}((14),(0))((13),(i))((13),(4-i))*((14-0),(j))((13-i),(0))((13-4+i),(4-j))*((14-0-j),(k))((13-i-0),(4-k))((13-4+i-4+j),(0))$
Molto bella. E prima di semplificarla si può generalizzare.
"cenzo":
L'estensione al caso di un mazzo di $n$ carte (a parità di altre condizioni) mi sembra abbastanza agevole.
L'unica condizione imposta dalla tua formula è che le carte interessate siano fra tre differenti; posso poi avere un mazzo $n$ e ogni carta occorrere $m$ volte (o anche $m_1$, $m_2$ e $m_3$ volte). Avremo tre sommatorie in $m$ (o $m_1$ ecc.) e i coefficienti aggiustati sul numero $n$ e le differenze (con $m+m$ o $m_1+m_2$ ecc.).
Generalizzare a $k!=3$ carte si può fare, ma ci vuole un po' di tempo...
Bel lavoro.
PS. Il titolo del thread andrebbe modificato: "con soluzione".
"Rggb":
Generalizzare a $k!=3$ carte si può fare, ma ci vuole un po' di tempo...
Si, questa generalizzazione la vedo alquanto problematica.
Già per $k=4$, avremmo quattro gruppi di 10 carte (10/10/10/10 invece di 14/13/13).
Non è possibile ad esempio scegliere 4 "Due", 4 "Tre" e 4 "Quattro" dal primo gruppo in quanto non avremmo carte a sufficienza (10<12).
Diversi casi non sarebbero più ammissibili (a parte che il loro conteggio diventa ben più difficile...)
Al limite, per $k=n=40$ (ammesso di distinguere anche ciascun asso dagli altri, etc...) la probabilità di vincere il solitario sarebbe la probabilità che nessuna carta occupi la posizione corrispondente al proprio numero progressivo (una volta fissata una certa numerazione).
Di questo problema ho letto qualcosa di Umby qui (cicli e punti fissi..
):https://www.matematicamente.it/forum/dis ... tml#358863
In tal caso la probabilità di vincere dovrebbe essere circa $1/e$.
[OT]E' quasi ora del cenone: mi aspetta un delizioso piatto di vermicelli alle vongole..
Buon appetito e buona conversazione a tutti
[/OT]
"cenzo":
Una formula per esprimere la somma dei binomiali relativi ai precedenti 125 casi potrebbe essere questa:
$\sum_{i=0}^{4}\sum_{j=0}^{4}\sum_{k=0}^{4}((14),(0))((13),(i))((13),(4-i))*((14-0),(j))((13-i),(0))((13-4+i),(4-j))*((14-0-j),(k))((13-i-0),(4-k))((13-4+i-4+j),(0))$
che ovviamente poi semplificherei così:
$\sum_{i=0}^{4}\sum_{j=0}^{4}\sum_{k=0}^{4}((13),(i))((13),(4-i))*((14),(j))((9+i),(4-j))*((14-j),(k))((13-i),(4-k))$
Ho provato ad implementarla in R per verificare se esce lo stesso coefficiente ottenuto "a mano" col foglio di calcolo:
> coeff_carcerato<-function() { + sum<-0 + for (i in 0:4) { + for (j in 0:4) { + for (k in 0:4) { + sum<-sum+choose(13,i)*choose(13,4-i)*choose(14,j)*choose(9+i,4-j)*choose(14-j,k)*choose(13-i,4-k) + } + } + } + sum + } > coeff_carcerato() [1] 1.608107e+12 > format(coeff_carcerato(),,12) [1] "1608107296510"
Il conto torna.
In definitiva la probabilità di vincere il solitario è esprimibile in questo modo:
$([\sum_{i=0}^{4}\sum_{j=0}^{4}\sum_{k=0}^{4}((13),(i))((13),(4-i))*((14),(j))((9+i),(4-j))*((14-j),(k))((13-i),(4-k))]*(4!)^3*28!)/(40!)$
L'estensione al caso di un mazzo di $n$ carte (a parità di altre condizioni) mi sembra abbastanza agevole.
ciao cenzo, volevo chiedere una cosa,
ho provato ad usare la formula (non semplificata) per il mazzo da 52 carte è mi risulta
$p("vittoria")=0.008165023553234$
quindi un po inferiore a caso delle 40 carte (napoletane)
però mi sembra controintuitivo perché a parità del numero di carte "pericolose" 12 nel mazzo da 52 ci sono più posti a
disposizione.
Nei conti ho sostanzialmente sostituito il 14 col 18 ed il 13 col 17.
Ho usato male la formula o faccio un errore interpretativo sul confronto 40 Vs 52?
"markowitz":
Nei conti ho sostanzialmente sostituito il 14 col 18 ed il 13 col 17.
Hai ricordato il termine fattoriale, che cambia in $40!$ al numeratore e $52!$ al denominatore?
Però comunque, direi che può essere di poco (sic) inferiore.
"markowitz":
ho provato ad usare la formula (non semplificata) per il mazzo da 52 carte è mi risulta
$p("vittoria")=0.008165023553234$
quindi un po inferiore a caso delle 40 carte (napoletane)
Ciao, mi trovo col tuo conto.
Ho fatto un grafico della probabilità di vincere il solitario (in base alla formula): risulta che essa diminuisce all'aumentare delle carte del mazzo.
"markowitz":
però mi sembra controintuitivo perché a parità del numero di carte "pericolose" 12 nel mazzo da 52 ci sono più posti a
disposizione.
Secondo me è controintuitivo solo all'apparenza. All'aumentare delle carte aumentano pure le posizioni pericolose.
Se nel mazzo di 40 erano pericolose 14 posizioni per l'asso, con 52 carte sono pericolose 18 posizioni.
Non di rado nel calcolo delle probabilità accade di imbattersi in situazioni apparentemente controintuitive (mi viene da pensare ai numeri ritardatari del lotto o al problema di Monty Hall).
"cenzo":
Non di rado nel calcolo delle probabilità accade di imbattersi in situazioni apparentemente controintuitive (mi viene da pensare ai numeri ritardatari del lotto o al problema di Monty Hall).
Ed è proprio per questo che il calcolo delle probabilità, secondo me, è il campo più intrigante della matematica
Penso che con il numero di carte che aumenta sempre più, e lasciando invariati i 4 pali ( e quindi i 4 Assi, 2, 3) la probabilità tende a:
0,00770734
0,00770734
"Umby":
Penso che con il numero di carte che aumenta sempre più, e lasciando invariati i 4 pali ( e quindi i 4 Assi, 2, 3) la probabilità tende a: 0,00770734
Una curiosità.. il tuo è un conto solo numerico oppure hai fatto il limite ?
Allora adesso si passa al caso $k=4$ ??
"cenzo":
Allora adesso si passa al caso $k=4$ ??
Comunque, considerando un mazzo 52 e le carte fino al quattro si può impostare una formula sulla base della tua... ma dove vuoi arrivare, a calcolare al limite per studiarne le proprietà?
"cenzo":
Una curiosità.. il tuo è un conto solo numerico oppure hai fatto il limite ?
Numerico (vedi tuo spoiler)
Si trattava di una idea già presente fin dal primo momento, ed ovviamente piu il numero di carte aumentano, minore è il "peso" della presenza o meno di carte uguali nelle posizioni diverse. (...mi son spiegato malissimo...)
Rimane tuttavia che ognuna delle $12$ carte interessate ( A, 2, 3) ha la probabilità di essere al posto giusto nei $2/3$ dei casi.
[size=75]Corretto orrore grammaticale[/size]
"cenzo":
Allora adesso si passa al caso $k=4$ ??
Potresti fare un secondo grafico.
Fissare ad esempio le 52 carte a 4 pali. Verificare il K (il numero massimo che si chiama girando la carta [k=3 1-2-3-1-2-3.....]), partendo da 2 fino ad arrivare a 52.
Ho fatto un po di conti e mi sono accorto di una cosa che forse tu (osservando il grafico) avevi già notato
Per ottenere la massima generalità (limitatamente al caso delle 3 carte e dei 4 semi s'intende)
non dovremmo poter iniziare i conti usando 12 carte? Cioè solo quelle "pericolose" appunto?
E da li aumentare le componenti dei vari semi da 5 ad N con N-4 carte neutre?
ma la formula funziona solo se in ogni seme ci sono almeno 6 carte quindi come dal tuo grafico il mazzo minimo
è da 24 carte. Altrimenti ci troviamo in qualche punto con $C(N,K)$ dove $K>N$
E' un problema serio della formula o c'è solo da mettere qualche min/max da qualche parte?
"cenzo":
Ho fatto un grafico della probabilità di vincere il solitario (in base alla formula): risulta che essa diminuisce all'aumentare delle carte del mazzo.
Per ottenere la massima generalità (limitatamente al caso delle 3 carte e dei 4 semi s'intende)
non dovremmo poter iniziare i conti usando 12 carte? Cioè solo quelle "pericolose" appunto?
E da li aumentare le componenti dei vari semi da 5 ad N con N-4 carte neutre?
ma la formula funziona solo se in ogni seme ci sono almeno 6 carte quindi come dal tuo grafico il mazzo minimo
è da 24 carte. Altrimenti ci troviamo in qualche punto con $C(N,K)$ dove $K>N$
E' un problema serio della formula o c'è solo da mettere qualche min/max da qualche parte?
Forse ho individuato un po il senso del problema
se si hanno almeno 6 carte per ogni seme allora ne abbiamo in totale 24
il fatto è che ci sono 8 prime posizioni 8 seconde posizioni ed 8 terze posizioni
per esempio nel caso dell'ASSO ci sono 16 posizioni ammesse per vincere (8 seconde ed 8 terze)
ma anche per il DUE sono sedici (otto prime ed 8 terze)
quindi 8 (le terze) sono comuni.
Il punto è che esiste la possibilità che i 4 assi siano tutti nelle terze posizioni
e lo stesso per i due e la cosa non crea "conflitti" perché copriamo tutti gli 8 posti disponibili.
I tre in terza posizione non ci possono andare.
Ma se abbiamo meno di 8 carte per ogni seme il fatto che (seguendo l'esempio di prima)
i 4 assi sono nelle terze posizioni implica che MENO di 4 due vi si possano congiuntamente trovare.
Da qui la limitazione della formula.
Non so se quanto detto infici l'esattezza della formula in senso generale
ma sicuramente ne impedisce l'utilizzo nei casi come quello sopra.
Come avevamo detto sto solitario non è banale, è un bel casino
La ricerca di una soluzione esatta e generale continua...
se si hanno almeno 6 carte per ogni seme allora ne abbiamo in totale 24
il fatto è che ci sono 8 prime posizioni 8 seconde posizioni ed 8 terze posizioni
per esempio nel caso dell'ASSO ci sono 16 posizioni ammesse per vincere (8 seconde ed 8 terze)
ma anche per il DUE sono sedici (otto prime ed 8 terze)
quindi 8 (le terze) sono comuni.
Il punto è che esiste la possibilità che i 4 assi siano tutti nelle terze posizioni
e lo stesso per i due e la cosa non crea "conflitti" perché copriamo tutti gli 8 posti disponibili.
I tre in terza posizione non ci possono andare.
Ma se abbiamo meno di 8 carte per ogni seme il fatto che (seguendo l'esempio di prima)
i 4 assi sono nelle terze posizioni implica che MENO di 4 due vi si possano congiuntamente trovare.
Da qui la limitazione della formula.
Non so se quanto detto infici l'esattezza della formula in senso generale
ma sicuramente ne impedisce l'utilizzo nei casi come quello sopra.
Come avevamo detto sto solitario non è banale, è un bel casino
La ricerca di una soluzione esatta e generale continua...
@ Umby
confesso che -ingenuamente- sono arrivato a $(2/3)^12$ facendo il limite della formula approssimata proposta diversi post fa..
Il tuo ragionamento (as usual) è più immediato, semplice e comprensibile
@ markowitz
Hai compreso perfettamente il problema.
Tuttavia, riflettendoci meglio, mi sembra che la formula possa andare bene anche per mazzo 12..23 (sempre nel caso $k=3$).
Mi spiego. Come hai detto te, alcuni casi non sono ammissibili e per tali casi si presenta un binomiale $C(N,K)$ con $K>N$. In tali casi possiamo (per convenzione) porre il binomiale uguale a zero (pensa che R lo fa di default! ). In tal modo i casi non ammissibili sono praticamente esclusi dalla sommatoria..
Ad esempio per $n=12$ (sempre $k=3$) verrebbe $p=(346*(4!)^3)/(12!)$
Questo è allora il grafico aggiornato per $k=3$ e $n>=12$ (ho aggiunto anche il limite suggerito da Umby)
@ Rggb
intendevo di esaminare il caso $k=4$ con mazzo 40
per capire se la formula può essere adattata (anche per k ancora maggiori) oppure diviene necessario (o conveniente?) cambiare radicalmente approccio..
confesso che -ingenuamente- sono arrivato a $(2/3)^12$ facendo il limite della formula approssimata proposta diversi post fa..
Il tuo ragionamento (as usual) è più immediato, semplice e comprensibile
@ markowitz
Hai compreso perfettamente il problema.
Tuttavia, riflettendoci meglio, mi sembra che la formula possa andare bene anche per mazzo 12..23 (sempre nel caso $k=3$).
Mi spiego. Come hai detto te, alcuni casi non sono ammissibili e per tali casi si presenta un binomiale $C(N,K)$ con $K>N$. In tali casi possiamo (per convenzione) porre il binomiale uguale a zero (pensa che R lo fa di default!
). In tal modo i casi non ammissibili sono praticamente esclusi dalla sommatoria..Ad esempio per $n=12$ (sempre $k=3$) verrebbe $p=(346*(4!)^3)/(12!)$
Questo è allora il grafico aggiornato per $k=3$ e $n>=12$ (ho aggiunto anche il limite suggerito da Umby)
@ Rggb
intendevo di esaminare il caso $k=4$ con mazzo 40
per capire se la formula può essere adattata (anche per k ancora maggiori) oppure diviene necessario (o conveniente?) cambiare radicalmente approccio..
Perfetto il problema è risolto è
solo una curiosità
io facevo i conti con Matlab e nei casi in cui, con la notazione precedente, $K>N$
restituiva errore. Anche Excel fa lo stesso.
Allora ciò pensato un po...
il segnale di errore deriva dal fatto che esplicitando la nota formula delle combinazioni
salterebbero fuori dei fattoriali negativi (quelli si indefiniti) da cui l'errore
però, un po come per le divisioni, se cerchiamo quanti sottoinsiemi di 10 elementi ci sono
un un insieme di 8 elementi la risposta è ZERO!!! Non indefinito!!! Ovvero la domanda ha senso
come ha senso fare 12/15 fra naturali e vedersi restituire 0+resto
Il problema del fattoriale impica solo una gestione più attenta delle istruzioni if all'interno delle
funzioni di combinazione
A scanso di equivoci ho controllato sul Ross, che mi sembra un riferimento abbastanza autorevole,
e dice chiaramente che se $K>N$ o $K<0$ si ha $C(N,K)=0$
Quindi Excel e Matlab sbagliano !!!
Mentre R ha ragione!!!
Non vi sembra una mancanza abbastanza grave per applicativi molto diffusi [size=150]ed a pagamento[/size]
come Excel e Matlab
rispetto ad R che è [size=150]open source[/size]???
solo una curiosità
io facevo i conti con Matlab e nei casi in cui, con la notazione precedente, $K>N$
restituiva errore. Anche Excel fa lo stesso.
Allora ciò pensato un po...
il segnale di errore deriva dal fatto che esplicitando la nota formula delle combinazioni
salterebbero fuori dei fattoriali negativi (quelli si indefiniti) da cui l'errore
però, un po come per le divisioni, se cerchiamo quanti sottoinsiemi di 10 elementi ci sono
un un insieme di 8 elementi la risposta è ZERO!!! Non indefinito!!! Ovvero la domanda ha senso
come ha senso fare 12/15 fra naturali e vedersi restituire 0+resto
Il problema del fattoriale impica solo una gestione più attenta delle istruzioni if all'interno delle
funzioni di combinazione
A scanso di equivoci ho controllato sul Ross, che mi sembra un riferimento abbastanza autorevole,
e dice chiaramente che se $K>N$ o $K<0$ si ha $C(N,K)=0$
Quindi Excel e Matlab sbagliano !!!
Mentre R ha ragione!!!
Non vi sembra una mancanza abbastanza grave per applicativi molto diffusi [size=150]ed a pagamento[/size]
come Excel e Matlab
rispetto ad R che è [size=150]open source[/size]???
Questo thread m'è garbato una cifra. markowitz, concludiamo in bellezza: OpenSource is often (read "always") better.
@Cenzo
Inoltro a te i complimenti, considerato che hai svolto il 99% del lavoro, arricchendolo di grafici e codice che spesso rendono molto di più di semplici numeri o formule.
Concordo con Rggb, un gran bel thread, ed anche sull'utilizzo di software OpenSource.
Inoltro a te i complimenti, considerato che hai svolto il 99% del lavoro, arricchendolo di grafici e codice che spesso rendono molto di più di semplici numeri o formule.
Concordo con Rggb, un gran bel thread, ed anche sull'utilizzo di software OpenSource.
Grazie Umby, grazie a tutti: un bel thread, istruttivo e divertente!
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo