¿Cómo resolver este rompecabezas?

Question

Hay $N$ consecutivos puertas. Dos jugadores de la 'B' y 'J' juega a un juego. Ambos turnos alternativamente, y en cada turno, un jugador puede abrir cualquier puerta. Que definir un bloque de 3 días de puertas abiertas como "agujero". La primera de ellas para crear un "agujero" gana. Jugador 'J' juega primero.

Dado 'N', ¿cómo podemos determinar el ganador suponiendo que ambas juega de manera óptima?

Ejemplo: Vamos a denotar la puerta abierta por la 'o' y cerró la puerta por '-'.

Si N = 3: Inicialmente, todas las celdas están cerradas (---), si 'J' se abre la primera puerta de la configuración (o--). 'B' puede abrir el segundo celular que conduce a la configuración (oo-) o tercera celda (o-o). En ambos casos, 'J' gana.

Si N = 5:

'J' gana por la apertura de la 3ª de la célula es decir, de la configuración (--o--).

Answer 1

En el curso de un juego, los jugadores se quiere evitar la formación de configuraciones o-o o oo, porque eso significa que el otro jugador va a ganar en el siguiente movimiento. Por lo tanto van a tener que abrir las puertas con el fin de dividir secuencias consecutivas de puertas cerradas en dos pequeñas secuencias consecutivas de puertas cerradas.

Si un jugador crea una secuencia de longitud $0$ o $1$ delimitada por las puertas abiertas (o-o o oo) por la apertura de una puerta, entonces el siguiente jugador gana, así que hasta el último movimiento, el juego sólo se componen de secuencias de longitud $\ge 2$ (salvo, quizás, en los límites)

Agregar tres imaginario puertas en cada lado de la secuencia original, y abrir los dos extremos de las puertas. Entonces usted tiene un equivalente de juego, ya que los jugadores nunca intente abrir la $4$ cerrado imaginario puertas (esto podría crear una secuencia de longitud $<2$ permitiendo que el siguiente jugador para ganar). Por lo tanto, sólo necesitamos pensar acerca de los juegos con las secuencias de las puertas cerradas delimitada por dos puertas abiertas.

Desde el juego de los jugadores en una única secuencia en un momento, podemos considerar que cada secuencia es su propio juego, y sólo tenemos que calcular sus respectivos Grundy números. Dejando $\otimes$ ser la operación xor bit a bit de las operaciones sobre los números naturales en $\oplus$ ser la superposición de los juegos, tenemos $G(x \oplus y) = G(x) \otimes G(y)$, e $G(x) = \min \Bbb N - \{G(y); x \to y\}$ (donde $x \to y$ significa que hay un movimiento para jugar en $x$ conseguir $y$)

Si observamos $n$ el juego con una secuencia de $n$ a puerta cerrada delimitada por dos puertas abiertas, y mirando a los movimientos permitidos, obtenemos :
$G(n) = \min \Bbb N - \{G(i)\otimes G(j); 2 \le i,j ; i+j+1=n\}$

Esto permite calcular el Grundy número de $(n)$ $O(n^2)$ pasos. Por ejemplo, $G(2) = G(3) = G(4) = 0$ debido a que usted no puede hacer cualquier movimiento en el que hay (no se puede jugar allí sin crear un $(0)$ o $(1)$ secuencia, lo que significa que el oponente gana a nivel mundial en el siguiente turno).

Si $G(N+4) = 0$, entonces el primer jugador pierde, y si $G(N+4)>0$, entonces no es una estrategia ganadora para el primer jugador.
El primer par de $N$ donde el primer jugador pierde se $6,12,22,30,32,44,54,64,76,86,98,\ldots$

Answer 2

EDITADO en respuesta a comentarios por Gugg:

Si $N$ es impar, es un 1º triunfo de jugador. Deje $N=2n+1$ y etiquetar a las puertas de $-n,\dots,n$. 1er jugador abre la puerta a cero y para el resto del juego se juega un partido de final de mover, si es posible, de lo contrario, las respuestas a 2º jugador de apertura de la puerta $k$ por la apertura de la puerta $-k$. La apertura de la puerta $-k$ nunca puede permitir que un juego interminable de moverse por el 2º jugador, ya que si no lo hacía, a continuación, por la simetría 2º jugador permitido un juego interminable de moverse por la apertura de la puerta $k$, y el 1 de jugador habría hecho.

MÁS de EDICIÓN: Berlekamp, Conway y Guy, la senda de la victoria, Volumen 1, página 93: "Treblecross es un Tic-Tac-Toe juego que se juega en un $1\times n$ franja en la que ambos jugadores usan el mismo símbolo (X). La primera persona en completar una línea de tres cruces gana." Ellos descubren el nim-valor" de $n\le12$, pero por lo que puedo ver, no trabajar fuera de cualquier general de los resultados.

AÚN MÁS EDIT: Hay exploraciones de Treblecross disponibles en la web.

http://lbv-pc.blogspot.com.au/2012/07/treblecross.html se analiza.

http://www.calstatela.edu/faculty/sheubac/presentations/EllieSJhandout.pdf es un debate por parte de Heubach, Chinn, Dufour, y Stevens, desde Mayo de 2009. Dicen que no hay ningún análisis completo; que Grundy valores se han calculado a a $n=2^{21}=2097152$, la búsqueda de 37 "P" posiciones: $0, 1, 2, 8, 14, 24, 32, 34, 46, 56, 66, 78, \dots, 16170$

http://www.mathstat.dal.ca/~rjn/papers/UnsolvedCGT.pdf es Chico y Nowakowski, problemas sin resolver en la combinatoria de los juegos, Febrero 2008. Treblecross viene en parte inferior de la página 3, la parte superior de la página 4. Grundy número de computación empujado a $2^{25}$. Ellos llaman a este juego "Tal vez el más notorio y digno de atención" de la "finito octal juegos".

Flammenkamp mantiene un up-to-fecha sitio web en estos juegos, http://wwwhomes.uni-bielefeld.de/achim/octal.html Él ha empujó la Grundy número de cálculos a $2^{28}$.