7 votos

Ganar estrategia en $(2n+1) \times (2n+1)$ juego de matrix.

Edit: Un par de minutos después de la publicación de esta pregunta (que yo había estado pensando durante aproximadamente un día) me di cuenta de la respuesta en el $3 \times 3$ de los casos; véase mi respuesta a continuación. Sin embargo, la pregunta que todavía podría ser interesante en el más general de la $(2n+1) \times (2n+1)$ de los casos, por lo que todavía estoy interesada en la cuestión más general. Abajo está la pregunta original.


Revisión de campo $\mathbb K$. Dos jugadores, Eloise y Abelardo, jugar a un juego. Comienzan con un vacío $3 \times 3$ matriz. $$ \begin{pmatrix} * & * & * \\ * & * & * \\ * & * & * \end{pmatrix} $$ Su turno alternativo: en primer lugar Eloise, a continuación, Abelardo, y así sucesivamente. Una vez se compone de relleno en uno de los espacios en blanco en la matriz con un elemento de $\mathbb K$. Después de Eloise primer movimiento, la matriz podría parecer $$ \begin{pmatrix} * & 3 & * \\ * & * & * \\ * & * & * \end{pmatrix}; $$ después de Abelardo primer movimiento, que podría parecer $$ \begin{pmatrix} * & 3 & * \\ * & * & * \\ -5 & * & * \end{pmatrix}. $$ El juego termina cuando la matriz se llena, por lo que un juego siempre dura 9 vueltas. Eloise gana el juego si la matriz es invertible, es decir, si su determinante es distinto de cero. Abelardo gana si la matriz es singular, es decir, su determinante se desvanece.

Claramente, dado que el número de vueltas en el juego es limitado, uno de los jugadores tiene una estrategia ganadora.

Mi pregunta es:

¿Eloise o Abelardo tiene una estrategia ganadora? ¿Esto dependerá el campo $\mathbb K$, y si es así, ¿de qué manera?

La pregunta está motivada por esta pregunta y respuesta , donde se muestra que si trabajamos en un $2n \times 2n$ de la matriz en su lugar, Abelardo tiene una estrategia ganadora: cuando Eloise juega un movimiento en una fila impar, Abelardo juega el mismo movimiento en la fila de abajo; y cuando Eloise juega un movimiento en una hilera, Abelardo juega el mismo movimiento en la fila de arriba. Esto asegura que, por cualquier $i$ filas $2i-1$ $2i$ está de acuerdo, por lo que la matriz es singular. Tenga en cuenta que esta estrategia también funciona si Abelardo sólo copias Eloise se mueve en las filas 1 y 2, y juega de movimientos aleatorios (fuera de la fila 1 y 2) de lo contrario.

La misma estrategia no funciona en el extraño caso: si Abelardo intenta hacer filas 1 y 2 de la $3 \times 3$ matriz, Eloise se puede llenar la fila 3 en primer lugar, obligando a Abelardo a hacer un movimiento en la fila 1 y 2 antes de Eloise. Ya que todos los números pares son fáciles, y un $1 \times 1$ matriz es un caso trivial, esto hace que el $3 \times 3$ matriz de la primera no-trivial caso; pero, por supuesto, podemos hacer la pregunta de una $(2n +1) \times (2n+1)$ matriz para cualquier $n$.

Escribí un corto, a la ineficiencia de secuencia de comandos de Python para la fuerza bruta de la solución para $\mathbb K = \mathbb F_2$, e $\mathbb K = \mathbb F_3$. (Es tan ineficiente que $\mathbb K = \mathbb F_5$ ya es un problema). Resulta que en estos dos casos, Abelardo tiene una estrategia ganadora (suponiendo que mi script es la correcta), aunque no he sido capaz de ver un patrón en los resultados de los cálculos que sugieren un humano-comprensible estrategia.

Para una última observación: parece que Eloise tiene una ventaja, consiguiendo el primer y el último turno, pero resulta que su primer turno es (esencialmente) determinado. Es decir, si ella juega un cero, entonces Abelardo puede vencer a ella. Sin pérdida de generalidad, supongamos ella ha jugado el cero en la parte superior izquierda. A continuación, Abelardo puede agregar un cero al lado, y Eloise se ve obligado a guardar la fila de convertirse en todos los ceros: $$ \begin{pmatrix} 0 & 0 & e_1 \\ * & * & * \\ * & * & * \end{pmatrix}. $$ Entonces, Abelardo puede jugar un cero en el medio a la izquierda, obligando a Eloise de forma similar guardar la columna de la izquierda se convierta todos los ceros: $$ \begin{pmatrix} 0 & 0 & e_1 \\ 0 & * & * \\ e_2 & * & * \end{pmatrix}. $$ Pero, a continuación, Abelardo gana por jugar un 0 en el centro del campo: $$ \det\begin{pmatrix} 0 & 0 & e_1 \\ 0 & 0 & * \\ e_2 & * & * \end{pmatrix} = 0. $$ Por lo tanto, Eloise debe jugar un no-cero mover, y por la ampliación de la matriz podemos muy bien suponer que ella juega 1. Así, podemos empezar el juego como $$ \begin{pmatrix} 1 & * & * \\ * & * & * \\ * & * & * \end{pmatrix} $$ en su lugar, dejar de Abelardo y tomar el primer paso.

3voto

Mees de Vries Puntos 165

De hecho, me di cuenta de la respuesta a mí mismo, sólo un par de minutos después de la publicación, pero pensé que no iba a eliminar la pregunta que ya había tenido un par de upvotes y una de las favoritas. La respuesta es,

Abelardo tiene una estrategia ganadora, independientemente de $\mathbb K$.

Para simplificar, la estrategia es tirar de la misma "plaza de los ceros" truco que gana él el juego si Eloise se inicia con un 0 mover. Tomamos la versión del juego donde Eloise se inicia con un 1 en la esquina superior izquierda. A continuación, Abelardo juega un 0 en el centro. $$ \begin{pmatrix} 1 & * & * \\ * & 0 & * \\ * & * & * \end{pmatrix} $$ Sin pérdida de generalidad (por simetría) podemos asumir que Eloise jugada siguiente, o en la columna de la izquierda o en la parte inferior de la fila. Ahora podemos distinguir un par de casos.

  1. Eloise juega en una esquina, de modo que el campo es $$ \begin{pmatrix} 1 & * & * \\ * & 0 & * \\ x & * & y \end{pmatrix}, $$ donde $x,y$ puede ser un campo vacío o uno de sus valores. A continuación, Abelardo puede sacar sus truco de la misma manera: $$ \begin{pmatrix} 1 & 0 & * \\ * & 0 & * \\ x & * & y \end{pmatrix} \ \begin{pmatrix} 1 & 0 & * \\ * & 0 & * \\ x & e_1 & y \end{pmatrix} \ \begin{pmatrix} 1 & 0 & * \\ * & 0 & 0 \\ x & e_1 & y \end{pmatrix} \ \begin{pmatrix} 1 & 0 & * \\ e_2 & 0 & 0 \\ x & e_1 & y \end{pmatrix} \ \begin{pmatrix} 1 & 0 & 0 \\ e_2 & 0 & 0 \\ x & e_1 & y \end{pmatrix} $$
  2. Eloise juega por debajo de la 1, de modo que el campo es $$ \begin{pmatrix} 1 & * & * \\ e_1 & 0 & * \\ * & * & * \end{pmatrix}. $$ A continuación, Abelardo fuerzas $$ \begin{pmatrix} 1 & * & * \\ e_1 & 0 & * \\ * & 0 & * \end{pmatrix}\ \begin{pmatrix} 1 & e_2 & * \\ e_1 & 0 & * \\ * & 0 & * \end{pmatrix}\ \begin{pmatrix} 1 & e_2 & * \\ e_1 & 0 & * \\ * & 0 & 0 \end{pmatrix}\ \begin{pmatrix} 1 & e_2 & * \\ e_1 & 0 & * \\ e_3 & 0 & 0 \end{pmatrix}\ \begin{pmatrix} 1 & e_2 & * \\ e_1 & 0 & 0 \\ e_3 & 0 & 0 \end{pmatrix}. $$
  3. Eloise se reproduce a continuación el 0. A continuación, Abelardo puede hacer el mismo como en el caso 2 por jugar ceros en (2,3), (1,3), (1,2) respectivamente.

No es obvio para mí si o cómo esto se generaliza a los números impares mayores que 3.

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