Variación de un juego de matrices

Question

El problema original apareció en el examen Putnam del año pasado:

"Alan y Barbara juegan a un juego en el que se turnan para rellenar las entradas de una matriz 2008×2008 inicialmente vacía. Alan juega primero. En cada turno, un jugador elige un número real y lo coloca en una entrada vacía. El juego termina cuando se rellenan todas las entradas. Alan gana si el determinante de la matriz resultante es distinto de cero; Barbara gana si es cero. ¿Qué jugador tiene una estrategia ganadora?"

No es difícil ver que Barbara puede ganar este juego reflejando los movimientos de Alan sobre una línea vertical. (De hecho, se podría decir que "gana con la multiplicidad 1004".) Mi pregunta es, ¿y si los objetivos fueran al revés? Es decir, supongamos que Alan (el primer jugador) quiere que el determinante sea cero y Bárbara quiere que sea distinto de cero. ¿Quién tiene ahora la estrategia ganadora?

Si esperas que el resultado dependa únicamente de la paridad, debes tener en cuenta que Alan gana en el caso 2×2, porque puede forzar que una fila o columna sólo tenga ceros. Por desgracia, no está nada claro (para mí, al menos) que pueda hacer algo similar con una matriz de 4×4, y mucho menos con una de 2008×2008.

Answer 1

Tampoco puedo hacer todo el problema, pero puedo manejar un caso más general que la otra respuesta : Bárbara gana si Alan juega sólo 0s en un tablero de la forma (4n)x(4n). (Esto es más general porque considera todas las formas posibles de que los 0s fuercen a un determinante a ser cero, no sólo filas y columnas. Hay que reconocer que es menos general porque requiere más del tamaño de la matriz).

En primer lugar, consideremos el caso del 4x4. Rotule la matriz como sigue:

aacd
bbcd
efgg
efhh

Esto empareja las entradas de la matriz. Entonces, la estrategia de Bárbara es bastante fácil: jugar en el par coincidente de donde juegue Alan. Se puede comprobar que, independientemente de cómo juegue Alan, habrá cuatro entradas de Bárbara cuyo producto contribuya al determinante global. Si Barbara juega entradas algebraicamente independientes, entonces esto implica que todo el determinante es distinto de cero.

Extender esto a (4n)x(4n) es bastante fácil. Haz n bloques de 4x4 a lo largo de la diagonal de la matriz grande. Si Alan juega en uno de ellos, Bárbara juega con la estrategia anterior localmente. Si él juega en un bloque fuera de la diagonal, Bárbara simplemente ayuda a Alan jugando 0 en ese bloque. El resultado final será una matriz diagonal de bloques con determinante distinto de cero.

Answer 2

Aunque todavía no puedo responder en el caso general, en el caso en que n > 2 y Alan mueve sólo con 0 en un intento de llenar una fila o columna con 0s, no puede ganar.

Esta prueba está escrita de forma semi-informal para facilitar la lectura.

---

Llama 0 a los movimientos de Alan y X a los de Bárbara.

Una fila o columna "bloqueada" es una fila o columna que Barbara tiene al menos una X. Una fila o columna "desbloqueada" no tiene Xs.

Para que Alan gane en una cuadrícula de nxn, después de completar su jugada tiene que haber al menos una fila con n-1 0s desbloqueados y al menos una fila con n-1 0s desbloqueados.

Definir un conjunto R que contenga, para cada fila no bloqueada, el número de 0s en esa fila.

Definir un conjunto C que contenga, para cada columna no bloqueada, el número de 0s en esa columna.

Para nuestra explicación a continuación escribiremos el conjunto R seguido del conjunto C. Por ejemplo, si R={2,1} y C={1,3} los conjuntos se escribirán como {2,1} {1,3}.

El juego comienza con R y C como conjunto vacío.

     (fuente)

• (1ª jugada) Alan mueve y los conjuntos pasan a ser {1} {1}.

• (2ª jugada) Bárbara se mueve para bloquear una fila y los conjuntos pasan a ser {} {1}.

• (3er movimiento) Alan tiene tres opciones, consideremos cada una:

  • [Caso 1] Alan se mueve en la misma columna que el 0 desbloqueado existente. Los conjuntos pasan a ser {1} {2}
    Bárbara se mueve en la misma columna que los dos 0 desbloqueados. Los conjuntos se convierten en {1} {}.

  • [Caso 2] Alan se mueve en una casilla que está bloqueada tanto en fila como en columna. Bárbara bloquea la columna no bloqueada y los conjuntos se convierten en {} {}.

  • [Caso 3] Alan se mueve en una casilla que no contiene 0s ni Xs tanto en la fila como en la columna. Los conjuntos pasan a ser {1} {1,1}.

     (fuente)

Ahora la situación es como en el diagrama anterior. Supongamos que los 0 están en A y D, y que B y D están vacíos. Una de las filas debe estar bloqueada; supongamos que es la misma fila que A. Entonces Bárbara se mueve en C y los conjuntos se convierten en {} {1}. Si la fila bloqueada es la misma que D, Bárbara se mueve a B y los conjuntos se convierten en {} {1}.

La situación si los 0 están en B y C es simétrica.

Ahora observa que todos los casos son idénticos a una posición anterior del juego o son simétricos a una posición anterior. Por lo tanto Alan nunca puede ganar la partida.

Answer 3

Permítanme ampliar mi comentario. Digamos que estamos tratando con una matriz de 4x4 Alan se limita a los números enteros, Barbara puede utilizar cualquier número racional. Alan mueve primero y quiere forzar a la matriz a tener un determinante integral. Alan se mueve primero Barbara se mueve segundo y su entrada es 1/2 en la misma fila que Alan la mirada en la matriz con la fila Alan se movió por primera vez en y la columna Barbara se movió por primera vez en suprimido. Supongamos que Alan se mueve siguiente en esa matriz entonces Barbara se mueve en la misma fila y entonces la fila Alan se movió en y la columna Barbara se movió en se suprime o Alan no se mueve en la matriz todavía Barbara se mueve en la matriz derivada y otra vez su entrada es 1/2 en la misma fila que Alan. En cualquiera de los dos casos la fila en la que se movió Alan y la columna en la que se movió Barbara se borran y obtenemos una nueva matriz derivada en la que se repite el proceso hasta que haya 4 elementos en la matriz con entrada 1/2 cuyo producto esté en el determinante sumando o restando 1/16. Bárbara se asegura de que el resto de sus entradas son integrales como resultado el 1/16 no se puede cancelar ya que el resto de contribuciones al determinante se pueden expresar como fracciones con denominador 8 o menos y el determinante no es integral. Esta idea se puede ampliar de varias maneras dependiendo de la restricción de los movimientos de Alan.

Answer 4

He aquí una prueba casi de paridad que, en mi opinión, aclara la situación.

Considera el último movimiento. Llámalo X.

Empezando por la ecuación en la que el determinante es cero,

$a_1 + ... + a_{(n-1)\Gamma(n)}+ xb_1 + ... + xb_{(n-1)!}= 0$

$a_1 + ... + a_{(n-1)\Gamma(n)}= - xb_1 - ... - xb_{(n-1)!}$

$a_1 + ... + a_{(n-1)\Gamma(n)}= -x (b_1 + ... + b_{(n-1)!})$

$-\frac{a_1 + ... + a_{(n-1)\Gamma(n)}}{b_1 + ... + b_{(n-1)!}}= x$

Por lo tanto para ganar la persona con la última jugada simplemente necesita jugar

$-\frac{a_1 + ... + a_{(n-1)\Gamma(n)}}{b_1 + ... + b_{(n-1)!}}$

Si n es par, la última jugada es de Barbara por lo que gana, si n es impar, es de Alan por lo que gana.

Lo único que frustra esta estrategia en general es que ${b_1 + ... + b_{(n-1)!}}$ puede ser cero.