Alice y Bob matriz de problema.

Question

Alice y Bob jugar el siguiente juego con un $n*n$ matriz, donde $n$ es impar. Alice se llena en una de las entradas de la matriz por un número real. luego Bob esponja. Entonces Alice y así sucesivamente así sucesivamente hasta que toda la matriz se llena. Al final el determinante de la matriz es tomado. si es distinto de cero Alicia gana y si es cero, Bob gana. La pregunta es para determinar quién gana jugando a la estrategia perfecta cada vez.

Cuando n es incluso es fácil ver por qué Bob gana cada vez. y para n igual a 3 tengo bruta forzado. Bob gana. Pero para n = 5 y encima no puedo ver quién va a ganar en la estrategia perfecta cada vez.

Cualquier inteligente appraoches para la resolución de este problema?

Answer 1

Traté de que el planteamiento de leibniz fórmula para determinantes

$\det(A) = \sum_{\sigma \in S_n} sgn(\sigma) \prod_{i=1}^n A_{i,\sigma_i}$

Hay $n!$ factorial términos de esta suma. Alice le ha $\frac{n^2+1}{2}$ se mueve mientras que Bob ha $\frac{n^2-1}{2}$ se mueve. Hay $n^2$ variables (matriz de entradas). Cada uno de ellos tomado solo aparecen en $(n-1)!$ términos en este resumen. Cuando Bob escoge un cero en su primer paso para cualquier entrada en la matriz, $(n-1)!$ factorial términos de esto, vaya a cero. Por ejemplo, considere un $5 \times 5$ matriz. Así que hay 120 términos. En el primer movimiento, cuando Bob hace que cualquier matriz de entrada cero, él se pone a cero el 24 de estas condiciones. En su segundo movimiento, él tiene que elegir de que la matriz de entrada que tiene menos número de presencia en el primer cero de salida 24 términos. Puede haber varias matriz de entradas. En la cara, se puede ver que hay, sin duda, otro de la matriz de entrada que aparecen en 24 distinto de cero en términos de dicha suma. Desde $n$ es extraño en este caso, la última oportunidad, siempre será la de Alice. Debido a eso, uno no tiene que preocuparse acerca de esto términos de suma cero. Lo que Bob tiene que hacer si él tiene que ganar es que

• Él tiene que asegurarse de que él toca al menos una vez (en efecto ceros) de cada uno de sus 120 términos. En el $n=5$ de los casos, cuenta con 12 posibilidades. En este 12 de posibilidades que él tiene que asegurarse de que él se pone a cero todos los 120 términos. En un sentido, significa que él tiene a un promedio de al menos 10 términos por la oportunidad de su. Me miré en el $n=3$ de los casos, bob tiene 4 posibilidades hay y 6, se puede poner en cero todos ellos en 3 movimientos.

• Él tiene que asegurarse de que Alice no tener el control de todos los de la matriz de entradas en un solo término en 120 términos, porque entonces será distinto de cero, y desde la última posibilidad es la de ella, Bob no será capaz de cero, así que ella va a ganar.

Según la explicación anterior, en el $5 \times 5$, se tiene que la media de la matanza de 10 términos en cada oportunidad que parece bastante fácil de hacer. Siento que este método es un poco fácil generalizar y muchos realmente inteligentes gente de aquí puede hacerlo.

EDITAR\begin{align} \begin{bmatrix} a & b & c & d& e \\ f& g & h &i& j \\k& l& m& n& o \\ p& q& r& s& t\\ u& v& w& x& y \end\begin{align} \begin{bmatrix} 0 & \otimes & \otimes & 0 & \otimes \\ g & f & h &i& j \\l& k& m& n& o \\ q& p& r& s& t\\ v& u& w& x& y \end\begin{align} \begin{bmatrix} 0 & \otimes & \otimes & 0 & \otimes \\ 0 & f & h &i& j \\ \otimes & k & m& n& o \\ 0 & p& r& s& t\\ \otimes & u& w& x& y \end-

En respuesta a @Ross Milikan, traté de mirar a la solución de $5 \times 5$ de los casos, este es el enfoque. Considere la posibilidad de $5 \times 5$ matriz con sus entradas de lleno en el alfabeto inglés de fila, de modo que la matriz de interés es

-#-#-{bmatrix} \end{align}

Sin pérdida de Generalidad (WLOG), vamos a Alice recoger $a$ (de hacer cualquier entrada cero es ventajoso para ella). Digamos que Bob recoge $b$ (de nuevo WLOG, recogiendo cualquier entrada es el mismo). Esto ayuda a Bob a cero el 24 de términos en el total de 120. Alice ha de recoger una entrada en esta primera fila de lo contrario, estará en una situación de desventaja (desde entonces, Bob decide escoger los 3 términos en total desde la primera fila y recibe 72 términos ceros). Así, respecto de la primera fila, Alice toma 3 de ellos, Bob escoge 2 de ellos (es decir $b$$d$), y por lo tanto los ceros 48 términos del total de 120. Ahora se nota que el siguiente movimiento es de Bob. Permítanos swap de la segunda columna y en la primera columna. Esto no cambia el determinante distinto de su signo. Mirar a la modificación de la matriz

-#-#-{bmatrix} \end{align}

donde $0$ es poner en las entradas de Bob ha modificado y $\otimes$ ha sido puesto en entradas modificadas por Alice. Ahora en la primera columna, supongamos que Bob se apodera de $g$$q$, y alice se apodera de $l$$v$. De nuevo Alice tiene que ver este y cualquier otro movimiento se puso en una situación de desventaja. Bob había hecho 4 se mueve ya, el siguiente paso es la suya, y ahora la matriz,

-#-#-{bmatrix} \end{align}

Ahora nos quedamos con la parte inferior $4 \times 4$ matriz, Bob se queda con 8 posibilidades, y el primer paso es el suyo. Compare esto con $4 \times 4$ de los casos, se ve intuitivamente que Bob debe ganar.

Answer 2

Ok, así que Alice tiene la estrategia ganadora si las dimensiones son impares, y he aquí por qué.

Para Alice para ganar, el determinante debe ser distinto de cero, lo que significa que todas las filas/columnas deben ser linealmente independientes.

Alice hace el primer movimiento. Ella puede ir a cualquier lugar. Entonces Bob hace un movimiento. Para Bob para ganar, en el caso más simple, que necesita para duplicar cualquiera de Alicia filas o columnas (entonces ellos no van a ser linealmente independientes). Así que su estrategia ideal podría ser el espejo de sus movimientos. Todos Alice tiene que hacer es asegurarse de que Bob no puede duplicar una de sus filas/columnas, y, por supuesto, debe asegurarse de no duplicar cualquier a sí misma, pero suponiendo que ella es lo suficientemente bueno en aritmética, esto es trivial (ya podemos utilizar cualquiera de los infinitos números reales)

Si n fueron incluso, luego Bob iba a ganar, porque él podría espejo de Alicia, se mueve todo el camino a través de, y no importa a donde ella va, él puede espejo de ella, hasta el final, forzando a una de las filas/columnas de a sea igual a otra, llevando a cero el determinante.

Si n es impar, entonces esta estrategia ya no funciona para Bob, porque él ya no tiene la última jugada. Así que incluso si él espejos Alice través de todo el camino, ella puede asegurar que ninguno de sus filas/columnas son cada vez duplicada por tomar ventaja de la número impar de filas y columnas, y el hecho de que ella va primero y el último. En última instancia, entonces, Alice va a ser capaz de hacer movimientos que Bob no puede espejo, y ella puede garantizar la no-cero determinante.

Por ejemplo, supongamos que Alicia es llenado en una fila, y Bob es el reflejo de ella, con la siguiente fila. Supongamos que rellene toda la fila guardar el elemento final. Si alice rellena este elemento, y Bob espejos, ella pierde. Pero Alicia tiene ahora todo el resto de la junta, por lo que ella puede posiblemente siga tomando Bob a través de este proceso de llenado en las filas hasta el último elemento. Si ellos hacen esto hasta el último de la fila (ya que n es impar, habrá una sola de la última fila), entonces Alice puede empezar a llenar en la última fila, y Bob no puede espejo de ella. Debido a que la longitud de una fila es impar, Alice puede llenar en el elemento final de la fila. Luego, Bob debe hacer un movimiento - pero el único disponible de movimientos son de relleno en el elemento final de las filas anteriores (que vienen en pares ya que Bob reflejado Alice todo el camino). Pero entonces lo que sea que Bob recoge al final de una fila, Alice puede elegir algo más por el espejo de la fila, y así evitar la duplicación de las filas de terminar como duplicados, por lo tanto el mantenimiento de la independencia. Esto continúa hasta el final, con Alice haciendo que el último movimiento. Por lo tanto, Alicia gana.

Answer 3

Sabemos que el determinante de una matriz a es distinto de cero si el rango de la matriz es el mismo tamaño de la matriz. Así, en este caso, el rango(A) es impar. Así, en la última columna (o la primera columna) todos Alice tiene que hacer para garantizar una victoria es asegurarse de que el número real no puede ser escrito como una combinación lineal de los otros en esa columna, haciendo que cada columna independiente. Esto a su vez hace que el rango(A) = n, es decir, el determinante es distinto de cero.

Puede no ser la respuesta correcta en cuanto a lo que usted está buscando, pero es una generalización de los resultados.