Enigma a catena

[sssebi]

Ma no, la probabilità resta sempre la stessa a prescindere dalla posizione di partenza. In qualunque posizione si trovi la carta, mescolando in maniera casuale ho sempre 50/52 di probabilità che la carta non finisca agli estremi.

Poi non ho capito che c'entra il modo di mescolare, io intendo una qualsiasi combinazione casuale di carte. Una carta qualsiasi del mazzo, dopo una mescolata casuale, ha 1/52 di probabilità di finire prima, 1/52 di finire seconda, 1/52 di finire terza, ..., 1/52 di finire ultima. Poi se aggiungi la variante di una "mescolata specifica" devi essere più chiara circa la combinazione di questa mescolata. Cioè io ovviamente penso ad una mescolata generale, senza metodi tradizionali o altri metodi, che poi non so nemmeno qual è il metodo tradizionale, io mescolo come mi viene prima. Ognuno mescola le carte a suo modo, io parlo di una mescolata generale, ovvero una qualsiasi permutazione di carte a partire da una disposizione di partenza.

[Ajeje.]

Per quanto riguarda il meteo è un esempio che non sta né in cielo né in terra. È certo che conta la probabilità, ma in questo caso entrano in gioco altre decine di fattori che non hanno nulla a che fare con la matematica pura (venti, inquinamento, persino eclissi, tutte cose al di fuori che la matematica pura ti può dire). Un solitario è una cosa completamente diversa, non ci sono fattori estranei alla matematica.

E anche l'esempio dell'asso in ultima posizione è un esempio sbagliato. Certo è che se mescoli 2-3 volte la probabilità che ritorni nella stessa posizione è minore (e anche incalcolabile visto che è una persona che mescola), ma se ad esempio mescolasse un macchina mescolatrice per 5 minuti la probabilità rimarrebbe 1/52. Comunque sono tutte cose che non c'entrano nulla con la soluzione del solitario, che è l'unica cosa che mi interessa, alla fine della fiera.

Tornando a parlare con sssebi, sono d'accordo su quello che hai detto. Io infatti alla seconda carta avevo già considerato 36/39 possibilità meno la percentuale che sia uscita al primo colpo. Continuando su questa strada però credo anch'io sia un conto lunghissimo. Proverò a vedere se così ne esce qualcosa, oppure prima o poi chiederò a qualche amico professore universitario che conosco perché veramente è un dubbio che ormai è diventato una croce.
Edit: Lasciamo stare l'esempio sviante, non sono assolutamente d'accordo ma al limite ci penseremo risolto questo.

[sssebi]

Io stavo provando a fare un bottom-up, nel senso che semplifico il problema considerando solo 10 carte (che vanno dall'1 al 10) e poi se mi riesce ci provo con 40. Per adesso quindi consiglio di concentrarci su questo.

A questo punto la cosa sembrerebbe semplice dato che bisogna contare solo fino a 10 senza ripetizioni e cose varie, ma incredibilmente anche qui la strada non sembra scontata!

Ho considerato che la probabilità che l'1 non si trovi nella prima carta è di 9/10, dato che l'1 si può trovare in 9 posizioni su 10. Per quanto riguarda il 2 pensavo che si potesse trovare in 8 posizioni su 9, perchè devo togliere la posizione dell'1 sia nei casi favorevoli (9) sia nei casi possibili (10), così via con gli altri numeri fino al 10.
Mi viene:
9/10*(9-1)/(10-1)*(9-2)/(10-2)*...*(9-8)/(10-8) =
= 9/10*8/9*7/8*...*1/2 = 1/10 (tutto si semplifica e si può notare anche l'equivalente scrittura di 9!/10!)

Sul fatto che l'1 può stare in 9 posizioni su 10 non ci piove ma sulla posizione del 2 ritornano i soliti dubbi: è vero che il 2 può andare in 8 posizioni ma solo se l'1 non si trovava alla seconda posizione, cioè 1, 3, 4, ..., 10 meno la posizione dell'1; ma se l'1 si trovava alla seconda posizione allora il 2 può andare in 9 posizioni, cioè 1, 3, 4, ..., 10.

Al momento non so come uscirne fuori, intanto spero di essere stato chiaro su quello che ho appena scritto.

[Ajeje.]

Ok, ho capito circa. Il ragionamento iniziale è indubbiamente sbagliato (come confermato dal risultato che viene 1/10).

Per uscirne fuori so come fare, ma non purtroppo con una formula. Ho provato anche a considerare semplicemente 3 carte, ma tutt'ora una formula corretta non mi viene. Il risultato è 1/3 con 3 carte (basta calcolare il numero di casi favorevoli diviso il numero di casi possibili), però via formula non so come ci si arrivi.

Per intenderci:
Numero di casi favorevoli: 2 -> 312, 231.
Numero di casi possibili: 6 -> oltre a 312 e 231: 123, 213, 132, 321, i quali sono appunto perdenti.

Analogamente si può fare con n carte, ma già con 4 i casi favorevoli sono 9 e i casi possibili 24: si vede facilmente che il numero aumenta in una maniera esponenzialmente proibitiva da calcolare così.

@Shira, ah, con questo ragionamento è evidente che una soluzione per il solitario c'è: basta considerare il numero di casi favorevoli, ossia il numero di casi in cui non venga mai il numero della carta che dici, diviso il numero di casi possibili totali. È un conto che non ti basterebbe un quaderno intero se lo fai a mano, ma comunque una soluzione c'è.

[sssebi]

Benissimo, hai fatto un buon passo in avanti, non ci avevo pensato di ridurmi a 3 carte. Ma il fatto che a 3 carte abbiamo una soluzione certa ci permette di andare avanti con sicurezza perchè abbiamo una base certa. Vediamo se riesco a concludere tutto, ti rendo partecipe di tutti i miei ragionamenti...
Non so se ti va di leggere tutto questo poema, però se proprio vogliamo arrivare alla soluzione ti conviene capire tutti i passaggi

Come detto, se troviamo tutti i casi possibili e tutti i casi favorevoli abbiamo finito perchè basta fare il rapporto e abbiamo la soluzione.

Per i casi possibili la soluzione è semplice, perchè essi sono tutte le permutazioni che si possono ottenere con n carte, questi si calcolano con il fattoriale. Infatti:
per 3 carte i casi possibili sono 3!=3*2=6;
per 4 carte i casi possibili sono 4!=4*3*2=24;
per 5 carte i casi possibili sono 5!=5*4*3*2=120;
...
per n carte i casi possibili sono n!=n*(n-1)*(n-2)*...*3*2

Il problema resta solo quello di trovare i casi favorevoli. Ovviamente sono in quantità minore perchè ai casi possibili dobbiamo sottrarre tutti i casi in cui perdiamo, cioè quando in tutte le permutazioni si verifica che l'1 sta nella prima carta, il 2 nella seconda, ..., la n nella n-esima.

Come primo passo, quindi, bisogna capire quali sono le permutazioni dove come prima carta c'è l'1. Il valore sarebbe (n-1)!. (Infatti se le moltiplichiamo per n carte riotteniamo n!).
A questo punto facendo n!-(n-1)! togliamo ai casi possibili tutti i casi in cui l'1 è presente come prima carta, quindi un passo in avanti verso i casi favorevoli.

Ora però, a questi, bisogna anche togliere tutte le permutazioni dove il 2 sta nella seconda carta meno in quelle dove ci sta anche l'1 nella prima perchè quest'ultimi sono stati già tolti nel passaggio precedente. Anche questo valore ho trovato, sarebbe (n-1)!-(n-2)!. (Cioè tutti i casi in cui il 2 è presente come seconda carta sono tanti quanti lo sono quelli dell'1 a prima carta solo che ho sottratto quelli in cui come prima carta c'è l'1 e contemporaneamente il 2 come seconda, il cui valore sarebbe (n-2)!).
Quindi facendo n!-(n-1)!-((n-1)!-(n-2)!) togliamo ai casi possibili non solo tutti i casi in cui l'1 è presente come prima carta ma anche quelli dove il 2 è presente come seconda carta, un ulteriore passo in avanti verso i casi favorevoli.

Il difficile arriva adesso perchè dobbiamo togliere tutte le permutazioni dove il 3 è presente come terza carta meno quelle dove l'1 è presente come prima carta e il due come seconda carta, a questa sottrazione dobbiamo poi aggiungere tutte le permutazioni in cui l'1 sta nella prima e contemporaneamente il 2 nella seconda perchè le abbiamo sottratte 2 volte, prima con l'1 e poi con il 2, quindi per regolare i conti dobbiamo riaggiungerle una volta sola dopo la sottrazione. Il valore sarebbe (n-1)!-2(n-2)!+(n-3)!. (Nel primo addendo ho considerato tutti i casi in cui il 3 è presente nella terza carta, poi ho fatto la doppia sottrazione dell'1 e del 2 e infine ho riaggiunto le permutazioni sottratte 2 volte dove figurava sia l'1 che il 2).
Quindi facendo n!-(n-1)!-((n-1)!-(n-2)!)-((n-1)!-2(n-2)!+(n-3)!) togliamo ai casi possibili tutti i casi in cui l'1 figura alla prima carta, il 2 alla seconda e il 3 alla terza.

Continuando ora dobbiamo togliere anche le permutazioni dove il 4 è presente alla quarta carta meno tutte le permutazioni dove l'1 è presente alla prima, il 2 alla seconda e il 3 alla terza, poi a questa quantità dobbiamo aggiungere quelle dove l'1 e il 2 sono contemporaneamente presenti alla prima e alla seconda, quelli dove l'1 e il 3 sono contemporaneamente presenti alla prima e alla terza e quelli dove il 2 e il 3 sono contemporaneamente presenti alla seconda e alla terza, infine sottraiamo a questa quantità quelle dove l'1, il 2 e il 3 sono contemporaneamente presenti alla prima, alla seconda e alla terza ...il valore sarebbe (n-1)!-3(n-2)!+3(n-3)-(n-4)!.
Quindi facendo n!-(n-1)!-((n-1)!-(n-2)!)-((n-1)!-2(n-2)!+(n-3)!)-((n-1)!-3(n-2)!+3(n-3)-(n-4)!) togliamo tutte le permutazioni in cui l'1 figura alla prima carta, il 2 alla seconda, il 3 alla terza e il 4 alla quarta.

Ancora non è chiaro il meccanismo, infatti a questo punto ero quasi tentato di abbandonare però alcuni fatti mi hanno spinto a continuare anche con la quinta carta, ad esempio il fatto della sequenza ordinata di (n-1), (n-2), (n-3),...

Quindi provando un ultimo tentativo con le permutazioni dove il 5 è presente alla quinta carta, con le relative somme e sottrazioni che abbiamo applicato nei passaggi precedenti, risulta (n-1)!-4(n-2)!+6(n-3)!-4(n-4)!+(n-5)!.
Quindi la formula che ci permette di trovare tutti i casi possibili meno i casi in cui l'1 figura come prima carta, il 2 come seconda, il 3 come terza, il 4 come quarta e il 5 come quinta è la seguente: n!-(n-1)!-((n-1)!-(n-2)!)-((n-1)!-2(n-2)!+(n-3)!)-((n-1)!-3(n-2)!+3(n-3)-(n-4)!)-((n-1)!-4(n-2)!+6(n-3)!-4(n-4)!+(n-5)!).

Ora, la cosa positiva è che resta confermato l'ordine della decrescenza fattoriale di n, ma la cosa negativa è che ogni volta compaiono quei numeri che moltiplicano i fattoriali apparentemente senza ordine quindi impossibili da prevedere al crescere delle carte. Poi però arriva l'illuminazione e mi accorgo che in realtà un senso quei numeri ce l'hanno! Non so per quale arcano motivo ma quei numeri non sono nient'altro che i numeri che figurano nel Triangolo di Tartaglia! Infatti 1 4 6 4 1 sono proprio quelli che figurano al quinto gradino del Triangolo di Tartaglia e 1 3 3 1 sono quelli del quarto gradino. A questo punto possiamo sapere quali saranno i successivi, cioè per trovare tutte le permutazioni con il 6 come sesta carta, con le relative somme e sottrazioni che abbiamo applicato nei passaggi precedenti, dobbiamo svolgere la seguente formula: (n-1)!-5(n-2)!+10(n-3)!-10(n-4)!+5(n-5)!-(n-6)!.

Per verifica, ho fatto la prova con 5 carte e ho visto che risulta. Viene n!-(n-1)!-((n-1)!-(n-2)!)-((n-1)!-2(n-2)!+(n-3)!)-((n-1)!-3(n-2)!+3(n-3)-(n-4)!)-((n-1)!-4(n-2)!+6(n-3)!-4(n-4)!+(n-5)!), sostituendo la n con il 5 risulta 120-24-18-14-11-9=44. Infatti i casi favorevoli sono proprio 44 che fratto i casi possibili (120) risulta 11/30. Quindi la probabilità che il solitario mi risulti con 5 carte è di 11/30, cioè una volta ogni 2,72 volte circa.

La strada effettivamente è un po' lunga, ho cercato comunque di essere il più chiaro possibile. Nonostante abbiamo trovato questa formula restano comunque dei passaggi un po' lunghi da fare, ma il problema principale è che sono certo che queste formule risultino fino a 10 carte però non so se dall'undicesima in poi, con le ripetizioni, tutte queste formule continuino ad avere senso. Ci penserò dopo però

[Ajeje.]

Ok tutto abbastanza chiaro, però non era la via che avrei voluto usare (casi favorevoli/casi possibili). Ottimo che hai trovato anche il fatto che i coefficienti sono quelli del triangolo di tartaglia, fino a 10 carte siamo riusciti a trovare il risultato finalmente.

Sono abbastanza convinto che con 40 carte il caso sia diverso e si complichi parecchio, però almeno un risultato lo abbiamo trovato. Secondo me dovremmo iniziare a ragionare con 12 carte, tre 1, tre 2 e tre 3. Il processo sarà analogo poi con 40 (come hai trovato tu ora).

Esattamente con 10 carte quanto ti viene? Io ho provato a fare il conto, e devo dire che è facilissimo sbagliare, mi viene 1334961 su 3628800 casi possibili. E quindi 1 volta ogni 2.718 volte (che è quasi uguale al valore con 5 -.-), il 36.78%. Risulta anche a te?

Rimango comunque sconsolato per non aver trovato una soluzione (nemmeno con 3 carte) con il tipo di formule con cui avevo iniziato (ossia quelle del tipo 2/3*(1/2-1/3) (?) * ???)

[sssebi]

Va be' ci consoliamo con la scoperta della soluzione, è questo l'obiettivo.
Io rimango già abbastanza soddisfatto dato che avendo proposto il quesito a tutti i miei colleghi di matematica nel nostro gruppo facebook nessuno sapeva dove metterci mano nemmeno con 10 carte, cioè neppure il secchione del 30 e lode ad ogni esame

Non era nemmeno la via che avrei voluto usare io, ma a quanto pare non abbiamo tante altre scelte...

Comunque poi svolgendo i calcoli si possono notare delle semplificazioni. La formula che avevo dato al post precedente era comunque lunghissima, soprattutto col crescere delle carte, invece svolgendo i calcoli mi sono reso conto che possiamo semplificare tutto ad una formula molto più breve. Praticamente basta svolgere la sommatoria a segni alterni di (n-i)!, con i che va da 0 a n, moltiplicando però ad ogni addendo i numeri del triangolo di Tartaglia che figurano al (n+1)esimo gradino. Infatti per 10 carte non c'è bisogno di fare tutto quel mare di sottrazioni e addizioni, basta andare all'undicesimo gradino e vediamo che i numeri sono 1 10 45 120 210 252 210 120 45 10 1, quindi facendo 10!-10*9!+45*8!-120*7!+...+45*2!-10+1 si trovano già i casi favorevoli. Poi si vede anche che strada facendo si possono fare molte altre semplificazioni, ho usato pochissimo la calcolatrice per trovare il risultato.
In ogni caso i conti mi risultano esattamente uguali ai tuoi, quindi direi che non ci sono dubbi riguardo questo risultato.

Al resto ancora ci devo pensare, non ho avuto tanto tempo, credo comunque che di questo passo la soluzione non è tanto lontana, spero solo che con le ripetizioni non bisogna cambiare metodo e che i calcoli siano simili a questi...

[sssebi]

Ovviamente non si può lasciare il quesito irrisolto

Allora, eravamo arrivati alla soluzione del solitario senza ripetizioni con 10 carte (più in generale l'abbiamo trovata per n carte), al crescere di n la soluzione si avvicina ad 1/e (numero di Nepero), infatti con 5 carte ci veniva circa 1/2,72 e poi con 10 carte ci veniva circa 1/2,718. Non so come sia uscito fuori il numero di Nepero (stesso dicasi per il triangolo di Tartaglia) ma è questo il bello della Matematica
Poi avevamo pensato di iniziare ad occuparci delle ripetizioni, ma per semplificare la cosa avevamo pensato di fare solo quello con tre carte, cioè il solitario 1,2,3 proposto in partenza (con 40 carte). In questo caso (stavolta servendomi anche di un aiuto) credo di esserci arrivato.

La strada purtroppo è sempre quella dei casi favorevoli diviso i casi possibili che sono sempre 40!, infatti il problema resta sempre quello di trovare i casi favorevoli.

Le posizioni che consideriamo sono:
La posizione [1] che sarebbe una tra queste 14 posizioni: 1,4,7,10,13,16,19,22,25,28,31,34,37,40;
La posizione [2] che sarebbe una tra queste 13 posizioni: 2,5,8,11,14,17,20,23,26,29,32,35,38;
La posizione [3] che sarebbe una tra queste 13 posizioni: 3,6,9,12,15,18,21,24,27,30,33,36,39.
Ognuna delle 40 posizioni rientra in una delle 3 classi.

Scegliamo ora tutte le posizioni favorevoli che possono occupare i 4 ASSI:
1) 4 in [2]
2) 3 in [2] e 1 in [3]
3) 2 in [2] e 2 in [3]
4) 1 in [2] e 3 in [3]
5) 4 in [3]

Sono 5 modi differenti, ovviamente stesso discorso per quanto riguarda i DUE e i TRE (facendo i dovuti cambiamenti di posizione). In totale abbiamo 125 (5x5x5) possibilità.

Il problema ora è che per trovare tutti i casi favorevoli bisogna trovare i casi favorevoli di ognuna di questa 125 possibilità e fare la somma. Purtroppo in informatica devo ancora migliorare, infatti ho lasciato i conti ad un mio amico che ha usato un foglio di calcolo.

Trovare i casi favorevoli di ogni possibilità non è un problema.

Primo caso:
4 ASSI in [2]
4 DUE in [3]
4 TRE in [1]
Devo scegliere 4 posti (4 assi) per 13 possibilità (le 13 posizioni del [2]) con 4! modi di disporle. Cioè il calcolo combinatorio per n=13 e k=4, moltiplicato per 4!;
Allo stesso modo poi devo scegliere 4 posti (4 due) per 13 possibilità (le 13 posizioni del [3]) con 4! modi di disporle. Cioè il calcolo combinatorio per n=13 e k=4, moltiplicato per 4!;
Infine devo scegliere 4 posti (4 tre) per 14 possibilità (le 14 posizioni del [1]) con 4! modi di disporle. Cioè il calcolo combinatorio per n=14 e k=4, moltiplicato per 4!.
In definitiva devo fare la moltiplicazione dei tre calcoli combinatori per (4!)^3 e trovo i casi favorevoli del primo caso.

Secondo caso:
4 ASSI in [2]
4 DUE in [3]
3 TRE in [1] e 1 TRE in [2]
Procedimento analogo al primo caso.

...

125esimo caso:
4 ASSI in [3]
4 DUE in [3]
4 TRE in [2]
Sempre con analogo procedimento.

Infine bisogna anche tenere conto delle permutazioni delle restanti 28 carte (le 40 carte meno i 4 assi, due e tre), cioè 28!.

Il risultato finale dei casi favorevoli viene 1608107296510 x (4!)^3 x 28! che diviso per i casi possibili (40!) risulta circa 0.008307.

La probabilità risulta circa di 1 su 120.

Il bello è che possiamo essere sicuri di questo risultato dato che il nostro utente Davyl mi ha riferito che ha scritto un programma per simulare questo gioco e, dal punto di vista statistico, ha notato che le probabilità di vincita si stabilizzano proprio intorno a 1/120.

[Davyl]

Complimenti Seby, confesso di non aver letto prestando grandissima attenzione al ragionamento (causa giornata stancante), però mi è sembrato sensato e il risultato coincide con quello atteso, quindi nice job

[sssebi]

Grazie Dave, c'è voluto un po' di tempo (un mese esatto) ma almeno alla fine ci siamo arrivati. E Ajeje mi è stato d'aiuto.

Comunque il quesito non era per nulla semplice, forse il più difficile che abbia mai svolto. E, anche scoprendo come trovare la soluzione, ci vuole parecchio tempo per farla uscire.

[Davyl]

Seby, quando hai tempo trovami la probabilità che su N dadi ALMENO UNO faccia un risultato >= K, con K € {1,2,3,4,5,6} :P

[Ajeje.]

Per N o per K dadi? Perché per N dadi non riesco a capire il senso del quesito (mi sembra assurdo), mentre per K è abbastanza semplice.

[Davyl]

Sicuro non sia per K dadi? Perché per N dadi il quesito mi sembra senza significato (o meglio, direi 100%, ma sarebbe comunque formulato male). Se è per K dadi:

Per K=1: 100%;
Per K=2: 97%;
Per K=3: 89%;
Per K=4: 75%;
Per K=5: 55%;
Per K=6; 31%.

Scusa, ma queste che probabilità sarebbero? Io chiedevo questo: ho N dadi, li lancio uno alla volta, e chiedevo quale fosse la probabilità che negli N lanci eseguiti almeno un dado abbia dato un risultato >= K.

[Ajeje.]

Sì ma N dadi con N che va da 1 a infinito?

Esempio: ho N (ad es. con N=5) dadi. Qual è la probabilità che almeno un dado abbia come risultato un numero maggiore o uguale di K (quindi maggiore uguale di un numero da 1 a 6)?

Da quello che hai scritto io capisco così, ma non credo sia quello che intendi, perché non avrebbe senso (sarebbe banalmente 100%).

[Davyl]

Sì ma N dadi con N che va da 1 a infinito?

Esempio: ho N (ad es. con N=5) dadi. Qual è la probabilità che almeno un dado abbia come risultato un numero maggiore o uguale di K (quindi maggiore uguale di un numero da 1 a 6)?

Da quello che hai scritto io capisco così, ma non credo sia quello che intendi, perché non avrebbe senso (sarebbe banalmente 100%).

Sì, è quello che intendo, perché non avrebbe senso? E perché sarebbe 100%?
Mettiamo caso di avere 2 dadi (N=2) e di lanciarli, voglio sapere la probabilità che nei 2 lanci almeno uno abbia fatto un risultato >=3 (K=3).
Ovviamente non è 100%, un semplice controesempio è considerare che al primo dado esca 1 e che al secondo esca 2, ad esempio.