5 votos

$4^4$ Tic-Tac-Toe es una primera victoria del jugador

He visto la afirmación de que en $4^4$ Tic-Tac-Toe es evidente que existe una primer jugador en ganar, y más en general, lo que es fácil ver que $n^n$ Tic-Tac-Toe es un triunfo para el primer jugador. Pero me parece que no puede obtener una prueba de trabajo.

De hecho, es fácil ver que $3^3$ Tic-Tac-Toe es un primer triunfo de jugador. (Después de mover en el centro, independientemente de sus oponentes mover usted puede encontrar una $3\times3$ sub-tablero que contiene el centro donde su rival no se ha movido y jugar en él. Entonces usted tiene una secuencia de forzar a que se mueve a ganar.) Supongo que hay un mayor dimensional generalización de esta idea.

Espero que sea obvio lo que las reglas de pienso, supongo que la única cosa que se debe aclarar es que en $n^d$ Tic-Tac-Toe necesitamos $n$ en una fila para ganar.

1voto

Misha Puntos 1723

En el papel de Qubic: $4 \times 4 \times 4$ Tic-Tac-Toe, Patashnik demuestra que incluso el $4^3$ juego es una victoria para el primer jugador con el juego óptimo; por lo tanto el $4^4$ juego debe ser también el primer triunfo de jugador. La prueba es una computadora con la ayuda de la solución, sin embargo, que puede no ser satisfactorio.

Una tabla en este trabajo se demuestra que el estado de la $5^5$ juego estaba todavía abierto en el tiempo (en 1980). Es posible que el problema ha sido resuelto por ahora, pero me hace escéptico de que "una evidente victoria para el primer jugador" existe; definitivamente no era obvio para cualquier persona en el momento!

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