Considere el siguiente juego de cartas (conocido en Italia como "Cavacamicia", que se puede traducir como "camisa de rayas"):

Dos jugadores dividen aleatoriamente en dos mazos un mazo de cartas estándar. Cada jugador tiene un mazo.

Los jugadores alternan colocando en una pila la siguiente carta de su mazo.

Si un jugador (A) coloca una carta especial, es decir, una I, II o III, el otro jugador (B) tiene que colocar consecutivamente el número correspondiente de cartas.

• Si al hacerlo, B coloca una carta especial, la acción se invierte, y así sucesivamente; de lo contrario, si B coloca el número correspondiente de cartas pero no una carta especial, A recoge todas las cartas que se dejaron y las agrega a su mazo. A luego reinicia el juego colocando una carta.

El primer jugador que se quede sin cartas pierde el juego.

Nota: El resultado del juego depende exclusivamente de la partición inicial del mazo. (Lo que puede hacer que este juego parezca un poco inútil ;-)

Pregunta: ¿Este juego siempre termina? ¿Qué pasa si generalizamos este juego y le damos dos secuencias de cartas a cada jugador?

Con respecto a Mendigo-mi-vecino

Paulhus (1, p.164) escribió en 1999:

$C$${D_{2}}^{'}(C)$

Pero Conway et al. (2, p.892) escribió en 2006:

Strip-Jack-Naked o Beggar-My-Neighbor ** 1

Otro problema que tardó casi 47 años en resolverse se refiere a este viejo juego infantil. Cada uno de los dos jugadores comienza con aproximadamente la mitad de las cartas (mantenidas boca abajo), que alternativamente dan vuelta en una "pila" boca arriba en la mesa, hasta que una de ellas (que ahora es "el comandante") primero reparte una de las "cartas de mando" (Jack, Queen, King o Ace).

Después de que uno de estos ha sido repartido, el otro jugador (ahora "el respondedor") da vuelta a las cartas continuamente hasta que CUALQUIERA. ** 2 aparece una nueva carta de mando (cuando los jugadores cambian de roles ** 3) o se han entregado respectivamente 1, 2, 3 o 4 cartas de no mando. En el último caso, el comandante da vuelta la pila y la coloca en el fondo de su mano. El respondedor luego comienza la formación de una nueva pila al voltear su próxima carta, y el juego continúa como antes.

Un jugador que adquiere todas las cartas es el ganador y en los juegos reales, parece que alguien siempre gana. La interesante pregunta matemática, planteada por uno de nosotros hace muchos años, fue "¿es realmente cierto que el juego siempre termina?" Marc Paulhus ha encontrado recientemente que la respuesta es "¡no!". Aproximadamente 1 de cada 150,000 juegos (jugados con las 52 cartas habituales) continúa para siempre.

Estamos bastante seguros de que ninguna persona ha jugado el juego en ese número de veces, por lo que la posibilidad (con barajadura aleatoria) de experimentar un juego sin fin en la vida debe ser muy pequeña.

Sin embargo, con la misma seguridad, el número total de veces que este juego ha sido jugado por los niños ** 4 del mundo debe ser significativamente mayor que 150,000, por lo que muchos de ellos habrán sido teóricamente no finales. Sin embargo, imaginamos que, en la práctica, la mayoría de ellos terminaron porque alguien cometió un error.

Desafortunadamente no pude encontrar en (2) ninguna referencia al descubrimiento de Paulhus ... Me encantaría ver una secuencia de cartas que proporcione un juego sin fin para decir que el problema está resuelto.

En 2013, Lakshtanov y Aleksenko (3) escribieron:

Para los juegos de cartas del tipo Beggar-My-Neighbor, demostramos la finitud de la expectativa matemática de la duración del juego en las condiciones en que un jugador para jugar la primera carta se elige al azar y que las cartas en una pila se barajan antes de colocarlas en el cubierta. El resultado también es válido para modificaciones de tipo general de las reglas del juego. En otras palabras, mostramos que la gráfica de la cadena de Markov para el juego Beggar-My-Neighbor es absorbente; es decir, desde cualquier vértice hay al menos un camino que conduce al final del juego.

pero sus reglas no son las que seguí cuando jugué el juego cuando era niño ;-)

Que yo sepa, el juego más largo de Beggar-my-Neighbor fue encontrado en 2014 por William Rucklidge con 7960 cartas :

1: -J------Q------AAA-----QQ-
2: K----JA-----------KQ-K-JJK

Sobre Cavacamicia

Por lo general, jugué con un mazo de 40 cartas, las simulaciones con un mazo medio (solo 20 cartas) dan 16 juegos sin terminar en un total de 3.448.400 juegos.

Bibliografía

(1) PAULHUS, Marc M. Mendigo mi vecino. American Mathematical Monthly , 1999, 162-165. http://www.jstor.org/stable/2589054

(2) BERLEKAMP, Elwyn R .; CONWAY, John H .; GUY, Richard K. Formas ganadoras para sus juegos matemáticos, Volumen 4. AMC, 2003, 10: 12. http://www.maa.org/publications/maa-reviews/winning-ways-for-your-mathematical-plays -volumen-4

(3) LAKSHTANOV, Evgenii Leonidovich; ALEKSENKO, Alena Il'inichna. Finitud en el juego de cartas Beggar-My-Neighbor. Problemas de transmisión de información , 2013, 49.2: 163-166. http://dx.doi.org/10.1134/S0032946013020051