¿Cuántas aleaciones perfectas se necesitan para volver al estado inicial?

Question

El otro día, en un popular libro de ciencias vi:

Dada 32 cartas ( $c_i$ $i=0..31$ ), cortar la baraja en dos partes y pasarlos a la Americana (fusileros arrastrando los pies). La cubierta ahora se ve así: $c_0, c_{16}, c_1, c_{17}, \dots, c_{15}, c_{31}$.

El hecho es que, mediante la repetición de este shuffle 5 veces en total, usted va a volver a la inicial estado ordenado de la cubierta. Algunos de cerca de los magos pueden usar este resultado para pretender tener un azar que baraja.

Descubrí que es muy fresco, pero, de alguna manera, tenía que probar. Buscando una simple ejemplo como punto de partida tengo que para un 4-tarjeta-de la cubierta, es fácil ver que sólo se necesitan dos baraja: $$(c_0,c_1,c_2,c_3)\rightarrow(c_0,c_2,c_1,c_3)\rightarrow(c_0,c_1,c_2,c_3)$$

La versión generalizada que se me ocurrió es lo que yo quiero probar: Para $2^n$ tarjetas, usted necesita $n$ baraja para volver al estado inicial.

La recursividad?

Quería hacerlo por recursión, y me quedé atrapado bastante pronto. La única útil (espero) con la herramienta que he encontrado es un algebric representación de la mezcla. Si el estado actual de la cubierta es de ( $c_i$ $i=0..2^n$ ), a continuación, después de revolver se convertirá en ( $c_{f(i)}$ $i=0..2^n$ ), con: $$f(i) = 2^{n-1} i + \left\lfloor\frac{i}{2}\right\rfloor \pmod{2^n}$$

Con esta herramienta, yo "sólo" tienen que demostrar $\forall i, f^n(i) = f\circ f \circ \dots \circ f(i) = i$.

¿Alguien me puede ayudar a demostrar este teorema?

---

Y, como se ha sugerido, sería estupendo para demostrar que este es el mínimo número de veces que sea necesario.

Edit: ha habido un montón de trabajo en las referencias de esta secuencia. Este es el tipo de caso (no sólo $2^n$ tarjetas). Creo que esta es una buena cosa a tener en cuenta.

Answer 1

Su herramienta es casi correcto. La idea es trabajar con la inversa de shuffle. Es decir $(c_0,c_1,c_2,c_3,c_4,c_5,c_6,c_7)\rightarrow(c_0,c_2,c_4,c_6,c_1,c_3,c_5,c_7)$.

La última tarjeta de $c_{2^n-1}$ nunca mueva. Para el resto de tarjetas, usted puede encontrar la fórmula de recursión $f^{-1}(i)=2i \pmod{(2^n-1)}$. Así tenemos

$$\begin{align} (f^{-1})^n(i) & =2^ni & \pmod{(2^n-1)}\\ &=(2^n-1)\times i+i&\pmod{(2^n-1)}\\ &=i&\pmod{(2^n-1)} \end{align}$$

Así, se comprobó la inversa de shuffle! (Y, consecuentemente, para la inicial shuffle $f$).

Ahora a ver que $n$ es el orden de $f^{-1}$ y no es un divisor de a $n$ podemos observar cómo el grupo cíclico generado por $f^{-1}$ actúa sobre los números de $(1,\ldots,2^n-1)$. Las órbitas tienen todos el tamaño de un divisor de a $n$. Ahora a demostrar que no es en realidad una órbita de orden $n$ se nota que este es el caso de la órbita de $1$. De hecho, tenemos que esta órbita es $1,2,2^2,\dots, 2^{n-1}$. Estos son todos los $< 2^n-1$, por lo que todos los diferentes modulo $(2^n-1)$ y no son exactamente $n$ de ellos.

Answer 2

Deje que las posiciones de las tarjetas será dado por $i\in\{0\}\cup[2^n-1]$.

Definir una invertible mapa de $x:\{0\}\cup[2^n-1]\rightarrow [0,1]$ por $$x(i)=\frac{i}{2^n-1}.$$

Ahora usted puede mostrar que donde $\sigma$ es el rifle shuffle, que

$$\sigma(i)=x^{-1}(D(x(i)))\Rightarrow \sigma^N(i)=x^{-1}(D^N(x(i))),$$

donde $D:[0,1]\rightarrow [0,1]$ es la Duplicación de la Asignación de $$D(x)=2x\mod 1.$$

Tenga en cuenta que

$$x(i)=\frac{i}{2^n-1}=\frac{2^{-n}i}{1-2^{-n}}=\sum_{k=0}^\infty2^{-n}i(2^{-n})^k,$$ es recurrente en binario, de modo que

$$x(i)=(0.\overline{a_1a_2\dots a_n})_2,$$

donde $\displaystyle(0.a_1a_2\dots a_n)_2=\frac{i}{2^n}$.

Es fácil mostrar que

$$D((0.b_1b_2\dots b_n)_2)=(0.b_2b_3\dots b_n)_2.$$

Ahora, si usted tiene todo que usted tiene

$$D^n(x(i))=x(i),$$

debido a la naturaleza recurrente de $x(i)$. Por lo tanto tendríamos

$$\sigma^n(i)=x^{-1}(x(i))=i,$$ para todos los $i\in\{0\}\cup [2^n-1]$ y que sería un hecho.

Creo que la órbita-estabilizador teorema de $G=\langle\sigma\rangle$ actuando en $X=\{0\}\cup[2^{n}-1]$ mostrará que $n$ es un mínimo... mirando los puntos fijos de $D^n$... Por ejemplo, $x=(0.\overline{100\cdots001})_2$. Esto sólo tiene un estabilizador --- $\sigma^n$ pero $n$ elementos en la órbita de modo que $|G|=|\text{orb}(x)||\text{stab}(x)|=n\cdot 1=n$, de modo que $\text{o}(\sigma)=n$.

Answer 3

Esto tiene una respuesta con referencias en http://mathworld.wolfram.com/Out-Shuffle.html