Indovina il seme

Studente Anonimo
Studente Anonimo
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.

Risposte
chloe2
argomento piacevole

è davvero interessante, davvero fresco e grande informazione, è davvero bello sapere che questo tipo di moduli, davvero divertente e molto da pensare.

Rggb1
"Martino":
Quindi sono convinto che il lemma sia vero.

Ho seguito con interesse il tuo ragionamento, anche se ero partito da tutt'altro (ragionamento) per il problema originale - che ancora è messo male... siamo solo ai due semi ;)

Comunque stavo cercando di contare quelle che chiami sequenze eque irriducibili, ovvero
- "quante sono le sequenze (eque) irriducibili lunghe $n$?"
cercando cosi' di aggirare il problema cercando di "dimostrare che è una mucca partendo dalla coda invece che dalle corna".

Non ho ancora fatto un programma, magari ci penso domani; comunque ho fatto varie congetture e (contando) noto che:
- le sequenze irriducibili con $n=2$ sono 2 (essendo lunghe 2 esse sono irriducibili pd.)
- idem con $n=4$ sono 2
- idem con $n=6$ sono 4
- idem con $n=8$ sono 10
e mi sono fermato nel scrivere a mano. Ma se quelle con $n=10$ fossero 28 c'è da pensare (hai questo dato?) e forse una dimostrazione si trova.

Studente Anonimo
Studente Anonimo
"Rggb":
Comunque stavo cercando di contare quelle che chiami sequenze eque irriducibili, ovvero
- "quante sono le sequenze (eque) irriducibili lunghe $n$?"
cercando cosi' di aggirare il problema cercando di "dimostrare che è una mucca partendo dalla coda invece che dalle corna".

Non ho ancora fatto un programma, magari ci penso domani; comunque ho fatto varie congetture e (contando) noto che:
- le sequenze irriducibili con $n=2$ sono 2 (essendo lunghe 2 esse sono irriducibili pd.)
- idem con $n=4$ sono 2
- idem con $n=6$ sono 4
- idem con $n=8$ sono 10
e mi sono fermato nel scrivere a mano. Ma se quelle con $n=10$ fossero 28 c'è da pensare (hai questo dato?) e forse una dimostrazione si trova.
Considera che nel secondo lemma dimostro (all'inizio non avevo messo la dimostrazione, ma poi l'ho aggiunta) che il numero di sequenze eque irriducibili di lunghezza n è [tex]\frac{4}{n} \binom{n-2}{(n-2)/2}[/tex]. Quindi questo problema è risolto.

Il problema ancora da risolvere è: quante volte compare una data sequenza irriducibile di lunghezza [tex]2k \leq n[/tex] come fattore irriducibile di una qualche sequenza di lunghezza [tex]n[/tex]? La risposta è certamente [tex]2^{n-2k}[/tex] ma non sembra facile dimostrarlo. Magari lo è però. Boh.

Mi scuso se ti ho detto cose che sapevi già.

Studente Anonimo
Studente Anonimo
Vi ringrazio per il supporto :-D

Ora mi sono ridotto a dimostrare la seguente uguaglianza.

[tex]\displaystyle \sum_{a+b=t} \binom{2a}{a} \binom{2b}{b} = 2^{2t}[/tex],

dove [tex]0 \leq a,b \leq t[/tex]. Di nuovo, questa uguaglianza deve essere vera. Sto cercandone invano un'interpretazione insiemistica. Dietro c'è evidentemente una parametrizzazione delle sequenze binarie di lunghezza 2t (cioè dei sottoinsiemi di [tex]\{1,...,2t\}[/tex]), ma ancora non vedo quale. L'induzione non serve. Avete idee?

gugo82
Tanto per dirne una...

Col metodo della funzione generatrice si trova:

[tex]$\sum_{n=0}^{+\infty} \binom{2n}{n}\ x^n=\frac{1}{\sqrt{1-4x}}$[/tex]*;

quindi, tenendo a mente lo sviluppo del prodotto secondo Cauchy di due serie, si ha:

[tex]$\frac{1}{1-4x} = \left( \frac{1}{\sqrt{1-4x}} \right)^2 =\sum_{n=0}^{+\infty} \left\{\sum_{a+b=n} \binom{2a}{a} \binom{2b}{b}\right\}\ x^n$[/tex].

Confrontando lo sviluppo di Taylor/McLaurin di [tex]$\tfrac{1}{1-4x}$[/tex] con la serie precedente, per fissato [tex]$n$[/tex] naturale si ricava che:

[tex]$\sum_{a+b=n} \binom{2a}{a} \binom{2b}{b} =\frac{1}{n!}\ \frac{\text{d}^n}{\text{d} x^n} \left[ \frac{1}{1-4x}\right] \Big|_{x=0}$[/tex].

Per induzione si prova facilmente che:

[tex]$\frac{\text{d}^n}{\text{d} x^n} \left[ \frac{1}{1-4x}\right] =\frac{4^n\ n!}{(1-4x)^{n+1}}$[/tex]

ergo:

[tex]$\sum_{a+b=n} \binom{2a}{a} \binom{2b}{b} =\frac{4^n}{(1-4x)^{n+1}}\Big|_{x=0} =4^n=2^{2n}$[/tex],

come volevi. 8-)


P.S.: Si sarà capito che a me ragionare in maniera combinatoria secca parecchio... :lol:

L'idea della dimostrazione mi è venuta appena ho notato che le somme finite [tex]\sum_{a+b=t} \binom{2a}{a}\ \binom{2b}{b}[/tex] erano i termini della convoluzione della successione di termine generale [tex]f(n):=\binom{2n}{n}[/tex] con sé stessa; visto che la convoluzione [tex]$f(n)*f(n)$[/tex] è la successione dei coefficienti di Taylor del quadrato della serie [tex]$\sum f(n)\ x^n$[/tex], per terminare bastava determinare la somma di [tex]$\sum f(n)\ x^n$[/tex] e vedere se i conti venivano facili.


__________
* Si ricava dallo sviluppo della serie binomiale:

[tex]$(1-y)^\alpha =\sum_{n=0}^{+\infty} (-1)^n\ \binom{\alpha}{n}\ y^n$[/tex]

ponendo [tex]$\alpha=-\tfrac{1}{2}$[/tex] e facendo un po' di conti.

Studente Anonimo
Studente Anonimo
Onore all'analisi :D

Accidenti, sapevo che avevo già incontrato espressioni di quel tipo, ma la convoluzione non mi è proprio venuta in mente!

(OT: qual è il significato di [tex]\binom{\alpha}{n}[/tex] quando [tex]\alpha=-1/2[/tex]?)

PS.
Tanto per dirne una...
Significa che hai trovato altre dimostrazioni dell'uguaglianza?

gugo82
"Martino":
Onore all'analisi :D

:-D

"Martino":
Accidenti, sapevo che avevo già incontrato espressioni di quel tipo, ma la convoluzione non mi è proprio venuta in mente!

Visto che sotto-sotto sono un fan delle serie di potenze e delle funzioni analitiche, mi è venuto proprio naturale vedere quella somma in questo modo.

"Martino":
(OT: qual è il significato di [tex]\binom{\alpha}{n}[/tex] quando [tex]\alpha=-1/2[/tex]?)

Se [tex]$\alpha$[/tex] non è naturale, il coefficiente binomiale si definisce come:

[tex]$\binom{\alpha}{n} := \frac{1}{n!}\ \prod_{k=0}^{n-1} \alpha -k$[/tex];

tale definizione, se [tex]$\alpha \in \mathbb{N}$[/tex], restituisce il solito numerillo (infatti basta moltiplicare e dividere per [tex]$(\alpha -n)!$[/tex]).

"Martino":
PS.
Tanto per dirne una...
Significa che hai trovato altre dimostrazioni dell'uguaglianza?

Nono... Significa che l'ho buttata lì senza grosse pretese che ti piacesse.
E comunque confido che si possa dimostrare anche con metodi combinatori; dopotutto sono pur sempre permutazioni...

Studente Anonimo
Studente Anonimo
"gugo82":
Significa che l'ho buttata lì senza grosse pretese che ti piacesse.
Scherzi? Mi piace moltissimo invece.

Inserisco la dimostrazione del lemma.
Fatto.

gugo82
"Martino":
[quote="gugo82"]Significa che l'ho buttata lì senza grosse pretese che ti piacesse.
Scherzi? Mi piace moltissimo invece.

Inserisco la dimostrazione del lemma.
Fatto.[/quote]
Ad ogni modo non ho la più pallida idea di dove uscisse la tua relazione, perchè dopo la seconda pagina di conti tuoi e di ada mi perdo... Avete una bella pazienza, voi due! :lol:

Se metti tutto per iscritto, poi mi mandi il file pdf? Così ci do uno sguardo con calma e sangue freddo.

Grazie mille Martino.

adaBTTLS1
Martino, quello che dice gugo82 vale anche per me. dopo una mattinata (di ieri) in cui non mi sono collegata, ho trovato tutte queste belle novità:
volevo chiederti in che modo, con il nostro supporto, ti eri ricondotto all'ultimo sotto-problema. grazie.

Studente Anonimo
Studente Anonimo
In questa pagina ho scritto tutto con le dimostrazioni, dovrebbe essere abbastanza chiaro. Avevo anch'io idea di fare un pdf ma non ci riuscirò in tempi ragionevoli (oggi parto per una scuola estiva a Venezia...).

adaBTTLS1
sto provando a generalizzare la formula con due semi a più semi.
poiché c'è qualcosa che non mi convince nel passaggio da 2 a 3 semi, nel senso che l'impostazione era abbastanza complicata e lasciava presagire una formula ricorsiva mentre nello svolgimento e nell'esame dei vari sottocasi addirittura il risultato mi pare troppo semplice, prima di andare avanti ve la vorrei proporre per sottoporla a verifica anche informatica.
vi dico subito che la cosa che non mi convince è il fatto che con due soli semi la semplice suddivisione in pari-dispari ha complicato non poco la situazione, mentre con tre semi, con l'impostazione del tipo congruente a 1,2,0 (mod 3), considerando l'ordine di scelta sui semi di cui si è tanto parlato all'inizio, i casi si sono fermati a 3, contrariamente a quanto mi sarei potuta aspettare (io pensavo 3!=6, e non è detto che questo discorso sia valido mentre la formula è sbagliata).
allora butto qui la formula nel caso particolare di 30 carte con 3 semi (10 carte per ciascun seme).

$sum_(k=1)^10\{1/3*((3k-3),(k-1))*((2k-2),(k-1))*(((10)_(k-1))^3)/((30)_(3k-3))+sum_(j=k)^(k+9)\[((3k-3),(j))*(10-j)/(33-3k)* sum_(r=0)^j\((3k-3-j),(r))*((10)_j*(10)_r*(10)_(3k-3-j-r))/((30)_(3k-3))+$
$+((3k-2),(j))*(10-j)/(32-3k)*sum_(r=0)^j\((3k-2-j),(r))*((10)_j*(10)_r*(10)_(3k-2-j-r))/((30)_(3k-2))+((3k-1),(j))*(10-j)/(31-3k)*sum_(r=0)^j\((3k-1-j),(r))*((10)_j*(10)_r*(10)_(3k-1-j-r))/((30)_(3k-1)) ]}$

fatemi sapere. ciao e grazie.

adaBTTLS1
a questo punto butto giù anche l'altra, quella che dovrebbe rispondere alla domanda originaria del topic, con 40 carte e 4 semi:

EDIT: nel fare copia-incolla e nel ricorreggere poi, qualche $3$ non è diventato $4$ come avrebbe dovuto. ricorreggo:

$sum_(k=1)^10\{1/4*((4k-4),(k-1))*((3k-3),(k-1))*((2k-2),(k-1))*(((10)_(k-1))^4)/((40)_(4k-4))+$
$+sum_(j=k)^(k+9)\[((4k-4),(j))*(10-j)/(44-4k)* sum_(r,s=0)^j\((4k-4-j),(r)) *((4k-4-j-r),(s))*((10)_j*(10)_r *(10)_s*(10)_(4k-4-j-r-s))/((40)_(4k-4))+$
$+ ((4k-3),(j))*(10-j)/(43-4k)* sum_(r,s=0)^j\((4k-3-j),(r))* ((4k-3-j-r),(s))* ((10)_j*(10)_r*(10) _s*(10)_(4k-3-j-r-s))/((40)_(4k-3))+$
$+((4k-2),(j))*(10-j)/(42-4k)*sum_(r,s=0)^j\((4k-2-j),(r))* ((4k-2-j-r),(s))* ((10)_j*(10)_r*(10)_s*(10)_(4k-2-j-r-s))/((40)_(4k-2))+$
$+((4k-1),(j))*(10-j)/(41-4k)*sum_(r,s=0)^j\((4k-1-j),(r))* ((4k-1-j-r),(s))* ((10)_j*(10)_ s*(10)_ (4k-1-j-r-s))/((40)_(4k-1)) ]}$

ho trasformato la formula con i fattoriali, per simularla con Excel, ma non è molto agevole, e temo che senza i fattoriali decrescenti mi darebbe problemi, eventualmente dovrei "eliminare a mano" i termini che dovrebbero essere nulli.

Rggb1
Mi sono interessato allo sviluppo di Martino, ma non ho abbandonato altre strade (e sto ancora cercando di capire perché questo @#*! programma mi fornisce un risultato differente...)

@adaBTTLS
Hai calcolato quanto viene il risultato?

adaBTTLS1
no, cercavo appunto un supporto "informatico".
ho rimesso a posto la formula, e sto provando a simularla con Excel, però non confido molto di riuscirci.

Rggb1
Dopo un (bel) po' di prove e debug, sono finalmente venuto a capo del problema con l'algoritmo di simulazione; notare a tal proposito il cambio di avatar. ;)

Era come sospettavo un errore dovuto alla "distribuzione delle carte" non proprio casuale. Fra l'altro questo mi spinge a considerazioni interessanti in merito ai generatori pseudorandom (e al modo che ho usato per evitare il problema trovato), magari per una prossima puntata - dopo gli esami :-D

La simulazione con 40 carte e 4 semi fornisce un valore appossimato in linea a quello calcolato in precedenza (da DajeForte afair) ovvero $m=14.65$. Ora possiamo cercare di trovare una formula generale?

@adaBTTLS
Appena ho tempo cercherò di calcolare la tua formula. PS. la notazione $(n)_m$ indica il prodotto da $n$ per $m$ fattori, giusto?

adaBTTLS1
è il fattoriale decrescente: $m$ fattori a decrescere, partendo da $n$, cioè $(n)_m=n*(n-1)*...*(n-m+1)$
ti dico che l'uso di questo simbolo mi semplifica molto le cose, perché la "comparsa" del fattore "zero" mi fa annullare tutti i termini che non dovrebbero esserci.
però con Excel non l'ho trovata, ho modificato la formula per poterla simulare, ho risolto il problema per $j$ ma sono bloccata per $r,s$.

gugo82
"adaBTTLS":
è il fattoriale decrescente: $m$ fattori a decrescere, partendo da $n$, cioè $(n)_m=n*(n-1)*...*(n-m+1)$

In altri termini:

[tex]$(n)_m=\frac{n!}{(n-m)!} =m!\ \binom{n}{m}$[/tex]...

Ma è una notazione usata spesso o l'hai inventata tu per l'occasione?

adaBTTLS1
il significato è quello. è una notazione che si usa quotidianamente nel calcolo combinatorio.

gugo82
"adaBTTLS":
è una notazione che si usa quotidianamente nel calcolo combinatorio.

Ah ecco. Non essendo pratico di CC non l'avevo mai vista.
Grazie.

Rispondi
Per rispondere a questa discussione devi prima effettuare il login.