Indovina il seme
Ho un mazzo di 40 carte da briscola. Quattro semi (denari, coppe, spade, bastoni) e dieci carte per ogni seme (da 1 a 10).
Il gioco è questo: scartare una carta dopo l'altra cercando di indovinarne il seme. Supponiamo di giocare in modo perfetto (vale a dire, ricordando le carte scese) assegnando una qualche preferenza ai semi, per esempio denari - coppe - spade - bastoni, in caso di parità di semi scesi.
La mia domanda è: qual è il numero medio di carte indovinate se si gioca in modo perfetto?
Procedendo a caso il numero medio è ovviamente 10, ma giocando con la memoria delle carte scese dovrebbe essere apprezzabilmente più alto.
Naturalmente uno può riformulare la cosa dicendo che le carte sono i numeri da 1 a 40 e la cosa da indovinare è la classe resto modulo 4. Io ho una idea di cosa potrebbe essere ma lo devo ancora dimostrare.
Il gioco è questo: scartare una carta dopo l'altra cercando di indovinarne il seme. Supponiamo di giocare in modo perfetto (vale a dire, ricordando le carte scese) assegnando una qualche preferenza ai semi, per esempio denari - coppe - spade - bastoni, in caso di parità di semi scesi.
La mia domanda è: qual è il numero medio di carte indovinate se si gioca in modo perfetto?
Procedendo a caso il numero medio è ovviamente 10, ma giocando con la memoria delle carte scese dovrebbe essere apprezzabilmente più alto.
Naturalmente uno può riformulare la cosa dicendo che le carte sono i numeri da 1 a 40 e la cosa da indovinare è la classe resto modulo 4. Io ho una idea di cosa potrebbe essere ma lo devo ancora dimostrare.
Risposte
vedendo questo topic qualche giorno fa, ho provato ad affrontare il problema con un metodo molto simile a DajeForte, poi ho accantonato la cosa, e, visto che si è passati a metodi "informatici", ogni tanto mi sono incuriosita a vedere la discussione ed i risultati, senza però prestare molta attenzione ai passaggi.
a questo punto provo a buttar giù la mia formula, chiedendo un supporto informatico per il calcolo di $P[Max X_(j_i)=N]$, sperando di riuscire a chiarire che cosa si intende, e del risultato finale.
considerando la definizione di media, adattata al fatto che "ogni risultato positivo conta per $1$", trovo la media come la somma (su $i$) delle probabilità di indovinare la $i$-esima carta. in maniera molto schematica, tale probabilità è il rapporto tra il "massimo valore che posso scegliere" tra le carte rimaste di un seme e il totale delle $41-i$ carte rimaste. ma questo massimo valore non è univocamente determinato, e anch'esso può essere considerato una media, quindi una sommatoria dei prodotti dei numeri da 1 a 10 per le rispettive probabilità che questi siano il massimo (ciò che si potrebbe anche trovare informaticamente).
scrivo la formula (mi scuso se non fosse una novità rispetto ad altri interventi precedenti):
$E=sum_(i=1)^40\(1/(41-i)*sum_(N=1)^10\N*P[Max X_(j_i)=N])$, ove $j in {1,2,3,4}$, con $0<=X_j_i<=10, (X_1+X_2+X_3+X_4)_i=41-i$.
spero si capisca. ciao.
a questo punto provo a buttar giù la mia formula, chiedendo un supporto informatico per il calcolo di $P[Max X_(j_i)=N]$, sperando di riuscire a chiarire che cosa si intende, e del risultato finale.
considerando la definizione di media, adattata al fatto che "ogni risultato positivo conta per $1$", trovo la media come la somma (su $i$) delle probabilità di indovinare la $i$-esima carta. in maniera molto schematica, tale probabilità è il rapporto tra il "massimo valore che posso scegliere" tra le carte rimaste di un seme e il totale delle $41-i$ carte rimaste. ma questo massimo valore non è univocamente determinato, e anch'esso può essere considerato una media, quindi una sommatoria dei prodotti dei numeri da 1 a 10 per le rispettive probabilità che questi siano il massimo (ciò che si potrebbe anche trovare informaticamente).
scrivo la formula (mi scuso se non fosse una novità rispetto ad altri interventi precedenti):
$E=sum_(i=1)^40\(1/(41-i)*sum_(N=1)^10\N*P[Max X_(j_i)=N])$, ove $j in {1,2,3,4}$, con $0<=X_j_i<=10, (X_1+X_2+X_3+X_4)_i=41-i$.
spero si capisca. ciao.
Si Ada questo è esattamente quello che dicevo, ovvero condizionare l'evento "la azzecco o no" sulle carte che sono uscite.
Il problema è che, finchè sono due semi la cosa è fattibile,
perchè ad esempio dopo 10 estrazioni si possono avere che le dieci carte sono (10,0)(9,1),....(0,10) punto.
Se invece eleviamo il numero dei semi la cosa si complica enormemente e se poniamo questa variabile (max) = k vuol dire che ameno una deve essere uguale e le altre minori il che già in tre dimensioni crea qualche problema figuriamoci se da un piano passiamo ancora a dimensioni maggiori.
È proprio questo quello che io ho fatto fare al mio programma, ho fatto fare a lui il ragionamento su tutte le n-uple di carte per seme uscite dopo i estrazioni $(n_1,...,n_n)$ maniera che $max{n_j}=k$ e $sum_(j)^n n_j=i$ (n semi, i estrazioni effettuate). ?Casi favorevoli su possibili??Coefficienti multinomiali?
Sarebbe anche interessante trovare un'altra strada come per esempio quella di Martino, o magari provare a ragionare su delle strutture di simmetria che però vedo difficile perchè se uno vede la formula da due, quella da quattro deve essere ben più complicata e lo vedo difficile ottenerla mediante semplici ragionamenti induttivi.
Il problema è che, finchè sono due semi la cosa è fattibile,
perchè ad esempio dopo 10 estrazioni si possono avere che le dieci carte sono (10,0)(9,1),....(0,10) punto.
Se invece eleviamo il numero dei semi la cosa si complica enormemente e se poniamo questa variabile (max) = k vuol dire che ameno una deve essere uguale e le altre minori il che già in tre dimensioni crea qualche problema figuriamoci se da un piano passiamo ancora a dimensioni maggiori.
È proprio questo quello che io ho fatto fare al mio programma, ho fatto fare a lui il ragionamento su tutte le n-uple di carte per seme uscite dopo i estrazioni $(n_1,...,n_n)$ maniera che $max{n_j}=k$ e $sum_(j)^n n_j=i$ (n semi, i estrazioni effettuate). ?Casi favorevoli su possibili??Coefficienti multinomiali?
Sarebbe anche interessante trovare un'altra strada come per esempio quella di Martino, o magari provare a ragionare su delle strutture di simmetria che però vedo difficile perchè se uno vede la formula da due, quella da quattro deve essere ben più complicata e lo vedo difficile ottenerla mediante semplici ragionamenti induttivi.
Per risolvere il problema con due semi ho cercato di ragionare su un tipo di sequenza binaria che ho chiamato "sequenza irriducibile".
Una sequenza binaria finita si dice "equa" se in essa ci sono tanti 1 quanti 0. In particolare ogni sequenza equa ha lunghezza pari. E' facile vedere che il numero di sequenze eque di lunghezza [tex]n[/tex] è [tex]\binom{n}{n/2}[/tex].
Una sequenza binaria finita equa [tex](a_1,...,a_n)[/tex] si dice irriducibile se [tex](a_1,...,a_k)[/tex] non è equa per nessun [tex]k < n[/tex].
Chiamiamo [tex]P=\{(01),(10)\}[/tex] l'insieme delle preferenze, e scegliamo [tex]p \in P[/tex]. Sia [tex]s[/tex] una sequenza binaria finita equa. Il "numero indovinato di [tex]s[/tex] rispetto a [tex]p[/tex]" è il numero di cifre indovinate secondo il nostro gioco. Lo indico con [tex]\iota_p(s)[/tex].
Per esempio [tex]\iota_{01}(110100) = 3[/tex].
Il "numero indovinato di [tex]s[/tex] mediato sulle preferenze", o "P-medio di [tex]s[/tex]", è [tex]\frac{1}{2} (\iota_{10}(s)+\iota_{01}(s))[/tex].
Per le sequenze binarie risulta che tutte le sequenze irriducibili di lunghezza fissata hanno lo stesso P-medio:
Lemma 1. Il P-medio di una qualsiasi sequenza binaria finita equa irriducibile di lunghezza [tex]n[/tex] è [tex](n+1)/2[/tex].
Dimostrazione. Chiaramente, una sequenza [tex]s[/tex] equa irriducibile di lunghezza [tex]n>2[/tex] comincia con due uni oppure con due zeri. Per simmetria possiamo supporre che cominci con due uni. Allora [tex]\iota_{10}(s)=n/2+1[/tex] e [tex]\iota_{01}(s)=n/2[/tex]. La media è [tex](n+1)/2[/tex]. []
Dobbiamo ora sapere quante sono le sequenze eque irriducibili di una lunghezza fissata [tex]n[/tex].
Lemma 2. Il numero di sequenze eque irriducibili di lunghezza [tex]n[/tex] è [tex]\frac{4}{n} \binom{n-2}{(n-2)/2}[/tex].
Dimostrazione. Ogni sequenza binaria si può rappresentare come una spezzata nel piano cartesiano che parte dall'origine e sale in corrispondenza degli uni e scende in corrispondenza degli zeri. Per esempio la seguente spezzata corrisponde alla sequenza (non equa) 101101.
Una sequenza equa corrisponde ovviamente ad una spezzata il cui punto di arrivo appartiene all'asse delle ascisse. Prendiamo una sequenza equa s che comincia con la cifra 1. Dire che s è irriducibile equivale ovviamente a dire che la corrispondente spezzata intercetta l'asse delle ascisse solo nei punti (0,0) e (n,0). In altre parole, la sequenza ottenuta togliendo la prima e l'ultima cifra (che sono rispettivamente 1 e 0) non scende mai sotto il livello da cui è partita. Siamo quindi ridotti a contare il numero di sequenze eque di lunghezza [tex]n-2[/tex] che non scendono mai sotto l'asse delle ascisse. Questo è ovviamente equivalente a contare le sequenze eque di lunghezza [tex]n-2[/tex] che scendono sotto l'asse delle ascisse, cioè che intercettano la retta [tex]y=-1[/tex]. Sia [tex]x_0[/tex] la minima ascissa di un punto di intersezione tra la spezzata e la retta [tex]y=-1[/tex]. Consideriamo la spezzata ottenuta da quella originale simmetrizzando la parte prima di [tex]x_0[/tex] rispetto alla retta [tex]y=-1[/tex]. Questa nuova sequenza parte dal punto [tex](0,-2)[/tex] ed arriva a [tex](n-2,0)[/tex]. E' facile dedurre che il numero di spezzate di lunghezza [tex]n-2[/tex] che intercettano la retta [tex]y=-1[/tex] è uguale al numero di spezzate che partono da [tex](0,-2)[/tex] ed arrivano a [tex](n-2,0)[/tex]. Si tratta delle sequenze di lunghezza [tex]n-2[/tex] con [tex](n-2)/2+1[/tex] uni e [tex](n-2)/2-1[/tex] zeri. Risulta quindi che il numero di sequenze eque non irriducibili che partono da 1 è [tex]\binom{n-2}{(n-2)/2+1}[/tex]. Il numero di sequenze eque irriducibili che partono da 1 risulta quindi essere [tex]\binom{n-2}{(n-2)/2}-\binom{n-2}{(n-2)/2+1} = \binom{n-2}{(n-2)/2} \cdot (1-(\frac{n-2}{2})/(\frac{n-2}{2}+1)) = \binom{n-2}{(n-2)/2} \cdot 2/n[/tex]. Raddoppiando questo numero (per contare anche le sequenze che cominciano con 0) otteniamo il numero voluto. []
Per esempio le sequenze eque irriducibili di lunghezza 4 sono 1100 e 0011, quelle di lunghezza 6 sono 111000, 110100, 000111, 001011.
Ora mi servono due osservazioni importanti.
Osservazione 1. La media del numero indovinato (rispetto a una preferenza fissata) di tutte le sequenze eque di lunghezza [tex]n[/tex] coincide con la media di tali medie sull'insieme delle preferenze. In altre parole detto S l'insieme delle sequenze eque di lunghezza n, si ha [tex]\text{Media}(n,2) = \frac{1}{|S|} \sum_{s \in S} \iota_p(s) = \frac{1}{|P|}\sum_{p \in P} \frac{1}{|S|} \sum_{s \in S} \iota_p(s)[/tex]. In particolare potendo scambiare le sommatorie otteniamo che [tex]\text{Media}(n,2) = \frac{1}{|S|} \sum_{s \in S} \frac{1}{|P|} \sum_{p \in P} \iota_p(s)[/tex]. Quindi la media dei numeri indovinati è uguale alla media dei P-medi delle sequenze.
Osservazione 2. Ogni sequenza equa si decompone in sequenze irriducibili in un unico modo. Basta partire da sinistra e fare un segno ogni volta che si incorre in una sequenza equa. Per esempio la decomposizione di 1000101101000111 è 10|001011|01|000111. E' facile vedere che il P-medio di una sequenza equa è uguale alla somma dei P-medi delle sue componenti irriducibili. Per esempio il P-medio di 1000101101000111 è 1.5+3.5+1.5+3.5 = 10.
Riporto la tabella del caso n=6 spezzando le sequenze.
[tex]\begin{array}{c|c|c|c} \text{sequenza } s & \iota_{10}(s) & \iota_{01}(s) & \text{P-medio} \\ \hline 111000 & 4 & 3 & 3.5 \\ \hline 000111 & 3 & 4 & 3.5 \\ \hline 110100 & 4 & 3 & 3.5 \\ \hline 001011 & 3 & 4 & 3.5 \\ \hline 1100/10 & 5 & 3 & 4 \\ \hline 0011/01 & 3 & 5 & 4 \\ \hline 1100/01 & 4 & 4 & 4 \\ \hline 0011/10 & 4 & 4 & 4 \\ \hline 10/1100 & 5 & 3 & 4 \\ \hline 01/0011 & 3 & 5 & 4 \end{array}[/tex] [tex]\begin{array}{c|c|c|c} \text{sequenza } s & \iota_{10}(s) & \iota_{01}(s) & \text{P-medio} \\ \hline 10/10/10 & 6 & 3 & 4.5 \\ \hline 01/01/01 & 3 & 6 & 4.5 \\ \hline 10/10/01 & 5 & 4 & 4.5 \\ \hline 01/01/10 & 4 & 5 & 4.5 \\ \hline 10/01/01 & 4 & 5 & 4.5 \\ \hline 01/10/10 & 5 & 4 & 4.5 \\ \hline 10/01/10 & 5 & 4 & 4.5 \\ \hline 01/10/01 & 4 & 5 & 4.5 \\ \hline 10/0011 & 4 & 4 & 4 \\ \hline 01/1100 & 4 & 4 & 4 \end{array}[/tex]
Il problema per quanto riguarda le sequenze binarie è quindi quasi risolto. La sola cosa che resta da capire è quante volte occorre una data sequenza equa irriducibile come componente irriducibile di una sequenza equa di lunghezza [tex]n[/tex]. Questo è un fatto empirico di cui tuttavia sono abbastanza convinto:
Lemma 3. Il numero di occorrenze di una data sequenza equa irriducibile di lunghezza [tex]2k[/tex] (pari e minore o uguale a n) come componente irriducibile di una qualche sequenza equa di lunghezza [tex]n[/tex] è [tex]2^{n-2k}[/tex].
Dimostrazione. Scriviamo [tex]n=2k+2m[/tex]. Una sequenza irriducibile di lunghezza [tex]2k[/tex] collocata come fattore irriducibile di una data sequenza equa di lunghezza [tex]n[/tex] è determinata dalla sequenza equa alla sua sinistra e da quella alla sua destra. Tali due sequenze hanno lunghezze (ovviamente pari e non necessariamente non nulle) la cui somma è [tex]2m[/tex], quindi il numero totale di occorrenze della data sequenza irriducibile di lunghezza [tex]2k[/tex] è uguale alla somma [tex]\sum_{a+b=m} \binom{2a}{a} \binom{2b}{b}[/tex]. Come dimostrato da gugo82, il valore di questa somma è [tex]2^{2m}[/tex]. Riporto qui la dimostrazione. Lo sviluppo di Taylor della funzione [tex]1/\sqrt{1-4x}[/tex] attorno a zero è [tex]\sum_{m=0}^{\infty} \binom{2m}{m} x^m[/tex], quindi
[tex]1/(1-4x) = (1/\sqrt{1-4x})^2 = \left(\sum_{m=0}^{\infty} \binom{2m}{m} x^m \right)^2 = \sum_{m=0}^{\infty} \left( \sum_{a+b=m} \binom{2a}{a} \binom{2b}{b} \right) x^m[/tex].
Ne segue che [tex]\sum_{a+b=m} \binom{2a}{a} \binom{2b}{b} = \frac{1}{m!} \frac{d^m}{dx^m} \frac{1}{1-4x}|_{x=0} = \frac{1}{m!} \frac{4^m m!}{(1-4x)^m}|_{x=0} = 4^m = 2^{2m}[/tex]. []
Per l'osservazione 2, la somma dei P-medi delle sequenze eque di lunghezza [tex]n[/tex] è uguale alla somma dei P-medi delle sequenze eque irriducibili di lunghezza minore o uguale a n che occorrono come componenti irriducibili, contate ovviamente il numero di volte in cui occorrono, quindi tale somma risulta essere la seguente:
[tex]\sum_{k=1}^{n/2} \frac{2k+1}{2} \cdot \frac{4}{2k} \binom{2k-2}{k-1} \cdot 2^{n-2k}[/tex].
La media sulle [tex]\binom{n}{n/2}[/tex] sequenze eque risulta quindi essere
[tex]\text{Media}(n,2) = (\sum_{k=1}^{n/2} 2 \cdot \frac{2k+1}{2k} \cdot \binom{2k-2}{k-1} \cdot 2^{n-2k})/\binom{n}{n/2} = \frac{n}{2} - \frac{1}{2} + \frac{2^{n-1}}{\binom{n}{n/2}}[/tex].
L'ultimo passaggio l'ho fatto con l'aiuto di Wolfram Alpha.
In particolare la media è asintotica a [tex]n/2[/tex]. La stessa media che avremmo senza ricordarci le carte. In altre parole ricordarsi le carte scese non aiuta molto
Una sequenza binaria finita si dice "equa" se in essa ci sono tanti 1 quanti 0. In particolare ogni sequenza equa ha lunghezza pari. E' facile vedere che il numero di sequenze eque di lunghezza [tex]n[/tex] è [tex]\binom{n}{n/2}[/tex].
Una sequenza binaria finita equa [tex](a_1,...,a_n)[/tex] si dice irriducibile se [tex](a_1,...,a_k)[/tex] non è equa per nessun [tex]k < n[/tex].
Chiamiamo [tex]P=\{(01),(10)\}[/tex] l'insieme delle preferenze, e scegliamo [tex]p \in P[/tex]. Sia [tex]s[/tex] una sequenza binaria finita equa. Il "numero indovinato di [tex]s[/tex] rispetto a [tex]p[/tex]" è il numero di cifre indovinate secondo il nostro gioco. Lo indico con [tex]\iota_p(s)[/tex].
Per esempio [tex]\iota_{01}(110100) = 3[/tex].
Il "numero indovinato di [tex]s[/tex] mediato sulle preferenze", o "P-medio di [tex]s[/tex]", è [tex]\frac{1}{2} (\iota_{10}(s)+\iota_{01}(s))[/tex].
Per le sequenze binarie risulta che tutte le sequenze irriducibili di lunghezza fissata hanno lo stesso P-medio:
Lemma 1. Il P-medio di una qualsiasi sequenza binaria finita equa irriducibile di lunghezza [tex]n[/tex] è [tex](n+1)/2[/tex].
Dimostrazione. Chiaramente, una sequenza [tex]s[/tex] equa irriducibile di lunghezza [tex]n>2[/tex] comincia con due uni oppure con due zeri. Per simmetria possiamo supporre che cominci con due uni. Allora [tex]\iota_{10}(s)=n/2+1[/tex] e [tex]\iota_{01}(s)=n/2[/tex]. La media è [tex](n+1)/2[/tex]. []
Dobbiamo ora sapere quante sono le sequenze eque irriducibili di una lunghezza fissata [tex]n[/tex].
Lemma 2. Il numero di sequenze eque irriducibili di lunghezza [tex]n[/tex] è [tex]\frac{4}{n} \binom{n-2}{(n-2)/2}[/tex].
Dimostrazione. Ogni sequenza binaria si può rappresentare come una spezzata nel piano cartesiano che parte dall'origine e sale in corrispondenza degli uni e scende in corrispondenza degli zeri. Per esempio la seguente spezzata corrisponde alla sequenza (non equa) 101101.
Una sequenza equa corrisponde ovviamente ad una spezzata il cui punto di arrivo appartiene all'asse delle ascisse. Prendiamo una sequenza equa s che comincia con la cifra 1. Dire che s è irriducibile equivale ovviamente a dire che la corrispondente spezzata intercetta l'asse delle ascisse solo nei punti (0,0) e (n,0). In altre parole, la sequenza ottenuta togliendo la prima e l'ultima cifra (che sono rispettivamente 1 e 0) non scende mai sotto il livello da cui è partita. Siamo quindi ridotti a contare il numero di sequenze eque di lunghezza [tex]n-2[/tex] che non scendono mai sotto l'asse delle ascisse. Questo è ovviamente equivalente a contare le sequenze eque di lunghezza [tex]n-2[/tex] che scendono sotto l'asse delle ascisse, cioè che intercettano la retta [tex]y=-1[/tex]. Sia [tex]x_0[/tex] la minima ascissa di un punto di intersezione tra la spezzata e la retta [tex]y=-1[/tex]. Consideriamo la spezzata ottenuta da quella originale simmetrizzando la parte prima di [tex]x_0[/tex] rispetto alla retta [tex]y=-1[/tex]. Questa nuova sequenza parte dal punto [tex](0,-2)[/tex] ed arriva a [tex](n-2,0)[/tex]. E' facile dedurre che il numero di spezzate di lunghezza [tex]n-2[/tex] che intercettano la retta [tex]y=-1[/tex] è uguale al numero di spezzate che partono da [tex](0,-2)[/tex] ed arrivano a [tex](n-2,0)[/tex]. Si tratta delle sequenze di lunghezza [tex]n-2[/tex] con [tex](n-2)/2+1[/tex] uni e [tex](n-2)/2-1[/tex] zeri. Risulta quindi che il numero di sequenze eque non irriducibili che partono da 1 è [tex]\binom{n-2}{(n-2)/2+1}[/tex]. Il numero di sequenze eque irriducibili che partono da 1 risulta quindi essere [tex]\binom{n-2}{(n-2)/2}-\binom{n-2}{(n-2)/2+1} = \binom{n-2}{(n-2)/2} \cdot (1-(\frac{n-2}{2})/(\frac{n-2}{2}+1)) = \binom{n-2}{(n-2)/2} \cdot 2/n[/tex]. Raddoppiando questo numero (per contare anche le sequenze che cominciano con 0) otteniamo il numero voluto. []
Per esempio le sequenze eque irriducibili di lunghezza 4 sono 1100 e 0011, quelle di lunghezza 6 sono 111000, 110100, 000111, 001011.
Ora mi servono due osservazioni importanti.
Osservazione 1. La media del numero indovinato (rispetto a una preferenza fissata) di tutte le sequenze eque di lunghezza [tex]n[/tex] coincide con la media di tali medie sull'insieme delle preferenze. In altre parole detto S l'insieme delle sequenze eque di lunghezza n, si ha [tex]\text{Media}(n,2) = \frac{1}{|S|} \sum_{s \in S} \iota_p(s) = \frac{1}{|P|}\sum_{p \in P} \frac{1}{|S|} \sum_{s \in S} \iota_p(s)[/tex]. In particolare potendo scambiare le sommatorie otteniamo che [tex]\text{Media}(n,2) = \frac{1}{|S|} \sum_{s \in S} \frac{1}{|P|} \sum_{p \in P} \iota_p(s)[/tex]. Quindi la media dei numeri indovinati è uguale alla media dei P-medi delle sequenze.
Osservazione 2. Ogni sequenza equa si decompone in sequenze irriducibili in un unico modo. Basta partire da sinistra e fare un segno ogni volta che si incorre in una sequenza equa. Per esempio la decomposizione di 1000101101000111 è 10|001011|01|000111. E' facile vedere che il P-medio di una sequenza equa è uguale alla somma dei P-medi delle sue componenti irriducibili. Per esempio il P-medio di 1000101101000111 è 1.5+3.5+1.5+3.5 = 10.
Riporto la tabella del caso n=6 spezzando le sequenze.
[tex]\begin{array}{c|c|c|c} \text{sequenza } s & \iota_{10}(s) & \iota_{01}(s) & \text{P-medio} \\ \hline 111000 & 4 & 3 & 3.5 \\ \hline 000111 & 3 & 4 & 3.5 \\ \hline 110100 & 4 & 3 & 3.5 \\ \hline 001011 & 3 & 4 & 3.5 \\ \hline 1100/10 & 5 & 3 & 4 \\ \hline 0011/01 & 3 & 5 & 4 \\ \hline 1100/01 & 4 & 4 & 4 \\ \hline 0011/10 & 4 & 4 & 4 \\ \hline 10/1100 & 5 & 3 & 4 \\ \hline 01/0011 & 3 & 5 & 4 \end{array}[/tex] [tex]\begin{array}{c|c|c|c} \text{sequenza } s & \iota_{10}(s) & \iota_{01}(s) & \text{P-medio} \\ \hline 10/10/10 & 6 & 3 & 4.5 \\ \hline 01/01/01 & 3 & 6 & 4.5 \\ \hline 10/10/01 & 5 & 4 & 4.5 \\ \hline 01/01/10 & 4 & 5 & 4.5 \\ \hline 10/01/01 & 4 & 5 & 4.5 \\ \hline 01/10/10 & 5 & 4 & 4.5 \\ \hline 10/01/10 & 5 & 4 & 4.5 \\ \hline 01/10/01 & 4 & 5 & 4.5 \\ \hline 10/0011 & 4 & 4 & 4 \\ \hline 01/1100 & 4 & 4 & 4 \end{array}[/tex]
Il problema per quanto riguarda le sequenze binarie è quindi quasi risolto. La sola cosa che resta da capire è quante volte occorre una data sequenza equa irriducibile come componente irriducibile di una sequenza equa di lunghezza [tex]n[/tex]. Questo è un fatto empirico di cui tuttavia sono abbastanza convinto:
Lemma 3. Il numero di occorrenze di una data sequenza equa irriducibile di lunghezza [tex]2k[/tex] (pari e minore o uguale a n) come componente irriducibile di una qualche sequenza equa di lunghezza [tex]n[/tex] è [tex]2^{n-2k}[/tex].
Dimostrazione. Scriviamo [tex]n=2k+2m[/tex]. Una sequenza irriducibile di lunghezza [tex]2k[/tex] collocata come fattore irriducibile di una data sequenza equa di lunghezza [tex]n[/tex] è determinata dalla sequenza equa alla sua sinistra e da quella alla sua destra. Tali due sequenze hanno lunghezze (ovviamente pari e non necessariamente non nulle) la cui somma è [tex]2m[/tex], quindi il numero totale di occorrenze della data sequenza irriducibile di lunghezza [tex]2k[/tex] è uguale alla somma [tex]\sum_{a+b=m} \binom{2a}{a} \binom{2b}{b}[/tex]. Come dimostrato da gugo82, il valore di questa somma è [tex]2^{2m}[/tex]. Riporto qui la dimostrazione. Lo sviluppo di Taylor della funzione [tex]1/\sqrt{1-4x}[/tex] attorno a zero è [tex]\sum_{m=0}^{\infty} \binom{2m}{m} x^m[/tex], quindi
[tex]1/(1-4x) = (1/\sqrt{1-4x})^2 = \left(\sum_{m=0}^{\infty} \binom{2m}{m} x^m \right)^2 = \sum_{m=0}^{\infty} \left( \sum_{a+b=m} \binom{2a}{a} \binom{2b}{b} \right) x^m[/tex].
Ne segue che [tex]\sum_{a+b=m} \binom{2a}{a} \binom{2b}{b} = \frac{1}{m!} \frac{d^m}{dx^m} \frac{1}{1-4x}|_{x=0} = \frac{1}{m!} \frac{4^m m!}{(1-4x)^m}|_{x=0} = 4^m = 2^{2m}[/tex]. []
Per l'osservazione 2, la somma dei P-medi delle sequenze eque di lunghezza [tex]n[/tex] è uguale alla somma dei P-medi delle sequenze eque irriducibili di lunghezza minore o uguale a n che occorrono come componenti irriducibili, contate ovviamente il numero di volte in cui occorrono, quindi tale somma risulta essere la seguente:
[tex]\sum_{k=1}^{n/2} \frac{2k+1}{2} \cdot \frac{4}{2k} \binom{2k-2}{k-1} \cdot 2^{n-2k}[/tex].
La media sulle [tex]\binom{n}{n/2}[/tex] sequenze eque risulta quindi essere
[tex]\text{Media}(n,2) = (\sum_{k=1}^{n/2} 2 \cdot \frac{2k+1}{2k} \cdot \binom{2k-2}{k-1} \cdot 2^{n-2k})/\binom{n}{n/2} = \frac{n}{2} - \frac{1}{2} + \frac{2^{n-1}}{\binom{n}{n/2}}[/tex].
L'ultimo passaggio l'ho fatto con l'aiuto di Wolfram Alpha.
In particolare la media è asintotica a [tex]n/2[/tex]. La stessa media che avremmo senza ricordarci le carte. In altre parole ricordarsi le carte scese non aiuta molto
OT
Completamente fuori tema lo so. Scusate
Domani cercherò di understand quello scritto da Martino. Ma vorrei sapere:
posso chiederti ADA chi sia la donna rappresentata nel tuo avatar.
Sonbo molto curioso.
Scusatemi ancora per l'off topic ma è da un po' che me lo chiedevo.
Buon ferragosto.
Completamente fuori tema lo so. Scusate
Domani cercherò di understand quello scritto da Martino. Ma vorrei sapere:
posso chiederti ADA chi sia la donna rappresentata nel tuo avatar.
Sonbo molto curioso.
Scusatemi ancora per l'off topic ma è da un po' che me lo chiedevo.
Buon ferragosto.
Re-OT
ho risposto alla stessa domanda diverse volte, prima dando qualche indizio.
se lo chiedi "ancora", vuol dire che non ti sei informato.
visto che non ho voglia di "fare gli indovinelli", ti rispondo subito:
Maria Sklodowska Curie (Marie Curie).
non è più ferragosto, ma ricordo che dalle mie parti c'è una grotta in cui si ricorda San Rocco (si festeggia il 16 Agosto) e dai paesi intorno si usava fare la "scampagnata di ferragosto" proprio il 16, verso questo paese (Ripa di Fagnano Alto - AQ). dunque Buona Festa di San Rocco!
\OT
riguardo al problema, ho trovato qualcosa sulle partizioni di un naturale, con Martino altre volte ci siamo sentiti per problemi collegati, ma siccome è tutt'altro che banale la rielaborazione per questo caso particolare, ed inoltre si inserirebbe con forzatura nel mio schema precedente, dato che sarebbe impossibile inserire nella formula le probabilità delle singole stringhe, volevo sentire un vostro parere se possa essere utile una semplificazione (con un seme privilegiato) di una formula che conti le stringhe aventi il massimo noto: sono un po' arrugginita, dovrei riprendere in mano più formule per cercare di ricavare questa.
ho risposto alla stessa domanda diverse volte, prima dando qualche indizio.
se lo chiedi "ancora", vuol dire che non ti sei informato.
visto che non ho voglia di "fare gli indovinelli", ti rispondo subito:
Maria Sklodowska Curie (Marie Curie).
non è più ferragosto, ma ricordo che dalle mie parti c'è una grotta in cui si ricorda San Rocco (si festeggia il 16 Agosto) e dai paesi intorno si usava fare la "scampagnata di ferragosto" proprio il 16, verso questo paese (Ripa di Fagnano Alto - AQ). dunque Buona Festa di San Rocco!
\OT
riguardo al problema, ho trovato qualcosa sulle partizioni di un naturale, con Martino altre volte ci siamo sentiti per problemi collegati, ma siccome è tutt'altro che banale la rielaborazione per questo caso particolare, ed inoltre si inserirebbe con forzatura nel mio schema precedente, dato che sarebbe impossibile inserire nella formula le probabilità delle singole stringhe, volevo sentire un vostro parere se possa essere utile una semplificazione (con un seme privilegiato) di una formula che conti le stringhe aventi il massimo noto: sono un po' arrugginita, dovrei riprendere in mano più formule per cercare di ricavare questa.
"Martino":
Per esempio [tex]\iota_{01}(1101001) = 3[/tex].
Qui non sono concorde, infatti la sequenza che dovrebbe essere quella con la strategia migliore è 0000001, ovvero con [tex]i_p(1101001)=4[/tex]. Necessariamente poi il numero di cifre dovrebbe essere pari!
In teoria conoscendo le pescate passate, il primo seme potrebbe essere [tex]0[/tex] a parità di pescate già fatte e il seme con minori pescate altrimenti.
"Lord K":Qui non sono concorde, infatti la sequenza che dovrebbe essere quella con la strategia migliore è 0000001, ovvero con [tex]i_p(1101001)=4[/tex]. Necessariamente poi il numero di cifre dovrebbe essere pari!
[quote="Martino"]Per esempio [tex]\iota_{01}(1101001) = 3[/tex].
In teoria conoscendo le pescate passate, il primo seme potrebbe essere [tex]0[/tex] a parità di pescate già fatte e il seme con minori pescate altrimenti.[/quote]Hai ragione ho sbagliato a scrivere, intendevo la sequenza 110100. Ora ho corretto. Grazie.
Mi permetto di congetturare un risultato che sto cercando di supportare da una dimostrazione coerente, qui [tex]\mu_i(n,2)[/tex] è la media delle carte indovinate su un mazzo di [tex]n[/tex] carte e [tex]2[/tex] semi.
Congettura: [tex]\displaystyle \forall n \in \mathbb N, \mu_i(n,2) \geq \frac{2}{3} \cdot n[/tex]
Reputo che il metodo da me usato sia differente dal metodo di Martino. Osserviamo il caso di [tex]n=6, s=2[/tex]
[tex]\begin{tabular}{c|c|c} \text{sequenza s} & \text{sequenza ipotizzata} & \text{indovinate}
\\ \hline 000111 & 011111 & 4
\\ \hline 001011 & 011111 & 4
\\ \hline 001101 & 011101 & 5
\\ \hline 001110 & 011100 & 4
\\ \hline 010011 & 010111 & 5
\\ \hline 010101 & 010101 & 6
\\ \hline 010110 & 010100 & 5
\\ \hline 011001 & 010001 & 5
\\ \hline 011010 & 010000 & 4
\\ \hline 011101 & 010000 & 4
\\ \hline 100011 & 000111 & 4
\\ \hline 100101 & 000101 & 5
\\ \hline 100110 & 000100 & 4
\\ \hline 101001 & 000001 & 4
\\ \hline 101010 & 000000 & 3
\\ \hline 101100 & 000000 & 3
\\ \hline 110001 & 000001 & 4
\\ \hline 110010 & 000000 & 3
\\ \hline 110100 & 000000 & 3
\\ \hline 111000 & 000000 & 3
\end{tabular}[/tex]
Indovinate totali: [tex]82[/tex]
Media indovinete: [tex]\frac{82}{20} = 4,1[/tex]
Percentuale indovinate: [tex]\frac{82}{120} = 68,33%[/tex]
Congettura: [tex]\displaystyle \forall n \in \mathbb N, \mu_i(n,2) \geq \frac{2}{3} \cdot n[/tex]
Reputo che il metodo da me usato sia differente dal metodo di Martino. Osserviamo il caso di [tex]n=6, s=2[/tex]
[tex]\begin{tabular}{c|c|c} \text{sequenza s} & \text{sequenza ipotizzata} & \text{indovinate}
\\ \hline 000111 & 011111 & 4
\\ \hline 001011 & 011111 & 4
\\ \hline 001101 & 011101 & 5
\\ \hline 001110 & 011100 & 4
\\ \hline 010011 & 010111 & 5
\\ \hline 010101 & 010101 & 6
\\ \hline 010110 & 010100 & 5
\\ \hline 011001 & 010001 & 5
\\ \hline 011010 & 010000 & 4
\\ \hline 011101 & 010000 & 4
\\ \hline 100011 & 000111 & 4
\\ \hline 100101 & 000101 & 5
\\ \hline 100110 & 000100 & 4
\\ \hline 101001 & 000001 & 4
\\ \hline 101010 & 000000 & 3
\\ \hline 101100 & 000000 & 3
\\ \hline 110001 & 000001 & 4
\\ \hline 110010 & 000000 & 3
\\ \hline 110100 & 000000 & 3
\\ \hline 111000 & 000000 & 3
\end{tabular}[/tex]
Indovinate totali: [tex]82[/tex]
Media indovinete: [tex]\frac{82}{20} = 4,1[/tex]
Percentuale indovinate: [tex]\frac{82}{120} = 68,33%[/tex]
@Martino
La dimostrazione è mooolto carina.
Sto ancora lavorando per capire perché il programma mi fornisce risultati un po' inferiori (sospetto un problema sulle generazioni di numeri pseudo-casuali che dia preferenza ad "alcune" configurazioni - seguirà aggiornamento).
Risultati approssimati: il simulatore mi fornisce $m=22.5$ mentre il valore calcolato $M=23.5$
La dimostrazione è mooolto carina.
Sto ancora lavorando per capire perché il programma mi fornisce risultati un po' inferiori (sospetto un problema sulle generazioni di numeri pseudo-casuali che dia preferenza ad "alcune" configurazioni - seguirà aggiornamento).
"Martino":
puoi confrontare la mia formula con le prove sperimentali nel caso di 40 carte e 2 semi?
Risultati approssimati: il simulatore mi fornisce $m=22.5$ mentre il valore calcolato $M=23.5$
posto una nuova formula, con 40 carte e 2 semi (20 carte per ciascun seme):
$sum_(k=1)^20\{1/2*((2k-2),(k-1))*(((20)_(k-1))^2)/((40)_(2k-2)) + 2*[sum_(N=22-k)^20\N/(42-2k)*((2k-2),(20-N))*((20)_(20-N)*(20)_(2k+N-22))/((40)_(2k-2)) + sum_(N=21-k)^20\N/(41-2k)*((20)_(20-N) *(20)_(2k+N-21))/((40)_(2k-1))]}$
non ho controllato se viene come quella di Martino, comunque il calcolo diretto (con $n=6$) darebbe $3.5$.
prego coloro che sono intervenuti di provarla con strumenti informatici. grazie.
come altre volte, ho usato il simbolo $(n)_i$ per indicare il fattoriale decrescente $n*(n-1)*...*(n-i+1)$.
$sum_(k=1)^20\{1/2*((2k-2),(k-1))*(((20)_(k-1))^2)/((40)_(2k-2)) + 2*[sum_(N=22-k)^20\N/(42-2k)*((2k-2),(20-N))*((20)_(20-N)*(20)_(2k+N-22))/((40)_(2k-2)) + sum_(N=21-k)^20\N/(41-2k)*((20)_(20-N) *(20)_(2k+N-21))/((40)_(2k-1))]}$
non ho controllato se viene come quella di Martino, comunque il calcolo diretto (con $n=6$) darebbe $3.5$.
prego coloro che sono intervenuti di provarla con strumenti informatici. grazie.
come altre volte, ho usato il simbolo $(n)_i$ per indicare il fattoriale decrescente $n*(n-1)*...*(n-i+1)$.
@Lord K:
@Ada: con sei carte viene 4.1, non 3.5, quindi non credo che la tua formula funzioni. Ho dato in pasto la tua formula ad un programma e mi ha restituito il valore [tex]12.396[/tex]. Non può essere corretto, perché la media delle carte indovinate dev'essere almeno 20 (la metà delle carte).
"Lord K":Questa congettura è falsa a partire da [tex]n=8[/tex] perché la media con otto carte (che si può calcolare anche a mano) risulta [tex]5.32857[/tex] (approssimata all'ultima cifra scritta), mentre [tex]\frac{2}{3} \cdot 8 = 5.\bar{3}[/tex].
Congettura: [tex]\displaystyle \forall n \in \mathbb N, \mu_i(n,2) \geq \frac{2}{3} \cdot n[/tex]
@Ada: con sei carte viene 4.1, non 3.5, quindi non credo che la tua formula funzioni. Ho dato in pasto la tua formula ad un programma e mi ha restituito il valore [tex]12.396[/tex]. Non può essere corretto, perché la media delle carte indovinate dev'essere almeno 20 (la metà delle carte).
ok, grazie.
se hai idea di qualche possibile errore di trascrizione, fammelo sapere, perché effettivamente il calcolo diretto mi dava 3.5 e non 4.1.
intanto la rivedrò anch'io.
EDIT: me la stavo riscrivendo e mi sono accorta che ho saltato un pezzo (un coefficiente binomiale...): è meglio che non faccio ulteriori pasticci e la modifico in un nuovo post.
se hai idea di qualche possibile errore di trascrizione, fammelo sapere, perché effettivamente il calcolo diretto mi dava 3.5 e non 4.1.
intanto la rivedrò anch'io.
EDIT: me la stavo riscrivendo e mi sono accorta che ho saltato un pezzo (un coefficiente binomiale...): è meglio che non faccio ulteriori pasticci e la modifico in un nuovo post.
aggiungo il coefficiente binomiale mancante alla formula precedente:
"adaBTTLS":
posto una nuova formula, con 40 carte e 2 semi (20 carte per ciascun seme):
$sum_(k=1)^20\{1/2*((2k-2),(k-1))*(((20)_(k-1))^2)/((40)_(2k-2)) + 2*[sum_(N=22-k)^20\N/(42-2k)*((2k-2),(20-N))*((20)_(20-N)*(20)_(2k+N-22))/((40)_(2k-2)) + sum_(N=21-k)^20\N/(41-2k)*((2k-1),(20-N))*((20)_(20-N) *(20)_(2k+N-21))/((40)_(2k-1))]}$
non ho controllato se viene come quella di Martino, comunque il calcolo diretto (con $n=6$) darebbe $3.5$.
prego coloro che sono intervenuti di provarla con strumenti informatici. grazie.
come altre volte, ho usato il simbolo $(n)_i$ per indicare il fattoriale decrescente $n*(n-1)*...*(n-i+1)$.
@Ada: con la nuova formula che hai messo viene 23.4882, come viene a me. Come hai fatto ad ottenerla?
a proposito di verifica diretta, ho provato ad applicarla con $n=6$ (mi sono quasi "impazzita" perché non l'ho riscritta con 3 al posto di 20, e dopo una giornata particolarmente pesante ...): ho ottenuto 4.1 e non 3.5 come avevo trovato con "calcolo diretto": qual è il valore giusto?
io ho prima distinto i casi di $i$ pari e dispari (che poi ho chiamato, per $k$ da 1 a 20, $2k-1$ e $2k$): $i$ però rappresentava la $i$-esima carta, per cui la probabilità si trovava con le $i-1$ carte precedenti (quindi $2k-2$ per $i$ dispari e $2k-1$ per $i$ pari).
la probabilità che $r$ carte siano rosse e $i-1-r$ carte siano nere è data da $((i-1),(r))*((20)_r*(20)_(i-1-r))/((40)_(i-1))$.
visto che qui non contava quale colore fosse più rappresentato, per $i$ dispari bisognava isolare il termine con $r=(i-1)/2$ mentre tutti gli altri casi valevano per "due".
$AA k$, con un termine ($i=2k-1, r=k-1$) e due sommatorie, entrambe raddoppiate, una per $i=2k-1$ e una per $i=2k$, ho esaurito tutti i casi.
N.B.: io avevo provato con $i=10$ e $i=15$ a impostare il discorso, ma alla fine, quando mi sono posto il problema di "fermarmi" prima di 20 con la sommatoria, ho provato anche $i=30$, e il fattoriale decrescente mi risolve il problema perché mi annulla gli ultimi termini.
sulla tua hai già detto qualcosa, ma come l'hai ottenuta?
io ho prima distinto i casi di $i$ pari e dispari (che poi ho chiamato, per $k$ da 1 a 20, $2k-1$ e $2k$): $i$ però rappresentava la $i$-esima carta, per cui la probabilità si trovava con le $i-1$ carte precedenti (quindi $2k-2$ per $i$ dispari e $2k-1$ per $i$ pari).
la probabilità che $r$ carte siano rosse e $i-1-r$ carte siano nere è data da $((i-1),(r))*((20)_r*(20)_(i-1-r))/((40)_(i-1))$.
visto che qui non contava quale colore fosse più rappresentato, per $i$ dispari bisognava isolare il termine con $r=(i-1)/2$ mentre tutti gli altri casi valevano per "due".
$AA k$, con un termine ($i=2k-1, r=k-1$) e due sommatorie, entrambe raddoppiate, una per $i=2k-1$ e una per $i=2k$, ho esaurito tutti i casi.
N.B.: io avevo provato con $i=10$ e $i=15$ a impostare il discorso, ma alla fine, quando mi sono posto il problema di "fermarmi" prima di 20 con la sommatoria, ho provato anche $i=30$, e il fattoriale decrescente mi risolve il problema perché mi annulla gli ultimi termini.
sulla tua hai già detto qualcosa, ma come l'hai ottenuta?
"adaBTTLS":Il valore giusto è 4.1. Io col calcolo diretto ho trovato proprio 4.1.
ho ottenuto 4.1 e non 3.5 come avevo trovato con "calcolo diretto": qual è il valore giusto?
sulla tua hai già detto qualcosa, ma come l'hai ottenuta?Nel mio intervento del 15/08/2010 alle 18:10 c'è la dimostrazione della mia formula, mi manca solo da dimostrare il lemma di [tex]2^{n-k}[/tex], sono convinto che sia vero ma mi sta facendo dannare.
"Martino":
Nel mio intervento del 15/08/2010 alle 18:10 c'è la dimostrazione della mia formula, mi manca solo da dimostrare il lemma di [tex]2^{n-k}[/tex], sono convinto che sia vero ma mi sta facendo dannare.
a dire il vedo ho faticato ad entrare in quella terminologia, e francamente non ho ben capito quello che intendi dimostrare nel terzo lemma:
se prendo ad esempio una sequenza binaria come questa: $111010011000$ è equa ed irriducibile?
vuoi dimostrare che ad esempio esistono $2^8$ sottosequenze di lunghezza $4$ che siano come?
se prendo ad esempio una sequenza binaria come questa: $111010011000$ è equa ed irriducibile?Sì.
vuoi dimostrare che ad esempio esistono $2^8$ sottosequenze di lunghezza $4$ che siano come?Voglio mostrare (nel caso particolare) che ogni sequenza equa irriducibile di lunghezza 4 compare esattamente [tex]2^{12-4}[/tex] volte come fattore irriducibile di una qualche sequenza equa di lunghezza 12.
Ti faccio un esempio con n=6. Riporto la seguente tabella in cui ho spezzato ogni sequenza nei suoi fattori irriducibili.
[tex]\begin{array}{c|c|c|c} \text{sequenza } s & \iota_{10}(s) & \iota_{01}(s) & \text{P-medio} \\ \hline 111000 & 4 & 3 & 3.5 \\ \hline 000111 & 3 & 4 & 3.5 \\ \hline 110100 & 4 & 3 & 3.5 \\ \hline 001011 & 3 & 4 & 3.5 \\ \hline 1100/10 & 5 & 3 & 4 \\ \hline 0011/01 & 3 & 5 & 4 \\ \hline 1100/01 & 4 & 4 & 4 \\ \hline 0011/10 & 4 & 4 & 4 \\ \hline 10/1100 & 5 & 3 & 4 \\ \hline 01/0011 & 3 & 5 & 4 \end{array}[/tex] [tex]\begin{array}{c|c|c|c} \text{sequenza } s & \iota_{10}(s) & \iota_{01}(s) & \text{P-medio} \\ \hline 10/10/10 & 6 & 3 & 4.5 \\ \hline 01/01/01 & 3 & 6 & 4.5 \\ \hline 10/10/01 & 5 & 4 & 4.5 \\ \hline 01/01/10 & 4 & 5 & 4.5 \\ \hline 10/01/01 & 4 & 5 & 4.5 \\ \hline 01/10/10 & 5 & 4 & 4.5 \\ \hline 10/01/10 & 5 & 4 & 4.5 \\ \hline 01/10/01 & 4 & 5 & 4.5 \\ \hline 10/0011 & 4 & 4 & 4 \\ \hline 01/1100 & 4 & 4 & 4 \end{array}[/tex]
Come vedi qui le sequenze "10" e "01" compaiono come fattori irriducibili [tex]16=2^{6-2}[/tex] volte, "1100" e "0011" compaiono [tex]4=2^{6-4}[/tex] volte e "111000", "000111", "110100", "001011" compaiono [tex]1=2^{6-6}[/tex] volta. Quindi in questo caso possiamo affermare che una sequenza equa irriducibile di lunghezza [tex]k[/tex] (pari e compreso tra 2 e n) compare come fattore irriducibile di una sequenza equa di lunghezza n [tex]2^{n-k}[/tex] volte. Questo è vero anche per [tex]n=8[/tex] (l'ho verificato), e ho serie ragioni di credere che la formula che ho ottenuto sia vera nel caso [tex]n=40[/tex] (un'altra persona ha risolto questo caso e il risultato coincide). Quindi sono convinto che il lemma sia vero. Tuttavia ho pensato tutto il pomeriggio ad una dimostrazione ma non sono riuscito a trovarla.
dunque, vediamo un po':
hai scritto le $((6),(3))=20$ sequenze eque; $4/6*((4),(2))=4$ di esse sono risultate irriducibili; le altre $20-4=16$ le hai spezzate in sottosequenze eque irriducibili.
distinte, ce ne sono $2$ di lunghezza $2$ e $2$ di lunghezza $4$: ti chiedi perché in questa "frammentazione" è rispettato il ripetersi di ciascuna sequenza $2^(n-k)$ volte ... e se la formula è valida in generale.
proverò a rifletterci, ma probabilmente dovrò vedere il problema da un'altra prospettiva, e soprattutto avulso dal'argomento principale del topic.
anche le partizioni di un naturale potevano essere utili, ma il semplice conteggio non porta a nulla se non si riesce, con l'aiuto di esso, ad inserire in una formula le singole partizioni con le rispettive probabilità...
penso che, a patto di inserire più sommatorie di sommatorie o formule ricorsive, sia più semplice generalizzare la mia formula precedente (ma ovviamente questo è strettamente personale, e legato al tipo di ragionamento fatto finora...). a proposito, ti è chiara ora?
hai scritto le $((6),(3))=20$ sequenze eque; $4/6*((4),(2))=4$ di esse sono risultate irriducibili; le altre $20-4=16$ le hai spezzate in sottosequenze eque irriducibili.
distinte, ce ne sono $2$ di lunghezza $2$ e $2$ di lunghezza $4$: ti chiedi perché in questa "frammentazione" è rispettato il ripetersi di ciascuna sequenza $2^(n-k)$ volte ... e se la formula è valida in generale.
proverò a rifletterci, ma probabilmente dovrò vedere il problema da un'altra prospettiva, e soprattutto avulso dal'argomento principale del topic.
anche le partizioni di un naturale potevano essere utili, ma il semplice conteggio non porta a nulla se non si riesce, con l'aiuto di esso, ad inserire in una formula le singole partizioni con le rispettive probabilità...
penso che, a patto di inserire più sommatorie di sommatorie o formule ricorsive, sia più semplice generalizzare la mia formula precedente (ma ovviamente questo è strettamente personale, e legato al tipo di ragionamento fatto finora...). a proposito, ti è chiara ora?
non ho certo risolto il tuo problema, ma ho trovato un modo alternativo di contare le sottosequenze, ricorrendo alle partizioni di un naturale.
lavoro con $k=n/2$.
te lo illustro con $n=6 -> k=3$ e poi ti scrivo i risultati anche per $k=4$ e per $k=5$.
le partizioni di $k=3$ sono: $3, 2+1, 1+1+1$, e ciò, in termini di sequenze binarie di ordine $n=6$ ci dice che possiamo avere, come secondo il tuo schema:
- la sequenza composta di un'unica parte (equa irriducibile di ordine 6);
- la sequenza composta da due parti eque irriducibili (di cui una di ordine 4 ed una di ordine 2);
- la sequenza composta da tre parti eque irriducibili di ordine 2.
quante sono le sequenze eque irriducibili le sai trovare (in questo caso sono rispettivamente $4,2,2$);
inoltre quando hai due sottosequenze di ordine diverso le puoi solo scambiare fra loro in $2! =2$ modi;
quando hai tre sottosequenze dello stesso ordine non devi "scambiarle" se le conti opportunamente, infatti $((3),(3))=1$.
dunque:
le sequenze del primo tipo ($3$) sono $4$;
le sequenze del secondo tipo ($2+1$) sono $2*2*2=8$;
le sequenze del terzo tipo ($1+1+1$) sono $2^3=8$.
in totale $20$ come tornava a te.
ma quante volte compaiono sottosequenze di ordine due? ogni volta che troviamo $1$, e cioè: $4*0+8*1+8*3=32$;
quante sottosequenze di ordine 2 verificano le richieste? $2$;
per ragioni di simmetria (o regolarità), ciascuna di esse compare $32/2=16=2^4$ volte.
passiamo alle sottosequenze di ordine quattro, che compaiono $4*0+8*1+8*0=8$ volte, dunque, essendo $2$, ciascuna di esse compare $4=2^2$ volte.
(sotto)sequenze di ordine 6, banalmente compaiono $4$ volte, ed essendo 4, ciascuna compare 1 volta.
ora passo a $n=8 -> k=4$
$4 -> 10$
$3+1 -> 4*2*2=16$
$2+2 -> 2^2=4$
$2+1+1 -> 2*2^2*3=24$
$1+1+1+1 -> 2^4=16$
totale $70$
sottosequenze di ordine 2: $16*1+24*2+16*4=128 -> 128/2=64=2^6$
sottosequenze di ordine 4: $4*2+24*1=32 -> 32/2=16=2^4$
sottosequenze di ordine 6: $16*1=16 ->16/4=4=2^2$
sequenze di ordine 8: $10 ->10/10=1=2^0$
passo a $n=10 -> k=5$
$5 -> 28$
$4+1 ->10*2*2=40$
$3+2 -> 4*2*2=16$
$3+1+1 -> 4*2^2*3=48$
$2+2+1 -> 2^2*2*3=24$
$2+1+1+1 -> 2*2^3*4=64$
$1+1+1+1+1 -> 2^5=32$
tot. $252$
sott. 2: $40+48*2+24+64*3+32*5=2^9 -> (2^9)/2=2^8$
sott. 4: $16+24*2+64=128 ->128/2=2^6$
sott. 6: $16+48=64 -> 64/4=2^4$
sott. 8: $40 -> 40/10=4=2^2$
sott. 10: $28 ->28/28=1=2^0$
spero che ti possa essere utile. ciao.
lavoro con $k=n/2$.
te lo illustro con $n=6 -> k=3$ e poi ti scrivo i risultati anche per $k=4$ e per $k=5$.
le partizioni di $k=3$ sono: $3, 2+1, 1+1+1$, e ciò, in termini di sequenze binarie di ordine $n=6$ ci dice che possiamo avere, come secondo il tuo schema:
- la sequenza composta di un'unica parte (equa irriducibile di ordine 6);
- la sequenza composta da due parti eque irriducibili (di cui una di ordine 4 ed una di ordine 2);
- la sequenza composta da tre parti eque irriducibili di ordine 2.
quante sono le sequenze eque irriducibili le sai trovare (in questo caso sono rispettivamente $4,2,2$);
inoltre quando hai due sottosequenze di ordine diverso le puoi solo scambiare fra loro in $2! =2$ modi;
quando hai tre sottosequenze dello stesso ordine non devi "scambiarle" se le conti opportunamente, infatti $((3),(3))=1$.
dunque:
le sequenze del primo tipo ($3$) sono $4$;
le sequenze del secondo tipo ($2+1$) sono $2*2*2=8$;
le sequenze del terzo tipo ($1+1+1$) sono $2^3=8$.
in totale $20$ come tornava a te.
ma quante volte compaiono sottosequenze di ordine due? ogni volta che troviamo $1$, e cioè: $4*0+8*1+8*3=32$;
quante sottosequenze di ordine 2 verificano le richieste? $2$;
per ragioni di simmetria (o regolarità), ciascuna di esse compare $32/2=16=2^4$ volte.
passiamo alle sottosequenze di ordine quattro, che compaiono $4*0+8*1+8*0=8$ volte, dunque, essendo $2$, ciascuna di esse compare $4=2^2$ volte.
(sotto)sequenze di ordine 6, banalmente compaiono $4$ volte, ed essendo 4, ciascuna compare 1 volta.
ora passo a $n=8 -> k=4$
$4 -> 10$
$3+1 -> 4*2*2=16$
$2+2 -> 2^2=4$
$2+1+1 -> 2*2^2*3=24$
$1+1+1+1 -> 2^4=16$
totale $70$
sottosequenze di ordine 2: $16*1+24*2+16*4=128 -> 128/2=64=2^6$
sottosequenze di ordine 4: $4*2+24*1=32 -> 32/2=16=2^4$
sottosequenze di ordine 6: $16*1=16 ->16/4=4=2^2$
sequenze di ordine 8: $10 ->10/10=1=2^0$
passo a $n=10 -> k=5$
$5 -> 28$
$4+1 ->10*2*2=40$
$3+2 -> 4*2*2=16$
$3+1+1 -> 4*2^2*3=48$
$2+2+1 -> 2^2*2*3=24$
$2+1+1+1 -> 2*2^3*4=64$
$1+1+1+1+1 -> 2^5=32$
tot. $252$
sott. 2: $40+48*2+24+64*3+32*5=2^9 -> (2^9)/2=2^8$
sott. 4: $16+24*2+64=128 ->128/2=2^6$
sott. 6: $16+48=64 -> 64/4=2^4$
sott. 8: $40 -> 40/10=4=2^2$
sott. 10: $28 ->28/28=1=2^0$
spero che ti possa essere utile. ciao.
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo