Mischiando il mazzo

[jordan]

Siano $1\le K\le N$ degli interi. Dato un mazzo di $N$ carte, prendiamo le $K$ carte in cima al mazzo, invertiamo l'ordine di queste ultime, e mettiamole sotto il mazzo. Ripetiamo questo procedimento parecchie volte. Dimostrare che dopo al massimo $(2N/K)^2$ operazioni torniamo con il mazzo ordinato come all'inizio.

(Baltic Way 2005/6)

[Sir Yussen]

Invertire sarebbe far assumere all'i-esima carta la $K-i+1$-esima posizione? (in $\mathbb{Z}K$ ovviamente)

[jordan]

In $\mathbb{Z}/K\mathbb{Z}$ direi semplicemente $i$ o $-i$

Edit: "invertire" significare prendere le carte $\{1,2,\ldots,K\}$ e riordinarle come $\{K,K-1,\ldots,1\}$.

[nic.h.97]

Ho diviso in 2 casi , solo che nn riesco a completarne 1.

1)per $ K|N $ abbiamo che si formano $ N/K $ gruppi di carte .
Definiamo$ N=a_1;a_2;...a_n $
$ g_1=a_1;a_2;...a_k $
$ g_2=a_{k+1};....a_{2k} $
e cosi' via fino ad arrivare a $ g_{N/K} $.
Dopo $ g_{N/K} $ , abbiamo $ g_{N/K+1} $ e $ g_{N/K+1} $ è uguale insiemisticamente a $ g_1 $ .
Quindi possiamo dire che si formano $ N/K $ gruppi costanti , ovvero tengono sempre le stesse carte.
Dopo $ N/K $ mosse invertiamo innanzitutto l'ordine dei gruppi.
e inoltre invertiamo anche gli elementi all'interno di ciascun gruppo.
Con altre $ N/K $ mosse , reinvertiamo nuovamente l'ordine dei gruppi , riottenendo quello iniziale e inoltre invertiamo anche l'ordine degli elementi all'interno dei gruppi ottenendo cos' la configurazione iniziale. Quindi dopo$ N/K + N/K $ mosse riotteniamo la configurazione iniziale
2) se N e K sono coprimi.
Qua ho notato delle cose, ma non ho completato.
Qua , diversamente dal punto 1 , abbiamo che i gruppi non rimangono costanti .
Dopo$ [N/K] $ mosse tolgo delle $ x $ carte ad un gruppo e gli rimetto le sue stesse $ x $ carte dopo altre $ [N/K] $ mosse.
Allora , posso comunque dire che ho dei gruppi di carte comunque uguali.

Ovvero $ g_1=g_{[2N/K]} $ e cosi' via anche per gli altri.
Se analizziamo dei gruppi che hanno gli stessi elementi , noto che dopo $ [2N/K] $ mosse inverto prima l'ordine degli elementi , dopo altre $ [2N/K] $ mosse
(ovvero dopo che gli elementi tornano gli stessi , perchè dopo $ [2N/K] $ mosse riottengo lo stesso gruppo).
***) prendo i primi $ v $ elementi ( dove $ a $ è il piu' piccolo naturale tale che $ N=km+a $ , per il massimo $ m $naturale )
li inverto questi $ v $ elementi e li rimetto giu' (nel gruppo).
dopo altre $ [2N/K] $ mosse reinverto nuovamente e dopo altre $ [2N/K] $ mosse ripeto il passaggio ***) fino ad ottenere la configurazione del mazzo iniziale.
Arrivato qua mi manca una cosa : non riesco a trovare una relazione per calcolare in quante mosse rimettere apposto un singolo gruppo

[jordan]

Il primo punto è ovviamente giusto; il secondo no: $\text{gcd}(K,N)=1$ non esaurisce tutti i casi, manca $2\le \text{gcd}(K,N) \le K-1$; poi, come viene definita la sequenza degli $g_i$ visto che $K \nmid N$?

[Gottinger95]

Ci provo. Sia \(\{ 0, \ldots, N-1 \} \) le carte del mazzo e sia \(N-1 = Qk + R\) la sua divisione euclidea per \(k\). La permutazione secondo cui viene mischiato il mazzo è

\(\sigma(i) = \begin{cases} \sigma_1(i) = (N-1)-i & 0 \leq i \leq k-1 \\ \sigma_2(i) = i-k & k \leq i \leq N-1 \end{cases} \)

Cerchiamo di decomporre la permutazione in cicli disgiunti per calcolare il periodo come \(m.c.m.\) dei periodi dei cicli.

Passo 1. Modulo \(k\), la permutazione \(\sigma_1(i)\) ha al massimo periodo 2, mentre \(\sigma_2(i)\) ha periodo 1. Infatti \(\sigma_1(i) =(N-1 - i) \equiv R-i \pmod k \). Se \(R-i \equiv i \pmod k \), ossia \(R \equiv 2i \pmod k \), la permutazione ha periodo 1, altrimenti ha periodo 2.

Passo 2. " L'andamento" della permutazione, partendo da un elemento minore di \(k\), è il seguente:

\(i \xrightarrow{\sigma_1} N-1 -i \xrightarrow{\sigma^{j_1}_2} R+(k)-i \xrightarrow{\sigma_1} N-1 - R +(-k) +i \xrightarrow{\sigma^{j_2}_2} i \)

dove i \((\pm k )\) sono da considerarsi presenti sse \( R < i \), e \(j_1, j_2\) sono i quozienti rispettivamente di \(N-1 -i\) e \( N-1 - R +(-k)+ i\) divisi per \(k\).

Calcoliamo \(j_1, j_2\) sottraendo ai dividendi i resti e dividendo per \(k\):

\(\displaystyle j_1 = \frac{(N-1 -i) - (R+(k)-i ) } {k } = \frac{(Qk -i-(k)+i ) } {k } = Q-(1) \)
\(\displaystyle j_2 = \frac{(N-1 - R +(-k)+i) - i } {k } = \frac{ Qk+(-k)+i-i} {k} = Q+(-1) \)

Perciò sse \(R \geq i \) allora \( j_1 = j_2 = Q \), altrimenti sse \(R < i \) allora \( j_1 = j_2 = Q-1 \).

Passo 3. I cicli suddetti passano per tutti i numeri: infatti il ciclo di un numero qualsiasi \(r\) con \(0 \leq r \leq k-1 \) passa per tutti numeri che hanno resto \(r \pmod k\), perchè la permutazione parte dal numero con resto \(r\) più alto (\( N-1 - R +(-k) +r\) ) al più basso ( \( r \) ) .
Dunque, indicando con \(P(r)\) il periodo del ciclo che parte da \(0 \leq r \leq k-1 \), abbiamo:

\(P(r) =
\begin{cases}
j_1 + j_2 + 2 = 2(Q-1) + 2 = 2Q & R < i \\
j_1 + j_2 + 2 = 2Q+2 & R \geq i \\
j_1 + 1 = Q + (-1) + 1 = Q + (+1) & R \equiv 2i \pmod k
\end{cases} \)

Consideriamo il minimo comune multiplo tra questi tre possibili casi:

\(\displaystyle P_{\sigma} = gcd(2Q, 2Q+2, Q + (+1) ) = gcd(2Q, 2Q+2) = 2Q(Q+1) = 2Q^2 + 2Q \)

che è sempre minore di \((2N/k)^2 \). Infatti abbiamo (con un puntone interrogativo sulla disuguaglianza):

\(2Q^2 + 2Q \leq (2N/k)^2\)
\(2Q^2 + 2Q \leq 4(Q+ (R/k))^2 \)
\(2Q^2 + 2Q \leq 4Q^2 + (8RQ/k) + (4R^2/k^2) \)
\( 2Q - 2Q^2 \leq 4R(2Qk + R) \)

Dallo studio della quadratica nell l'LHS notiamo che essa può assumere nell'intervallo \(Q \geq 1 \) al massimo il valore 0, e l'RHS può assumere al minimo il valore 0. Con questo si conclude la dimostrazione.

Edit. C'è un errore nel m.c.m, che potrebbe essere \(2(Q+1)\) se \(Q \mid Q+1 \), ossia \(Q=1\).

[jordan]

Bene, le idee ci sono tutte Questa è la mia