¿Qué es matemáticamente significativa sobre este algoritmo?

Question

En esta pregunta, un cierto algoritmo fue presentado:

Empezar con una cubierta de $n$ tarjetas.

1. Tome la carta y la puso sobre la mesa en la parte superior de alguna de las tarjetas que ya existe

2. Mover la nueva tarjeta superior a la parte inferior de la cubierta

3. Vaya al paso 1 si todavía quedan cartas en el mazo. Cuando no hay más cartas en la baraja, una ronda que ha pasado

4. Recoger las cartas de la mesa; esta es la nueva cubierta. Si la nueva cubierta es en el orden original, hemos terminado. De lo contrario, repita el procedimiento desde el paso 1.

Como muestro en mi respuesta a esa pregunta, hay algunas peculiaridades.

1. Potencias de dos ir a través de unas rondas antes de que las cartas están en el orden original. Por ejemplo, mientras que los números en torno a $64$ $60+$ rondas antes de regresar a su estado original, $64$ sólo toma $12$ rondas. Parece que cada poder de otros dos de dos resultados en $4m$ rondas donde $m\in\Bbb N$.
2. Números primos ir a través de un número inusualmente elevado de rondas. Por ejemplo, mientras que los números en torno a $31$ todos toman menos de $100$ rondas, $31$ es de $210$ rondas.
3. Sin duda hay otras propiedades interesantes de este algoritmo

Lo que es significativo acerca de este algoritmo que hace que los números primos y los poderes de los dos para tener peculiar de salida?

---

En respuesta a Victor Engel comentario, aquí es una prueba de que el algoritmo devolverá siempre de la cubierta para el caso de partida:

1. Sabemos que cada ronda es un uno-a-uno con función de una cubierta de ordenar a otro de la cubierta de los pedidos (esta debe ser clara en la manera en que está establecido; es reversible).
2. Sabemos que hay un número finito de la cubierta ordenamientos.

Se supone que hay un caso en el que el algoritmo no volver a la partida de orden.

$\implies$ En ese caso, hay un número infinito de órdenes, o hay un bucle en algún lugar en la secuencia.

Pero sabemos que hay un número finito de orden (ver 2.).

$\implies$ hay un bucle en algún lugar en la secuencia.
$\implies$ o se retrocede a la partida de pedido o de los bucles de otro orden en la secuencia.

Pero sabemos que no es un volver a la partida de pedidos debido a que contradice nuestra suposición de que no es así.

Por lo tanto, la secuencia de los bucles de otro orden en la secuencia.

$$\implies\Longleftarrow$$

Esta es una contradicción. En el orden de la secuencia de bucle a otro orden en la secuencia, la función tendría que ser el no uno-a-uno, porque dos de los elementos en el dominio de mapa para el mismo elemento en el rango.

$\therefore$ Llegamos a la conclusión de que las aplicaciones repetidas en el algoritmo siempre conduce de nuevo al caso original.

^{_{Como una nota del lado, esta misma prueba en obras para demostrar que la aplicación repetida de un determinado algoritmo en un rubix cubos siempre lleva de nuevo a la original rubix cube}}

Answer 1

Respuesta parcial: Aquí está potencias de dos:

Vamos a investigar las primeras potencias de dos. Vamos a la izquierda-a-derecha el fin de denotar la parte superior a la parte inferior de permutación de las tarjetas. Aquí va:

$\{ a_1, a_2\} \rightarrow \{a_2, a_1\}$

$\{a_1, a_2, a_3, a_4\} \rightarrow \{a_4, a_2, a_3, a_1\}$

$\{a_1, a_2, a_3, a_4, a_5, a_6, a_7, a_8\} \rightarrow \{a_8, a_4, a_6, a_2, a_7, a_5, a_3, a_1\}$

En este último caso, hay un par de cosas:

Primer ciclo: $1 \rightarrow 8 \rightarrow 1$

Segundo ciclo: $2 \rightarrow 4 \rightarrow 2$

Tercer ciclo: $3 \rightarrow 7 \rightarrow 5 \rightarrow 6 \rightarrow 3$

Así que para encontrar el número de ciclos requeridos, encontrar el MCM de las duraciones del ciclo.

Esta es la manera de hacer sentido de la forma: Si leemos de derecha a izquierda, primero tenemos que hacer con las probabilidades en un orden creciente, y, a continuación, nuestro conjunto de $2^n$ tarjetas se reduce a un conjunto de $2^{n-1}$ tarjetas en forma de $\{2, 4, 6, \dots, 2^n\}$. Entonces, las "probabilidades" de este conjunto (congruente a $2 \pmod 4$) son recogidos a cabo, dándonos $2^{n-1}$ tarjetas en la forma $\{4, 8, 12, \dots, 2^n\}$. A continuación, $4 \pmod 8$ son recogidos a cabo en orden creciente y así sucesivamente hasta que se agoten de tarjetas. Todavía no estoy seguro si podemos hacer de una forma cerrada de generalización para cualquier $2^n$ tarjetas (aunque es evidente que la primera y la última de las tarjetas se cambian de lugar).

Otro ejemplo:

$\{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16\} \rightarrow \{16, 8, 12, 4, 14, 10, 6, 2, 15, 13, 11, 9, 7, 5, 3, 1\}$

$1 \to 16$

$2 \to 8$

$3 \to 15 \to 9 \to 12$

$4 \to 4$

$11 \to 11$

$5 \to 14$

$6 \to 7 \to 13 \to 10$

De nuevo, el número de ciclos serían $4$.

En un mazo de $2^n$ tarjetas, los números de $2^{n-1}$ $2$ intercambiar posiciones, así como los números de $2^n$$1$.

Algunos ejemplos de números primos:

$\{1, 2, 3, 4, 5, 6, 7\} \rightarrow \{6, 2, 4, 7, 5, 3, 1\}$

Que da la permutación $(17436)$

$\{1, 2, 3, 4, 5, 6, 7, 8, 9, A, B\} \rightarrow \{6, A, 2, 8, 4, B, 9, 7, 5, 3, 1\}$

(Por el bien de ciclo de notación estoy usando $A = 10, B = 11$)

Que da la permutación $(1B6)(23A)(45978)$, por lo que el número requerido de ciclos serían $3 \times 5 = 15$

Answer 2

Sólo algunos elementos que podrían ayudar a una mejor comprensión.

Como notado ya, si tenemos $n$ tarjetas de una ronda corresponden a una permutación de $n$ elementos. Tratamos de entender esta permutación, y en particular, queremos saber el orden de esta permutación (es decir, el número de veces que se debe repetir esta permutación para obtener el orden original). Podemos escribir una permuations en 2 diferentes maneras. $$\{1,2,3,4,5,6,7,8\}\rightarrow\{8,4,6,2,7,5,3,1\} $$ o $$(1,8)(2,4)(3,6,5,7).$$ La última representación de medios, $1$ $8$ swap, $2$ $4$ swap, $3$ se convierte en $6$, $6$ se convierte en $5$, $5$ vuelve $7$ $7$ hace $3$. La llamamos cíclico de la representación. El orden de la permutación es el más mínimo común múltiplo de la longitud de los círculos.

Sobre el caso de una potencia de dos: Podemos probar por inducción que para todo $n$, $$\{1,\ldots,2^n\}\rightarrow\{2^n;2^{n-1};2^{n-2}.3,2^{n-2}.1;\ldots;2^{n-k}.(2^k-1),2^{n-k}.(2^k-3),\ldots,2^{n-k}.3,2^{n-k}.1;\ldots;2^n-1,2^n-3,\ldots,5,3,1\}.$$ Observe el uso de punto y coma $;$ aquí es sólo para subrayar algunos grupos especiales de números de longitud $1$, $1$, $2$,...,$2^{k-1}$,...,$2^{n-1}$.

Con esta descripción, se puede ver que para cualquier $k\leq n$, $2^k$ y $2^{n-k}$ swap. Más en general, podemos ver que para cualquier $k\leq n$ y cualquier $l$ tal que $2l+1\leq 2^{n-k}$, $2^{n-k}-l$ hace $2^k(2l+1)$, pero yo no averiguar cómo podría ayudar.

En el siguiente doy la representación cíclica de las permutaciones cuando tenemos $2^n$ tarjetas, para $1\leq n\leq 7$:

1. $(1,2)$
2. $(1,4)$
3. $(1,8)(2,4)(3,6,5,7)$
4. $(1,16)(2,8)(3,12,9,15)(5,14)(6,10,13,7)$
5. $(1,32)(2,16)(3,24,17,31)(4,8)(5,28,9,30)(6,20,25,15)(7,12,18,29)(10,26,13,14)(11,22,21,23,19,27)$
6. $(1,64)(2,32)(3,48,33,63)(4,16)(5,56,17,62)(6,40,49,31)(7,24,34,61)(9,60)(10,52,25,30)(11,44,41,47,35,59)(12,36,57,15)(13,28,18,58)(14,20,50,29)(19,54,21,46,37,55)(22,42,45,39,51,27)(23,38,53)$
7. $(1,128)(2,64)(3,96,65,127)(4,32)(5,112,33,126)(6,80,97,63)(7,48,66,125)(8,16)(9,120,17,124)(10,104,49,62)(11,88,81,95,67,123)(12,72,113,31)(13,56,34,122)(14,40,98,61)(15,24,68,121)(18,116,25,60)(19,108,41,94,69,119)(20,100,57,30)(21,92,73,111,35,118)(22,84,89,79,99,59)(23,76,105,47,70,117)(26,52,50,58)(27,44,82,93,71,115)(28,36,114,29)(37,110)(38,106,45,78,101,55)(39,102,53,46,74,109)(42,90,77,103,51,54)(43,86,85,87,83,91,75,107)$

Editar Voy a añadir aquí algunos grphique obtenidos con mathematica. En los dos siguiente imagen podemos observar la irregularidad de la orden de la permutación cuando el número de tarjetas varía. La primera foto muestra los pedidos cuando tenemos hasta el $100$ tarjetas. El segundo show de la misma cosa a $2000$ tarjetas.

Por otro lado en el siguiente diagrama se parecen mostrar algún tipo de regularidad de la orden cuando consideramos $2^k$ tarjetas (con $1\leq k\leq 16$).

Más precisamente, aquí está el valor de $o_k$ de la orden de la permutación cuando consideramos $2^k$ tarjetas de:

• $o_1=o_2=2$
• $o_3=o_4=4=2^2=2o_2$
• $o_5=o_6=12=2^2.3=3o_4$
• $o_7=o_8=24=2^3.3=2o_6$
• $o_9=o_{10}=o_{11}=o_{12}=120=2^3.3.5=5o_8$
• $o_{13}=o_{14}=840=2^3.3.5.7=7o_{12}$
• $o_{15}=o_{16}=1680=2^4.3.5.7=2o_{14}$
• $o_{17}=o_{18}=5040=2^4.3^2.5.7=3o_{16}$

Parece que tenemos $o_{2l+1}=o_{2l}$ y que se dividen $o_{2k+2}$. Tal vez esto es comprobable por inducción pero no he encontrado todavía.