El Campamento De Día De Juego De Apilamiento

Question

Mi amigo trabaja en un campamento de día como consejero y él me dijo acerca de un interesante juego juega con su grupo de niños.

Usted tiene un perfectamente mezclados, regular $52$cartas de la baraja y un grupo de $2 \leq n < 52$ de los niños bajo su supervisión. Se pide a los niños a sentarse en círculo y distribuir al azar una tarjeta a cada uno de ellos. Por lo tanto, cada individuo recibe, ya sea rojo o negro de la tarjeta (dependiendo de la demanda) que se adhieren en su frente para que todos la vean. El consejero luego se sienta en el centro del círculo y pasa a través de los restantes $52-n$ cartas de la parte superior a la parte inferior de la cubierta y mostrar cada tarjeta para el grupo. Las reglas son como sigue:

1. A cada niño se le asigna un presidente para iniciar el juego. Esta silla puede ser vacantes u ocupados durante el juego y no se puede mover.
2. Si una roja (resp. negro) de la tarjeta se muestra, cada niño con un color rojo (resp. negro) tarjeta se sienta en la silla a su izquierda. Si alguien ya está en la silla, el niño se sienta sobre él/ella.
3. Si un niño tiene a alguien por encima de él/ella, él/ella no puede moverse cuando su color se dibuja, es decir, sólo los niños en la parte superior de una pila se puede mover.

Si dos niños tienen el mismo color y este color se dibuja, giran (shift) en el sentido horario $1$, $e.g.$ si $n=4$, y los colores se $RRBR$ y el rojo se dibuja, a continuación, la nueva configuración se $R \sharp (BR) R$ donde $(BR)$ significa negro niño en rojo chico y $\sharp$ denota un asiento vacío. Es posible que ningún niño se mueve en una tarjeta. El juego termina cuando no hay más cartas en la baraja. Todo el mundo gana en este juego, al igual que cualquier campamento de día de juego.

He encontrado este juego muy fascinante debido a su estructura matemática subyacente. Esto da lugar a profundos problemas matemáticos que actualmente estoy tratando de entender.

Supongamos que el juego no se detiene cuando el mazo de cartas está vacía, pero en lugar de después de algunos múltiple (llamado giro) de las cartas restantes se muestran, es decir, después de $(52-n)m$ tarjetas se muestran algunos de los $m$. Deseo analizar dos casos, a saber, el ciclismo , aunque la cubierta después de cada turno o a barajar el mazo después de cada turno. Por el ciclismo, me refiero a que la primera tarjeta que se muestra en la primera vuelta es la primera tarjeta que se muestra en la segunda vuelta y así sucesivamente.

1. En el caso del ciclismo, ¿cuál es la probabilidad de que, en algún momento en el juego, todos los $n$ de los niños se apilan en la parte superior de uno al otro?
2. ¿Qué acerca arrastrando los pies?
3. En ambos casos, lo que sucede cuando dejamos $m \to \infty$?

Sé muy poco acerca de las probabilidades, y no digamos la combinatoria, pero siento que estas preguntas pueden ser difíciles de responder. Este problema podría incluso ser indecidible. El juego algo me recuerda a la de un "ordenado" de la versión de la Torre de Hanoi con reglas adicionales, que yo sé cómo resolver, pero no puedo ver cómo podría ser útil en la situación actual. Una cosa que he notado es que en cualquiera de los casos, la pila completa $-$ si es que alguna vez sucede $-$ se alternan en el color como un corolario de la regla 2.

Yo tenía algunas ideas, por ejemplo considerando un gráfico con los cargos en cada vértice y con la realización de un apilamiento como un borde de la contracción y la transferencia de carga, pero esto parece demasiado complicado.

¿Cómo usted va sobre este problema? Cualquier ayuda sería muy apreciada.

Answer 1

Yo soy uno de los amigos mencionados en la pregunta!

Aquí están mis ideas aún. Voy a editar este post, como puedo conseguir más profundo en la resolución, o si encuentro otras ideas. Sólo voy a ser capaz de trabajar en esto en el lado durante el tiempo libre.

Uno de los enfoques que reducen la primera parte de el problema a un número finito tarea de cálculo, sería encontrar el número de resultados que producen una coloración del círculo de los niños a través de la órbita-estabilizador de la fórmula para el diedro grupo equipado con 2 colores de vértice, es decir, justo como nos gustaría resolver el collar problema con 2 colores de coloración para $k=2$ $k=n$ vértice.

Cada una de esas configuraciones (resultados) se asocia a un fácil de calcular la probabilidad. Entonces, la probabilidad de sacar una negra o una tarjeta roja también es fácilmente calculada con respecto a un determinado resultado.

Ahora mismo estaríamos a la izquierda con la formalización de el estado de las pilas. Yo no tengo ninguna idea clara sobre cómo se puede ir sobre hacer eso todavía.

Observar a pesar de que, dado que la única manera de que una pila puede ocurrir es por una secuencia $BRBRBRB...$ o $RBRBRBRB...$, es fácil ver que ninguna configuración en la que $|b-r|>2$, donde $b=$$B$% y $r=$$R$% puede obtener una pila compuesta de todos los niños... Si pudiéramos caracterizar los casos de $b=r$ $|b-r|=1$ en una manera similar, en el caso de que $m\rightarrow \infty$ con baraja estaría resuelto.