10 votos

Cuál es la estrategia ganadora de este juego en el conjunto del poder

Dado un conjunto finito, los jugadores alternativamente elija adecuada subconjuntos. Una vez que un subconjunto ha sido elegido, ninguno de sus subconjuntos pueden ser elegido más tarde. El último jugador en movimiento gana.

Me di cuenta de que, con un óptimo de juego, el Jugador 1 gana. Esto es debido a que él puede elegir el conjunto null y regalar su movimiento, convirtiéndose en el segundo jugador, o no elegir el nulo conjunto y hacer un "real" que se alojen en el primer jugador. Porque él puede elegir, y uno de los jugadores gane con un óptimo sistema de juego, el Jugador 1 debe ganar. Sin embargo, yo no puedo averiguar una estrategia para él, aparte de la elección/no elegir el conjunto null.

5voto

dc.sashwat Puntos 41

Este juego es muy conocido. Por desgracia, tiene muchos nombres diferentes, y muy pocos resultados conocidos.

Nombres/juegos relacionados

Chomp es un juego por lo general jugado en un rectángulo, donde los jugadores se muerde pero no puede comer la parte superior izquierda de la plaza. Para el conjunto finito de tamaño $2$, este juego es $2\times2$ chomp en esta manera: $$\begin{array}{|c|c|}\hline \boxed{\{1,2\}}& \{1\} \\ \hline \{2\}& \emptyset \\ \hline\end{array}$$ Esto se puede generalizar a las altas dimensiones, utilizando el $n$-cubo, por lo que su juego es equivalente a "$n$-dimensiones Chomp en un $2\times2\times\cdots\times2$ junta".

Andries E. Brouwer tiene una buena página en Chomp con una gran cantidad de información. Su juego se menciona en la sección "Chomp en un simplicial complejo", aunque se utiliza la convención opuesta, donde los movimientos son los complementarios de los movimientos que usted describe, de manera que teniendo todo el conjunto sería como tomar el conjunto vacío y tomando el conjunto vacío te haría perder (tomando el conjunto no está permitida en su descripción). También menciona que este juego puede ser llamado "Schuh del juego para la plaza libre de $N$" (aquí los jugadores seleccionar divisores), "subconjunto de comida para llevar", "hyperchomp" (como se usa en Jan Draisma recreativos de matemáticas página), y el "superconjunto de juego".

Resultados

En Nim-tipo de juegos por Gale y Neymar, se conjeturó que la jugada ganadora para el subconjunto de juego es siempre para tomar el elemento maximal (en tu juego, para tomar $\emptyset$ en primer lugar). Esto se muestra (después de la recomposición del juego, de modo que se inicia después de que estandarizada de mover) por $n=1,2,3$ en Albert Meyer notas en Matemáticas para Ciencias de la computación e $n=4$ en las soluciones correspondientes. En Brouwer de la página mencionada anteriormente, y en el papel En Tres de remo Chomp por Brouwer, Horváth, Molnár-Sáska, y Szabó, se menciona que esto sigue siendo cierto para $n=5,6,7$.

No sé de ningún otro resultado, pero este superconjunto del juego se menciona en el Hombre y Nowakowski la lista de problemas no resueltos en la CGT de Más Juegos de que No hay Oportunidad para que cualquier progreso habría sido en los últimos 15 años o así, pero no puedo encontrar nada más.

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X