¿La matemática de barajar las fichas de póker?

Question

En primer lugar, debo decir que no tengo conocimientos avanzados de matemáticas y no sé a qué categoría pertenece esta pregunta. Se trata simplemente de una pregunta en la que he estado pensando recientemente.

He estado enseñándome a barajar fichas de póker y he notado una tendencia extraña. Decidí modelarlo en C# y no sólo no conseguí responder a mi pregunta, sino que cada vez parecía tener menos sentido para mí.

Así que, básicamente, esto es lo que hice. Elegí un cierto número de fichas, junto con un cierto número de colores, para ver cuántas barajadas se necesitan para volver a la forma inicial. Los barajados son los mismos barajados simples que todo el mundo ve en una mesa de póquer. Las fichas están todas agrupadas por colores al principio y la condición a satisfacer es volver a esta posición inicial.

Lo hice para fichas que van del 1 al 20, y colores que van del 1 al 11. Estos son los datos que he generado: http://i.imgur.com/ykG3BvO.png

He mirado este documento: http://scott-n.com/Archives/Docs/Mathematical%20Trends%20in%20Binary%20Chipshuffling.pdf

Se trata de un breve documento que pretende detallar algunas de las tendencias que existen cuando se utilizan sólo 2 colores.

¿Puede alguien aclararme el tema? A primera vista parece relativamente sencillo, pero cuanto más lo investigo, más difícil resulta.

Answer 1

Al igual que el comentario de azimut: Tampoco entiendo tu configuración para más de dos colores. Sin embargo para dos colores hay una respuesta.

La respuesta para dos colores

Digamos que tenemos $n$ fichas (en total, no por color) y queremos encontrar el número de barajadas necesarias que llamamos $k$ .

Hay dos formas diferentes de barajar las fichas: barajar hacia dentro y barajar hacia fuera, dependiendo de la forma en que se barajen las fichas:

In-shuffle:
RRRRBBBB => BRBRBRBR

Out-shuffle:
RRRRBBBB => RBRBRBRB

Básicamente, al hacer una baraja de salida, las fichas más externas nunca cambian de posición, y así $outShuffle(k) = inShuffle(k-2)$ . Para lo que sigue, supondré que estamos hablando de barajar y cantar

El número de barajadas es el menor número entero positivo $k$ para que $(n+1)$ divide $(2^k-1)$ . También se puede escribir como el menor número entero positivo $k$ para que $2^k\equiv1 \mod (n+1)$ Esto es lo mismo que el orden multiplicativo de $2 \mod (n+1)$ .

Explicación

Esta cuestión puede explicarse con la teoría de grupos de permutación. Desgraciadamente, no puedo darte una explicación real, ni una prueba, pero puedo darte una idea de cómo se puede explicar la fórmula que he dado arriba.

Un caso fácil: 8 fichas

Numeremos la pila de fichas de $1$ a $n$

12345678
RRRRBBBB

y veamos entonces qué pasa con la ficha en posición $1$ a lo largo del tiempo. Después de una barajada, obtenemos la siguiente imagen:

12345678
BRBRBRBR

La ficha de la posición $1$ está ahora en posición $2$ . Otra barajada más tarde, está en posición $4$ y luego en la posición $8$ antes de volver a la posición $1$ . Así que tenemos el ciclo $ 1\rightarrow 2\rightarrow 4\rightarrow 8\rightarrow 1$ de longitud $4$ .

Sin embargo, no sólo el chip de la posición $1$ seguir este ciclo. Las 4 fichas de este ciclo sólo rotan su lugar, lo que significa que después de 4 barajadas, todas vuelven a su lugar original. Lo mismo ocurre con las otras 4 fichas, en otro ciclo.

En consecuencia, después de 4 barajadas, se recupera la posición original.

Más complicado: 10 fichas

Comprobemos ahora lo que ocurre con la primera ficha, cuando hay 10 fichas en total. Obtenemos la siguiente permutación: $ 1\rightarrow 2\rightarrow 4\rightarrow 8\rightarrow 5\rightarrow 10\rightarrow 9\rightarrow 7\rightarrow 3\rightarrow 6\rightarrow 1$ .

La secuencia tiene una longitud de 10, por lo que se necesitan 10 barajadas para restaurar la configuración original. La cuestión es, sin embargo, cuál es la estructura matemática que hay detrás de esta secuencia.

Si se examina esta secuencia más detenidamente, se descubre que la fórmula para llegar a la siguiente posición es $(pos*2)\mod11$ . En general, esta fórmula es $(pos*2)\mod(n+1)$ .

Caso general

El $k$ La posición de una ficha se puede calcular duplicándola $k$ veces, mientras se calcula el módulo $(n+1)$ . El $k$ La posición de la primera ficha es la siguiente $2^k\mod(n+1)$ . Si y sólo si esto es $1$ el primer chip ha vuelto a su posición después de $k$ baraja.

Aunque esto no es en absoluto una prueba completa, puedes ver que esto podría llevar a que el número buscado sea el más pequeño $k>0$ para lo cual $2^k\equiv1\mod(n+1)$ .

Lo que falta

• ¿Por qué no puede haber un ciclo más largo que el que comienza en la posición $1$ ?
• ¿Por qué no hay una situación en la que los colores de las fichas son correctos, incluso sin que las fichas vuelvan a su posición original?

Ver también

• A002326: Orden multiplicativo de 2 mod 2n+1 (aquí $n$ es el número de fichas de un color Por lo tanto $2n+1$ no $n+1$ )
• Hilo del foro xkcd sobre este tema

Answer 2

Si cada barajada reordena las fichas de la misma manera, y todas las fichas son diferentes, esto no es más que repetir una permutación (multiplicándola por sí misma), por lo que (por teoría elemental de grupos) la configuración inicial sí se repite eventualmente. Si se dividen las fichas en grupos indistintos (colores), las configuraciones que son "iguales" al punto de partida son más, y tal vez se acierte antes con una de ellas.

Si la baraja reordena las fichas de diferentes maneras, se trata de un paseo aleatorio sobre las posibles configuraciones. Una interesante, pero lejos de un problema fácil, es calcular el tiempo medio de las repeticiones.