Il baro e la mischiata americana

[Alemin]

Luca si avvicina a una bancarella dove legge il cartello "scegli 1 carta tra 52, se la indovino mi devi 10€ se non la indovino vinci 100€!"
Luca, attratto dalla vincita, tenta la fortuna;
il baro mostra le carte 52 non truccate e davanti i suoi occhi le mischia x volte con questo procedimento (chiamato riffle shuffle o metodo americano) :
Divide il mazzo in due parti uguali;
Il mazzo inferiore lo tiene nella sinistra il mazzo superiore lo tiene nella destra;
A turno partendo dal mazzo a sinistra pone sul tavolo la ultima carta, sopra di essa mette l'ultima del mazzo di destra, poi ancora l'ultima di sinistra... e cosi via fino a quando ottiene di nuovo un solo mazzo.

Il trucco sta nel fatto che il baro conosce l'ordine iniziale e mischiando x volte con quel metodo riconduce il mazzo al mazzo iniziale.
Richieste:
a)Quanto vale x (ammesso che il trucco funzioni)?
b)è possibile ottenere una formula generale per calcolare x se le carte fossero n, con n pari?
c) e se n fosse dispari?

Esempio con 6 carte per chiarirsi le idee (spero):

Testo nascosto, fai click qui per vederlo

Ordine iniziale dall'alto:
654321
Prima separazione:
Sx:321 Dx:654
Prima mischiata:
635241
Seconda separazione:
Sx:241 Dx:635
Seconda mischiata:
623451
Terza separazione:
Sx:451 Dx:623
Terza mischiata:
642531
Quarta separazione:
Sx:531 Dx:642
Quarta mischiata:
654321
Con 4 mischiate si ottiene la serie iniziale

Buon divertimento

[Settevoltesette]

inserisco la mia brutta soluzione, magari qualcuno ne trova una meno calcolosa

Testo nascosto, fai click qui per vederlo

a) X = 50
b) NO, ma posso dire che X = k se 2n = 2^k , X = 2k*h (con h da calcolare caso per caso) se 2n = 2^k +2 , X = 2n - 2 altrimenti.
c) non si potrebbero spaiare, al più se 3 carte rimangono ferme X sarebbe lo stesso di 2n se le carte sono 2n+1

se 2n = 2^k si ha fissata per esempio la carta n.°2 che al primo passo si sposta di 1 al secondo di 2 al terzo di 4...
al k-1-esimo di 2^(k-1) ma dato che all'inizio si trova al secondo posto al k-1-esimo passaggio si ferma al posto n+1, ed allora al k-esimo torna in posizione iniziale. Quindi le permutazioni devono essere multiple di k.
So che la prima e l'ultima carta sono fisse, devo avere allora che gli altri fattori devono essere congrui a 2^k - 2 modulo k. Per il piccolo teorema di Fermat (a^p = a mod p) è congruo 0 modulo k, allora il minimo numero di passaggi è proprio k.

se 2n = 2^k +2 allora fissata la prima e l'ultima carta le rimanenti sono 2^k ed ancora una volta con lo stesso procedimento ho che la n.°2 torna in posizione iniziale al 2k-esimo passaggio, questa volta ho considerato solo 2^k carte, quindi la n.°2 si trova al primo posto e dopo k permutazioni si trova all'ultimo posto, dato che la regola di mischiare è simmetrica per tornare al primo mi servono il doppio delle permutazioni. Quindi il numero di permutazioni cercate è multiplo di 2k.
Questa volta 2^k = x mod 2k quindi posso dire che è multiplo di 2k, ma non posso essere più preciso.

altrimenti se 2n non è ne del tipo 2^k o 2^k +2 ho che non posso avere scorciatoie dunque la nostra carta n.°2 farà il giro di tutte le 2n-2 carte.

[billyballo2123]

Ciao Settevoltesette! Volevo chiederti se il "NO" che rispondi nel punto b) deriva dal fatto che non hai trovato la formula o se hai la dimostrazione che tale formula non può esistere.
Ciao ciao

[Settevoltesette]

se trovi tutte le soluzioni x al variare di k di 2^k = x mod 2k hai la formula risolutiva per ogni k (se tutto quello che ho fatto è giusto).

[billyballo2123]

Testo nascosto, fai click qui per vederlo

a) X = 50
b) NO, ma posso dire che X = k se 2n = 2^k , X = 2k*h (con h da calcolare caso per caso) se 2n = 2^k +2 , X = 2n - 2 altrimenti.

Non Mi torna... con $52$ carte in realtà bastano $8$ mischiate.
Concordo che $x = k$ se $n = 2^k$.
Se $n = 2^k+2$, allora $x = 2k$ (che è quello che hai scritto te ponendo però $h = 1$.
Per tutti gli altri casi non si ha che $x = n - 2$ (tranne che in casi eccezionali).

Riporto alcuni valori che ho trovato (nel senso che un computer ha trovato per me ):
\[
\begin{matrix}
n & x \\
2 & 1 \\
4 & 2 \\
6 & 4 \\
8 & 3 \\
10 & 6 \\
12 & 10 \\
14 & 12 \\
16 & 4 \\
18 & 8 \\
20 & 18 \\
22 & 6 \\
24 & 11 \\
26 & 20
\end{matrix}
\]

[Settevoltesette]

Non Mi torna... con $52$ carte in realtà bastano $8$ mischiate.

è un po' che ho mollato questo gioco, ma mi sembrano un po' poche, quando ho tempo ci riprovo per convincermene.

Se $n = 2^k+2$, allora $x = 2k$ (che è quello che hai scritto te ponendo però $h = 1$).

dovresti dimostrare che h = 1 costante, io feci un po' di tentativi e da un certo punto in poi h variava, in pratica la prima carta considerata torna in posizione iniziale ma le altre non sono ancora tutte in posizione iniziale "c'è un prodotto di permutazioni" e non è detto che abbiano tutte fattori comuni, potrei aver sbagliato, ma comunque non hai dimostrato che si ha h = 1.

Per tutti gli altri casi non si ha che $x = n - 2$ (tranne che in casi eccezionali).

in effetti questo è il punto che non ho dimostrato, ma che ho buttato li

P.s.
Ho appena fatto una prova con un mazzo di carte, hai ragione sul primo punto, con 52 carte bastano 8 mischiate.