Esercizi di Calcolo Combinatorio con le Carte

Problema 1

Sia dato un mazzo di \(52\) carte da poker disposte in un ordine qualsiasi. Quante mischiate devono essere fatte prima che il mazzo ritorni nell’ordine iniziale? Le mischiate devono essere fatte soltanto nel seguente modo: dividere il mazzo in due gruppi uguali di \(26\) carte; quindi muovere alternativamente ogni carta dei due gruppi nel nuovo mazzo, a partire dalla prima carta del secondo gruppo( posizione \(27\)), seguita dalla prima carta del primo gruppo (posizione \(1\)) e così via.

Soluzione
Ricordiamo il teorema di Fermat che ci sarà utile per la dimostrazione: dato un intero positivo \(a\) e un numero primo \(p\) tali che \((a,p)=1\), vale la seguente formula:

\[ a^{p-1}\equiv 1 \pmod{p} \]

Veniamo ora al problema. In base alla regola per le mischiate possiamo dire che se una carta occupa la posizione \(k\) con \(1 \le k \le 52\), dopo una mischiata la nuova posizione \(h\) è \(2k\) se \(1 \le k \le 26\) oppure la posizione \(2k-53\) se \(27 \le k \le 52\). Possiamo unificare in una unica formula \( h \equiv 2k \pmod {53}\), come è facile verificare. Dopo \(n\) mischiate la carta che inizialmente stava nella posizione \(k\) si troverà nella posizione \(h \equiv 2^{n}k \pmod {53}\).
Per il nostro problema bisogna quindi risolvere la seguente congruenza:

\[ 2^{n}x \equiv x \pmod{53} \]

Poiché \((2,53)=1\) possiamo cancellare la \(x\), ottenendo l’equazione \( 2^{n} \equiv 1 \pmod{53}\). Possiamo ora utilizzare il teorema di Fermat il quale afferma che \( 2^{52} \equiv 1 \pmod{53}\), poiché \(53\) è un numero primo. Quindi il mazzo di carte tornerà nell’ordine iniziale dopo \(52\) mischiate.
Ci si può chiedere se \(52\) è il numero minimo, oppure è possibile che il mazzo possa tornare nell’ordine iniziale con un numero di mischiate inferiore. Si può dimostrare che \(52\) effettivamente è il numero più piccolo per il quale risulta verificata la congruenza. In teoria dei numeri si dice che \(2\) è una radice primitiva di \(53\). Per uno studio dell’argomento vedere un libro di Teoria dei Numeri, ad esempio ^[1]. Per il calcolo delle radici primitive di un numero vedere WolframAlpha.

Esercizio 1.1
Calcolare il numero minimo di mischiate necessario nel caso di un mazzo di 30 carte.

Notare che \(2\) non è una radice primitiva di 31.

Risposta: 5 mischiate.

---

Problema 2

Dato un mazzo di \(n\) carte numerate da \(1\) a \(n\), in un ordine qualsiasi. Prendiamo la prima carta e muoviamola nella posizione corrispondente al suo numero. Ripetiamo questa procedura fino a che tutte le carte sono nella posizione giusta.

Ad esempio se partiamo dall’ordine iniziale 32154, abbiamo la seguente sequenza: 32154->21354 -> 12354 ->12345.

Esercizio 2.1
Supponiamo di partire con questo ordine delle carte: 2,3,4,…..,(n-1),n,1. Dimostrare che dopo \(2^{n-2}-1\) mosse, le carte saranno nell’ordine \(n,2,3,  \cdots , n-1,1\).

Suggerimento
Dimostrare per induzione. L’affermazione è chiaramente vera per \(n=2\) e per \(n=3\). Supposta vera per un \(n\) generico, dimostrare che è vera anche per \(n+1\).

Esempio 2.1
Partiamo dall’ordine iniziale 234561. Abbiamo la seguente sequenza di 15 passi: 234561->324561->243561->423561->235461->325461->253461->523461->234651->324651->243651->423651->236451->326451->263451->623451

Esercizio 2.2
Dimostrare che partendo dall’ordine iniziale \(2,3, \dots ,n,1\), sono necessarie \(2^{n-1}-1\) mosse per portare all’ordine \(1,2, \cdots ,n-1,n\).

Dimostrazione
In base all’esercizio precedente sono necessarie \(2^{n-2} -1\) mosse per arrivare all’ordine \(n,2,3,  \cdots , n-1,1\). Con un’ulteriore mossa si arriva all’ordine \( 2,3,  \cdots , n-1,1,n\). A partire da questa con \(2^{n-3}\) mosse arriviamo all’ordine \(2,3,  \cdots , 1,n-1,n\). Procedendo in questo modo possiamo concludere il numero di mosse \(N\) necessario per arrivare all’ordine finale è:

\[ N=2^{n-2} +2^{n-3} + \cdots + 2^{1} + 2^{0}=2^{n-1}-1 \]

Esempio 2.2
Mettere in ordine la stringa iniziale \(23451\) mediante \(15=2^{5-1}-1\) mosse.

Soluzione
Abbiamo la seguente sequenza di mosse: 23451->32451->24351->42351->23541->32541->25341->52341->23415->32415->24315->42315->23145->32145->21345->12345.

---

Problema 3

Sia dato un mazzo di \(t\) carte in totale, alcune rosse altre nere. Si sceglie una carta per volta; un giocatore scommette sul colore prima dell’estrazione. La strategia del giocatore è di scegliere sempre il colore che rappresenta la maggioranza delle carte presenti nella scatola. Se c’è lo stesso numero di carte sceglie un colore o l’altro con la stessa probabilità. Calcolare il numero atteso di risposte esatte.

Ricordiamo prima alcuni concetti di Probabilità:

Definizione 3.1
Sia \(X\) una variabile aleatoria che può assumere i valori \(\{x_{1},x_{2}, \cdots ,x_{n}\}\) con probabilità \(\{p(x_{1}),p(x_{2}), \cdots ,p(x_{n}) \}\). Si definisce valore atteso o media di \(X\) il numero

\[ E(X) = \sum_{k=1}^{n} x_{k}p(x_{k}) \]

Per calcolare il valore atteso di una variabile aleatoria bisogna determinare i valori che la variabile può assumere e, per ognuno di questi, calcolare la probabilità relativa.

Esempio 3.1
Una variabile aleatoria di Bernoulli assume solo due valori \(1,0\) con probabilità \(p,q\). Determinare il valore atteso.

Risposta: \(E(X)=p\).

Esempio 3.2
Calcolare il valore atteso nel lancio di un dado.

Risposta: \(\left( \frac{21}{6} \right)\).

Teorema 3.1
Data una variabile aleatoria discreta \(X\), che assume i valori \(\{x_{1}, \cdots ,x_{n}\}\) con probabilità \(\{p(x_{1}),p(x_{2}), \cdots ,p(x_{n}) \}\). Allora se \(Y\) è un’altra variabile aleatoria, il valore atteso di \(Y\) è dato dalla seguente espressione:

\[ E(Y) = \sum_{k=1}^{n} E(Y|X=x_{k})p(x_{k}) \]

dove il simbolo \(E(Y|X=x_{k})\) indica il valore atteso di \(Y\) sotto la condizione che la variabile \(X\) assume il valore \(x_{k}\). Questa formula viene anche chiamata legge delle probabilità totali.
Per un ripasso del calcolo delle probabilità vedere ^[2], oppure ^[3].

Tornando al problema, supponiamo che \(r\) e \(n\) siano i numeri delle carte rosse e nere. Naturalmente \(r+n=t\). Indichiamo con \(N(r,n)\) il numero atteso di risposte giuste.
Notiamo che \(N(r,n)=N(n,r)\) per motivi di simmetria. Inoltre è chiaro che \(N(r,0)=r\).
Il primo luogo osserviamo che se \(r=n > 0\), abbiamo la seguente relazione:

\[ N(r,r) = N(r,r-1) + \frac{1}{2} \]

Se invece \(r > n > 0\) applicando il principio delle probabilità totali abbiamo questa equazione di ricorrenza:

\[ N(r,n) = \frac{n}{r+n}N(r,n-1) + \frac{r}{r+n}N(r-1,n) + \frac{r}{r+n} \]

Esercizio 3.1
A partire dalle formule precedenti dimostrare la seguente formula:

\[ N(r,n) = r + \frac{1}{\binom{r+n}{n}} \sum_{i=0}^{n-1}\binom{r+n}{i} \]

Questa relazione si dimostra per induzione, supponendola vera per tutti gli argomenti la cui somma è minore di \(r+n\).

Esercizio 3.2
A partire dalla formula precedente dimostrare che, nel caso \(r=n\), risulta:

\[ N(r,r)=r – \frac{1}{2}+ \frac{2^{2r-1}}{\binom{2r}{r}} \]

Suggerimento
Ricordare le proprietà dei coefficienti binomiali e utilizzare la seguente formula:

\[ \sum_{i=0}^{n}\binom{n}{i} = 2^{n} \]

---

Problema 4

Calcolare la probabilità di trovare una coppia di assi vicini, mischiando in modo casuale un mazzo di carte da \(40\).

Soluzione
Il numero totale dei possibili ordinamenti di \(40\) carte è \(40!\). Poiché ci sono \(4\) assi, abbiamo \(\binom{40}{4}\) possibili modi in cui questi \(4\) assi possono essere posizionati nel mazzo.
Calcoliamo prima la probabilità che non ci siano assi adiacenti. Se partiamo da un mazzo di \(36\) carte, senza gli assi, il primo dei 4 assi ha 37 possibili posizioni di inserimento, contando anche le posizioni estreme; il secondo 36, il terzo 35 e il quarto 34. Quindi il numero di casi possibili senza assi adiacenti è:

\[ \frac{37 \cdot 36 \cdot 35 \cdot 34}{4!} =\binom{37}{4} \]

La probabilità che non ci siano assi adiacenti è quindi:

\[ q= \frac{\binom{37}{4}} {\binom{40}{4}} \]

Infine la probabilità che ci siano 2 assi adiacenti è:

\[ p= 1- q= 1 – \frac{\binom{37}{4}} {\binom{40}{4}} \]

---

Bibliografia

^[1]W. LeVeque – Fundamentals of Number Theory (Addison-Wesley)

^[2]S. Ross – A First Course in Probability (Pearson)

^[3]Murray Spiegel – Probabilità e Statistica (McGraw-Hill)