Problema "problematico"
Un problema che inizialmente avevo catalogato come un semplice esercizio di combinatoria, ma che si è rivelato più interessante del previsto. Tuttora la soluzione che ho trovato non è del tutto soddisfacente. Mi serve il vostro aiuto.
Ho un mazzo di 40 carte (quattro assi, quattro due, ..., quattro dieci), giro una carta per volta e contemporaneamente conto le carte girate. Se l' n-esima carta è un n, allora ho perso. Dopo aver contato dieci carte, ricomincio da uno. La partita è vinta se giro tutte le carte del mazzo.
Ad esempio:
Giro un 7 (1)
Giro un 4 (2)
...
Giro un 6 (10)
Giro un asso (1) - partita persa
Qual'è la probabilità di vincere?
È possibile trovare una formula che generalizzi il problema ad un qualsiasi mazzo di carte, non necessariamente regolare?
p.s; Elencare tutte le possibili permutazioni del mazzo è inutile. Tanto per scoraggiare eventuali tentativi, dico subito che sono $ 1.29*10^34 $ , anche se riusciste a scrivere 1 permutazione al secondo impieghereste circa 400 miliardi di triliardi di anni.
Ringrazio anticipatamente chiunque voglia dare il suo contributo.
Ho un mazzo di 40 carte (quattro assi, quattro due, ..., quattro dieci), giro una carta per volta e contemporaneamente conto le carte girate. Se l' n-esima carta è un n, allora ho perso. Dopo aver contato dieci carte, ricomincio da uno. La partita è vinta se giro tutte le carte del mazzo.
Ad esempio:
Giro un 7 (1)
Giro un 4 (2)
...
Giro un 6 (10)
Giro un asso (1) - partita persa
Qual'è la probabilità di vincere?
È possibile trovare una formula che generalizzi il problema ad un qualsiasi mazzo di carte, non necessariamente regolare?
p.s; Elencare tutte le possibili permutazioni del mazzo è inutile. Tanto per scoraggiare eventuali tentativi, dico subito che sono $ 1.29*10^34 $ , anche se riusciste a scrivere 1 permutazione al secondo impieghereste circa 400 miliardi di triliardi di anni.
Ringrazio anticipatamente chiunque voglia dare il suo contributo.
Risposte
Per ora scrivo la formula compatta che credo sia la soluzione del problema.
Con più calma scriverò il ragionamento che l'ha generata.
Con più calma scriverò il ragionamento che l'ha generata.
Non ho la minima idea di quello a cui tu stia pensando, ma sicuramente non va bene. Per j=1; i=9 abbiamo (9-9)=0 al numeratore! 
"attwo":
Non ho la minima idea di quello a cui tu stia pensando, ma sicuramente non va bene. Per j=1; i=9 abbiamo (9-9)=0 al numeratore!
Hai proprio ragione!
il ragionamento era in effetti sbagliato.
A breve una nuova proposta
Grazie comunque!
[Avevo mandato un msg ma mi ero scollegato !]
Elencare tutte le permutazioni può anche essere inutile, contarle invece utile. Qual è il tuo ragionamento?
Io proverei anzitutto a semplificare, e contare le sequenze di numeri 1..10 che sono nella "giusta" sequenza (metto 0 al posto di 10)
1234567890
1234567809
1234567980
...
fin qui mi sembra facile. Ora vediamo se mi viene un'idea per estendere a 40 numeri (carte), che ripetendosi complicano il calcolo.
Elencare tutte le permutazioni può anche essere inutile, contarle invece utile. Qual è il tuo ragionamento?
Io proverei anzitutto a semplificare, e contare le sequenze di numeri 1..10 che sono nella "giusta" sequenza (metto 0 al posto di 10)
1234567890
1234567809
1234567980
...
fin qui mi sembra facile. Ora vediamo se mi viene un'idea per estendere a 40 numeri (carte), che ripetendosi complicano il calcolo.
Tanti auguri, Rggb, [tex]10! = 3,628,800[/tex] 
Io avevo ragionato così (nel caso semplificato di [tex]n[/tex] carte tutte distinte l'una dall'altra, ma il ragionamento si estende anche al caso generale):
Sia [tex]P_n[/tex] l'insieme delle soluzioni valide, [tex]Q_n[/tex] l'insieme delle permutazioni che hanno almeno un elemento in una posizione che "non mi va bene", [tex](Q_n)_k[/tex] l'insieme delle permutazioni che hanno esattamente [tex]k[/tex] elementi in una posizione non valida, [tex]T_n[/tex] l'insieme di tutte le permutazioni, che possiamo considerare come insieme universo.
Ovviamente:
[tex]P_n = \overline{(Q_n)}[/tex]
[tex]Q_n = (Q_n)_1 \cup (Q_n)_2 \cup(Q_n)_3 ... \cup (Q_n)_n[/tex]
Vista la seconda uguaglianza, mi è sembrato molto più semplice cercare le permutazioni NON valide piuttosto che quelle valide. Isolati [tex]k[/tex] elementi dal nostro insieme originario, le permutazioni "valide" di tale insieme saranno, per definizione [tex]P(n-k)[/tex].
Tale ragionamento, anche se può sembrare piuttosto banale, è un passo fondamentale verso la (mia) soluzione. Mi consente infatti di scomporre il problema in una serie di problemi più semplici, che posso supporre di aver già risolto!
.
A questo punto è fatta! Ricordando che ci sono [tex]\begin{pmatrix} n \\ k \end{pmatrix}[/tex] modi di scegliere [tex]k[/tex] elementi da un insieme di [tex]n[/tex]:
[tex]P_n = n! - \displaystyle\sum_{k = 0}^{n} \begin{pmatrix} n \\ k \end{pmatrix} P(n-k)[/tex]
Dividendo il tutto per [tex]n![/tex] in maniera da ottenere la probabilità relativa.
Problemi:
1) È ricorsiva.
2) Se estesa al caso generale, richiede di considerare un insieme [tex]n_1, n_2, n_3, ..., n_k[/tex] che contiene [tex]n_1[/tex] elementi di tipo 1, ..., [tex]n_k[/tex] elementi di tipo [tex]n[/tex], e da una semplice sommatoria diventa la somma di un numero indeterminato di sommatorie!?!
Forza gente, brainstorming!
Io avevo ragionato così (nel caso semplificato di [tex]n[/tex] carte tutte distinte l'una dall'altra, ma il ragionamento si estende anche al caso generale):
Sia [tex]P_n[/tex] l'insieme delle soluzioni valide, [tex]Q_n[/tex] l'insieme delle permutazioni che hanno almeno un elemento in una posizione che "non mi va bene", [tex](Q_n)_k[/tex] l'insieme delle permutazioni che hanno esattamente [tex]k[/tex] elementi in una posizione non valida, [tex]T_n[/tex] l'insieme di tutte le permutazioni, che possiamo considerare come insieme universo.
Ovviamente:
[tex]P_n = \overline{(Q_n)}[/tex]
[tex]Q_n = (Q_n)_1 \cup (Q_n)_2 \cup(Q_n)_3 ... \cup (Q_n)_n[/tex]
Vista la seconda uguaglianza, mi è sembrato molto più semplice cercare le permutazioni NON valide piuttosto che quelle valide. Isolati [tex]k[/tex] elementi dal nostro insieme originario, le permutazioni "valide" di tale insieme saranno, per definizione [tex]P(n-k)[/tex].
Tale ragionamento, anche se può sembrare piuttosto banale, è un passo fondamentale verso la (mia) soluzione. Mi consente infatti di scomporre il problema in una serie di problemi più semplici, che posso supporre di aver già risolto!
.A questo punto è fatta! Ricordando che ci sono [tex]\begin{pmatrix} n \\ k \end{pmatrix}[/tex] modi di scegliere [tex]k[/tex] elementi da un insieme di [tex]n[/tex]:
[tex]P_n = n! - \displaystyle\sum_{k = 0}^{n} \begin{pmatrix} n \\ k \end{pmatrix} P(n-k)[/tex]
Dividendo il tutto per [tex]n![/tex] in maniera da ottenere la probabilità relativa.
Problemi:
1) È ricorsiva.
2) Se estesa al caso generale, richiede di considerare un insieme [tex]n_1, n_2, n_3, ..., n_k[/tex] che contiene [tex]n_1[/tex] elementi di tipo 1, ..., [tex]n_k[/tex] elementi di tipo [tex]n[/tex], e da una semplice sommatoria diventa la somma di un numero indeterminato di sommatorie!?!
Forza gente, brainstorming!
"attwo":
Tanti auguri, Rggb, [tex]10! = 3,628,800[/tex]
So benissimo quanto è il fattoriale di 10. Ma il mio tentativo è di contare, e ovviamente non ogni singola permutazione, ma calcolare quante sono.
Ti ripeto il ragionamento, considero le sequenze di dieci cifre (prendo un "mazzo 10" formato dalle "carte" 1 2 3 4 5 6 7 8 9 0) e provo a vedere quante sono le p. nelle quali c'è almeno una cifra in posizione corrispondente.
- quelle che cominciano per 1: 1234567890 1230567894 ... quante sono? (facile)
- quelle che hanno 2 in seconda cifra: 1234567890 (ancora) 3298765401 ... lo stesso numero di prima.
Come vedi, devo considerare delle ripetizioni, ma non mi sembra difficile venirne a capo. Cosa pensavi, che le contassi una per una con un calcolatore?
La cosa difficile è che questo calcolo va adattato ad un "mazzo 40", e ancora sono al buio - ma prima o poi mi (ti?) verrà qualcosa in mente.
NOTA: direi di spostare il tutto nella sezione Probabilità e Statistica, qualche moderatore è d'accordo?
Come vedi, devo considerare delle ripetizioni...
Idea molto interessante. Il problema è che non puoi sapere in anticipo nè quali nè quante combinazioni hai contato più volte, anzi, non è difficile dimostrare che il risultato della tua formula (dati n elementi) sarà sempre uguale ad $ n! $.
Un esempio per capirici:
Quante sono le permutazioni che iniziano con 1? Ovviamente $ (n-1)! $
Quante sono le permutazioni che iniziano con 2? Ovviamente $ (n-1)! $
...
Quante sono le permutazioni che iniziano con n? Ovviamente $ (n-1)! $
Totale: $ n(n-1)! = n! $
L'unico modo per "cavarsi dai guai" è utilizzare il metodo che ho già descritto nel post precedente, "riducendo" il problema a casi sempre più semplici, ma generando una formula ricorsiva...
Salvo nuove idee, of course.
Per quanto riguardo le permutazioni a punti fissi, già altre volte è stato affrontato questo problema.
https://www.matematicamente.it/forum/dis ... 49348.html
Al termine del topic, ci sta un link a wikipedia per calcolare in modo semplice tali permutazioni.
Il problema proposto da attwo è un tantino piu' complesso, perchè su 40 carte non abbiamo 40 punti fissi, ma 10. Quindi il tutto si complica...
Il problema è molto simile al solitario del prigioniero (... o nome similare ... )
https://www.matematicamente.it/forum/dis ... 49348.html
Al termine del topic, ci sta un link a wikipedia per calcolare in modo semplice tali permutazioni.
Il problema proposto da attwo è un tantino piu' complesso, perchè su 40 carte non abbiamo 40 punti fissi, ma 10. Quindi il tutto si complica...
Il problema è molto simile al solitario del prigioniero (... o nome similare ... )
"attwo":
Il problema è che non puoi sapere in anticipo nè quali nè quante combinazioni hai contato più volte, anzi, non è difficile dimostrare che il risultato della tua formula (dati n elementi) sarà sempre uguale ad $ n! $.
Non è la "mia" formula, ma ovviamente hai dimostrato ben poco, se non consideri le ripetizioni. E non è vero che "non posso saperlo in anticipo", vedi per esempio il messaggio di Umby.
@Umby
Sto cercando infatti di generalizzare: usando l'altra terminologia direi che ho 40 punti fissi, e sto cercando di calcolare in quanti modi posso mettere questi punti fissi in maniera differente, ovviamente senza ripetizioni.
(non so se riesco a spiegarmi bene... anzi direi proprio di no
mi faro vivo ancora quando avrò più tempo)
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo