No es un problema estándar (a menudo me asignar en álgebra lineal, y me fue asignado el problema en teoría de la representación); parece que podría estar relacionado.
Supongamos que usted ha $n$ personas que se sientan en una mesa circular, cada uno de ellos con dos vecinos. Cada uno de ellos tiene una taza de avena en frente de ellos, y una cuchara en cada mano. Descontentos con sus porciones individuales, todos ellos simultáneamente agarrar la mitad de la papilla de su vecina a mano izquierda, la mitad de la papilla de la vecina a mano derecha, y la puso en su tazón de fuente (que ha sido vaciado por sus vecinos haciendo lo mismo). ¿Qué sucede con la distribución de la papilla a lo largo del tiempo?
Edit: Más explícito, aplicado a las tarjetas. Por lo tanto, vamos a considerar el caso de los tres comedores/shufflers. Supongo que por comodidad, ahora que las cartas están, como Morón sugiere, "líquido"; vamos a volver a la discreta caso en la actualidad. Deje $x_i(n)$ el número de tarjetas que el $i$th persona tiene después de$n$, $\mathbf{x}(0) = (a_0,b_0,c_0)$ la distribución inicial de las tarjetas (por lo $a_0,b_0,c_0\geq 0$). A continuación, el procedimiento puede ser representado como
$$\begin{array}{rcrcrcl}
x_1(n+1) &=& & &\frac{1}{2}x_2(n) & + & \frac{1}{2}x_3(n)\\
x_2(n+1) & = & \frac{1}{2}x_1(n) & & &+& \frac{1}{2}x_3(n)\\
x_3(n+1) & = & \frac{1}{2}x_1(n) & + & \frac{1}{2}x_2(n)
\end{array}$$
Así podemos ver esto como el sistema lineal $\mathbf{x}(n+1) = A\mathbf{x}(n)$, donde
$$A = \left(\begin{array}{lll}
0 & 0.5 & 0.5\\
0.5 & 0 & 0.5\\
0.5 & 0.5 & 0
\end{array}\right).$$
El polinomio característico de a$A$$-t(t-0.5)^2$. Desde las filas suman a $1$, $(1,1,1)^T$ es un autovector de a $\lambda=1$ (es decir, si todo el mundo empieza con $1$, después de aplicar el procedimiento que todos terminan de nuevo con $1$: $(1,1,1)^T$ se asigna a uno veces sí). Una base para el subespacio propio correspondiente a$\lambda=-\frac{1}{2}$$(1,-1,0)^T$$(1,0,-1)^T$. Si, por ejemplo, el jugador que comenzó con una tarjeta de jugador y dos con una "anti-card" (tarjeta de antimateria, por ejemplo), a continuación, después de que el primer paso, el jugador consiguió la mitad de una tarjeta de 1 y la mitad de un anti-tarjeta de 2, que desapareció en una nube de humo; el jugador 2 tiene ahora la mitad de una tarjeta que tiene de 1, y el jugador 1 tiene la mitad de un anti-tarjeta de 2. Por lo $(1,-1,0)^T$ se asigna a $(-\frac{1}{2},\frac{1}{2},0)$. De igual manera, con $(1,0,-1)$.
Ahora, debido a $(1,1,1), (1,-1,0), (1,0,-1)$ es una base para $\mathbb{R}^3$, nuestra distribución original $\mathbf{x}(0)$ puede escribirse de forma única como
\[ \mathbf{x}(0) = a(1,1,1) + b(1,-1,0) + c(1,0,-1),\]
para algunos $a$, $b$, y $c$. Tenga en cuenta que el número de las tarjetas entre los tres jugadores es $3a$. Si aplicamos el procedimiento de $n$ veces para obtener $\mathbf{x}(n)$, obtendremos:
\begin{align*}
\mathbf{x}(n) &= A^n\mathbf{x}(0)\\
&= A^n(a(1,1,1)^T + b(1,-1,0)^T + c(1,0,-1)^T)\\
&= (a,a,a)^T + (-0.5)^n(b,-b,0)^T + (-0.5)^n(c,0,-c)^T\\
&= (a + (-0.5)^n(b+c), a-(0.5)^nb, a-(0.5)^nc)^T.
\end{align*}
Ahora, en realidad estamos interesados en el suelo de estas cantidades (ya que realmente estamos tratando con tarjetas actuales, no negativo y fraccionario de tarjetas). Tan pronto como $(0.5)^nb$ $(0.5)^nc$ son tanto más pequeño que $\frac{1}{4}$, la distribución será fundamentalmente la distribución uniforme de la $(a,a,a)$.
Para un ejemplo claro: supongamos que empezamos con el Jugador 1 habiendo $30$ tarjetas, Reproductor de $2$ $16$ naipes, el jugador $3$ $22$ tarjetas (he escogido los números al azar). En primer lugar, escribimos $(30,16,22)$ como una combinación lineal de $(1,1,1)$, $(1,-1,0)$, y $(1,0,-1)$. Resolver el sistema correspondiente, se obtiene:
$$(30,16,22) = \frac{68}{3}(1,1,1) + \frac{20}{3}(1,-1,0) + \frac{2}{3}(1,0,-1).$$
Así que después de $n$ aplicaciones del procedimiento, vamos a tener
$$
\mathbf{x}(n) = \frac{68}{3}(1,1,1) + \frac{(-1)^n20}{3(2^n)}(1,-1,0) + \frac{(-1)^n2}{3(2^n)}(1,0,-1).$$
Por lo que cada jugador tendrá exactamente un tercio de las tarjetas, modificado por un poco.
Si $n=2$, entonces el coeficiente de $(1,-1,0)$ $1.67$ y el coeficiente de $(1,0,-1)$$0.167$; por lo que sería de esperar que el primer jugador en el entero más cercano a $\frac{68}{3}+1.67$ tarjetas, es decir, acerca de la $24$; en el segundo jugador debe tener el entero más cercano a $\frac{68}{3} -1.67$ tarjetas, por lo que alrededor de $21$ tarjetas; y el tercer jugador al entero más cercano a $\frac{68}{3}-0.167$ tarjetas; esto es casi el $22.5$, por lo que tendrás $23$ tarjetas (para completar el conteo).
Si $n=3$, se obtiene acerca de $22$ tarjetas para el primer jugador, $23$ para el segundo, $23$ para el tercero). Si $n=4$, el primer jugador debe tener aproximadamente $23$ tarjetas; el segundo jugador debe tener aproximadamente $22$ tarjetas; y el tercer jugador debe tener aproximadamente $23$ tarjetas. Después de este punto, usted acaba de estar arrastrando los pies alrededor de que es una tarjeta de corto.
Un fenómeno similar ocurre con cualquier número impar de personas. Esto puede no ser el más rápido procedimiento para la división entre un número impar de jugadores, aunque.
Si intenta hacer esto con $n=4$ de la gente, entonces la matriz que se obtiene es:
$$ A = \left(\begin{array}{llll}
0 & 0.5 & 0 & 0.5\\
0.5 & 0 & 0.5 & 0\\
0 & 0.5 & 0 & 0.5\\
0.5 & 0 & 0.5 & 0
\end{array}\right).$$
Esta vez, el polinomio característico es $t^2(t-1)(t+1)$, por lo que tiene un autovalor $\lambda=1$ (con el correspondiente autovector $(1,1,1,1)$, lo que se asocia a "las cartas están distribuidas de manera uniforme"), se puede obtener un autovalor $\lambda=-1$, con el correspondiente autovector $(1,-1,1,-1)$; y se obtienen dos vectores propios de asignación a $0$; por ejemplo,$(0,1,0,-1)$$(1,0,-1,0)$.
Una vez que usted expresa su distribución original como una combinación lineal de estas,
\[ (x_1(0),x_2(0),x_3(0),x_4(0)) = \alpha(1,1,1,1) + \beta(1,-1,1,-1) + \gamma(0,1,0,-1) + \delta(1,0,-1,0),\]
los dos últimos componentes no importa después de la primera vez, por lo que terminan con
\[ \mathbf{x}(n) = \bigl( \alpha + (-1)^n\beta \alpha - (-1)^n\beta \alpha+(-1)^n\beta \alpha-(-1)^n\beta\bigr).\]
Así que según usted va a tener una cierta porción de las tarjetas distribuidas uniformemente (correspondiente a $\alpha$), y una cierta parte de las cartas (correspondiente a $\beta$) de intercambio entre incluso - y el número impar de jugadores en cada paso.
Edit: Otra forma de mirar el $n=4$ caso: Una mejor manera de ver lo que está sucediendo en este caso es reemplazar el vector $(1,-1,1,-1)$ con el vector $(2,0,2,0)$ (la suma del vector propio y $(1,1,1,1)$); todavía tenemos una base, así que podemos escribir cualquier distribución inicial como
$$(x_1(0),x_2(0),x_3(0),x_4(0)) = \alpha(1,1,1,1) + \beta(2,0,2,0) + \gamma(0,1,0,-1)$ + \delta(1,0,-1,0).$$
Pero ahora, cuando se aplica $A$, el vector $(2,0,2,0)$ se transforma en el vector $(0,2,0,2)$, y este vector es a su vez transformado de nuevo en un $(2,0,2,0)$. El número total de tarjetas es $4(\alpha+\beta)$. De estos, $4\alpha$ de las tarjetas se acaban distribuidos entre los jugadores, pero el resto de $4\beta$ tarjetas terminarán se distribuye equitativamente entre los dos no adyacentes a los jugadores, y luego cambió a los otros dos jugadores, luego cambió de nuevo. Si usted se imagina que estás en un puente tabla, en primer lugar la asociación Norte-Sur tiene el extra de $4\beta$ tarjetas, $2\beta$ cartas cada uno, van a la Este-Oeste, luego de nuevo hacia el Norte-Sur, y luego de vuelta ot Este-Oeste, etc.
Un fenómeno similar ocurre con cualquier número de jugadores.
Agregado: de Vuelta a la discreta caso. Bien, por encima de que estamos tratando con el "líquido tarjetas"/"gachas", donde las cartas son divisibles cualquier forma que desee. ¿Qué sucede si estamos jugando tarjetas actuales que no queremos dividir? Observe que cada jugador sólo está obligado a dividir sus cartas en la mitad; por lo que el único problema que se plantea si un jugador tiene un número impar de cartas. En ese caso, el jugador sólo tiene que dar la tarjeta adicional a cualquiera de sus vecinos que más le gusta, o al azar; la distribución final en este caso es muy cercana a la ideal "continuo" de distribución: cada uno de sus vecinos se supone que para obtener $x$-y-un-medio de tarjetas de él, pero tengo bien $x$ o $x+1$; así que la mayoría de los que una persona puede estar fuera de la "ideal", resultado de aplicar el procedimiento es $1$ tarjeta (la mitad de una tarjeta de un vecino, la mitad de una tarjeta a la otra). Este vector será bastante cerca de la "ideal" continua vector, y así, el resultado de aplicar el procedimiento para esta distribución también dará lugar a una distribución que es bastante cerca de lo que la distribución ideal. (Lineal mapas son continuos, y en este caso los valores propios son todos de valor absoluto menor o igual a $1$, por lo que la aproximación no va a empeorar a medida que pasa el tiempo; ya sea siendo el mismo, o mejoran). Usted puede ver esto en el ejemplo que he elaborado para $n=3$. Si usted comienza con $(30,16,22)$, después de que el primer paso que usted consigue $(19,26,23)$; en el siguiente paso, el "predijo" la distribución es $(24,21,23)$. La distribución real de obtener son $(24,22,22)$, $(25,21,22)$, $(24,21,23)$, o $(25,20,23)$, dependiendo de cómo las tarjetas adicionales se distribuyen. El sup-distancia a la predicción de la distribución es de 1 en todos los casos. Hacerlo una tercera vez, y dependiendo de cómo las cosas se rompen, terminará en cualquiera de los dos $(22,24,22)$, $(21,24,23)$, $(22,23,23)$, $(21,23,24)$, $(23,23,22)$, o $(21,25,22)$. El "peor" de distribución (la última) es mejor que la peor distribución en el paso anterior. Y así sucesivamente.
En resumen: el "dar la mitad de sus cartas a cada uno de sus vecinos y conseguir que la mitad de cada una de sus cartas" dará lugar a una distribución uniforme después de una bastante pequeña-ish número de pasos si hay un número impar de jugadores, pero no necesariamente el rendimiento y la distribución uniforme, si hay un número par de jugadores. En el último caso, parte de la cubierta se consigue distribuidas de manera uniforme, mientras que la otra parte termina intercambio entre los "equipos". Una de las ventajas de este, al menos por un número impar de jugadores, es que es un procedimiento que se repite un número de veces (como en el fusileros-barajar un mazo) con el fin de lograr la uniformidad, en lugar de un algoritmo complejo que implica diferentes acciones en diferentes pasos.
