In una notte molto buia, quando il frigo è vuoto, non avete amici per uscire, il vostro lui/lei è partito, avete risolto tutti gli IMO 6 di tutti gli anni e non sapete cosa fare (oddio non ricordo se la frase di EvaristeG era proprio così ), pensate a questo nuovo solitario:
- si ha un mazzo da 40 carte
- si mischiano
- sia $a_i$ il valore della $i$-esima carta. Se $\exists i: a_i \equiv i \pmod {10}$, allora avete perso (quest'orrido formalismo dice che se al primo passaggio trovate 1 oppure al secondo 2, ..., oppure all'undicesimo 1, .... avete perso.
Poi vi chiedete anche la probabilità di riuscire a questo gioco. Qual è il valore di codesta probabilità?
Dilemma che mi sono sempre posto e che ho provato a risolvere l'inverno scorso in montagna provando di generalizzare un gioco simile dove però basta che l' $ i $ esima carta non sia proprio la carta $ i $ (carte numerate da uno a quaranta e si conta fino a quaranta)... Purtroppo non ebbi successo... Ora la sfida mi chiama di nuovo
$ \mbox{ }\mbox{ } $And God said : $ \displaystyle c^2 \mu_0 \varepsilon_0 =1 $,
and then there was light.
Riformuliamo il problema in modo più generale in termini di permutazioni.
Voglio trovare il numero di permutazioni \(\sigma\) (che indichiamo con \(\#\sigma\) ) dell'insieme \(A=\{1, \ldots, mk\}\) tale che \(\sigma(i) \not \equiv i \pmod{m}, \ \forall i \in \{1, \ldots, mk\}\). Inoltre definiamo \(Q=\{0, \ldots, k-1\}\) e \(R=\{0, \ldots, m-1\}\).
Si definisce \(n\)-dismutazione \(D\) una permutazione di \(\{1, \ldots, n\}\) tale che \(D(i) \not = i, \ \forall i \in \{1, \ldots, n\}\). Indichiamo con \(D_n\) il numero di \(n\)-dismutazioni. Vogliamo dimostrare che la soluzione del nostro problema è \((k!)^m \cdot (D_m)^k\).
"Spezziamo" la nostra permutazione in due "fasi" differenti, ossia la interpretiamo come \(\sigma(qm+r) = \sigma_1(q)m+\sigma_2(r)\).
Visto che \(\sigma_1, \sigma_2\) sono indipendenti, si avrà \(\#\sigma = \#\sigma_1 \cdot \#\sigma_2\) (con ovvia interpretazione del cancelletto per \(\sigma_{1,2}\) ).
FASE 1: \(\#\sigma_1 = (k!)^m\). Il vincolo di cui dobbiamo tener conto è che le permutazioni sono bigettive, quindi se ho \(q_1m+r\) e \(q_2m+r\), i resti andranno nello stesso \(\sigma_2(r)\), e perciò devo scegliere \(\sigma_1\) in modo che \(\sigma_1(q_1) \not = \sigma_1(q_2)\).
Perciò devo fare in modo che \(\sigma_1\) sia una permutazione di \(Q\); se infatti capitasse \(\sigma_1(q_1) = \sigma_2(q_2)\) con \(q_1 \not = q_2\), avrei che \(\sigma(q_1m+r) = \sigma_1(q_1)m+\sigma_2(r) = \sigma_1(q_2)m+\sigma_2(r) = \sigma(q_2m+r)\) con \(q_1m+r \not = q_2m+r\), il che è assurdo perchè significa che \(\sigma\) non è una permutazione.
Quanti sono i modi di permutare \(Q\)? \(k!\). Per quanti resti devo permutare \(Q\)? \(m\). Perciò ho \(\#\sigma_1 = (k!)^m\).
FASE 2: \(\#\sigma_2 = (D_m)^k\). Il vincolo \(\sigma(qm+r) \not \equiv qm+r \pmod{m}\) è equivalente a \(\sigma_2(r) \not \equiv r \pmod{m}\),
ossia \(\sigma_2\) è una dismutazione di \(R\).
Quanti sono i modi di dismutare \(R\)? \(D_m\). Per quanti quozienti devo dismutare \(R\)? \(k\). Perciò ho \(\#\sigma_2 = (D_m)^k\).
Per quanto riguarda la probabilità \(P\) del problema, ho, usando \(D_m \sim m! /e\):
\(\displaystyle P = \frac{\#\sigma}{(mk)!} = \frac{(k!)^m (D_m)^k}{(mk)!} \sim \frac{(k!)^m (m!)^k}{(mk)! e^k}\)
che per \(m=10, k=4\) dà, in pasto a wolfram alpha, \(2,46 \cdot 10^{-10}\). Mi sembra un po' piccolo. Inizio a sospettare di aver sbagliato tutto.
), pensate a questo nuovo solitario:
