$n\times n$ juego de ajedrez con monedas

Question

Las filas y las columnas de un $n\times n$ tablero de ajedrez están numerados $1$ a $n$ y se coloca una moneda en cada campo. Se juega lo siguiente: Se selecciona una moneda que muestre la cola. Si está en la fila $x$ y la columna $y$ entonces toda moneda con número de fila al menos $x$ y un número de columna al menos $y$ se da la vuelta. Este procedimiento se repite. ¿Cuál es el número $L(n)$ para el que es posible conseguir en un máximo de $L(n)$ pasos para que todas las monedas del tablero muestren cara, sea cual sea la distribución inicial de caras y colas?

Demostré por inducción que siempre es posible alcanzar la posición final en el máximo $n^2$ pasos, pero no puedo mostrar para cada $n$ un caso en el que $n^2$ es realmente necesario.

Answer 1

Si empiezas con todas las monedas mostrando cara, y luego seleccionas cada moneda una vez y realizas el movimiento de lanzamiento como se describe (con esa moneda como "esquina"), entonces el tablero resultante requiere $n^2$ pasos para volver al estado de todas las cabezas. (Y esto se generalizó también a los tableros no cuadrados).

El tablero resultante tiene colas en la casilla de la fila $i$ , columna $j$ si y sólo si ambos $i$ y $j$ son Impares (aunque esto no es realmente necesario para demostrar la afirmación anterior).

Para ver por qué la afirmación es cierta, observe que la moneda en $(1,1)$ comienza las colas. Tiene que ser seleccionado por sí mismo si alguna vez va a ser volteado; y como el orden de los movimientos no importa*, podríamos voltearlo primero.

Entonces las dos monedas en $(1,2)$ y $(2,1)$ son colas, y se aplica la misma lógica: tienen que ser lanzadas alguna vez, ninguna otra moneda puede lanzarlas**, y por lo tanto podríamos lanzar las dos de inmediato.

Luego continúe de esta manera, dirigiéndose a su vez a todas las monedas en $(i,j)$ donde $i+j=k$ ya lo hemos hecho $k=2$ y $k=3$ .

*El orden de las jugadas sí importa si mantenemos la restricción de que sólo podemos lanzar monedas que sean cruz. Sin embargo, si eliminamos esta restricción y nos permitimos elegir cualquier moneda, entonces este argumento muestra que $n^2$ todavía se necesitan movimientos.

**Dado que seleccionar una sola moneda dos veces es lo mismo que no hacer nada en el tablero, podemos suponer que una vez seleccionada una moneda, no volverá a ser seleccionada.

Answer 2

Dejemos que $V:=\text{Mat}_{n\times n}\left(\mathbb{F}_2\right)$ sea el conjunto de $n$ -por- $n$ matrices sobre $\mathbb{F}_2$ que es un $\mathbb{F}_2$ -espacio vectorial. Para cada $i,j\in\{1,2,\ldots,n\}$ , dejemos que $T_{i,j}$ denota la matriz cuya $(a,b)$ -la entrada es $1$ si $a\geq i$ y $b\geq j$ y es $0$ de lo contrario. Dado que $\dim_{\mathbb{F}_2}\left(V\right)=n^2$ ningún subconjunto de tamaño inferior a $n^2$ abarca $V$ . Por lo tanto, $L(n)\geq n^2$ es necesario. Por otro lado, $\big\{T_{i,j}\,|\,i,j\in\{1,2,\ldots,n\}\big\}$ abarca $V$ (o, más bien, este conjunto es de tamaño $n^2$ y es linealmente independiente sobre $\mathbb{F}_2$ por lo que es un subconjunto de extensión de $V$ ). Así, $L(n)=n^2$ .

---

Si busca un ejemplo en el que $n^2$ se necesitan movimientos, entonces mira $A:=\displaystyle\sum_{i=1}^n\,\sum_{j=1}^n\,T_{i,j}$ . Entonces, si $A=\left[a_{\mu,\nu}\right]$ entonces $a_{\mu,\nu}=1$ si $\mu$ y $\nu$ son impar, y $a_{\mu,\nu}=0$ de lo contrario. La moneda en la casilla del tablero de ajedrez $(\mu,\nu)$ tiene la cola hacia arriba inicialmente si $a_{\mu,\nu}=1$ .

---

---

En general, en un $d$ -tablero de ajedrez de tamaño $n_1\times n_2\times \ldots \times n_d$ podemos jugar a este juego de forma similar. Dejemos que $t$ sea un número entero positivo fijo. En lugar de asignar una moneda a cada $d$ -podemos asignar a cada uno de los hipercubos unitarios un elemento de $\mathbb{Z}/(t\,\mathbb{Z})$ , llamado el etiqueta del hipercubo. Un movimiento consistirá en seleccionar un hipercubo unitario $\left(i_1,i_2,\ldots,i_d\right)$ y añadir $1$ a la etiqueta de cada hipercubo unitario con índice $\left(j_1,j_2,\ldots,j_d\right)$ tal que $j_\mu\geq i_\mu$ para todos $\mu=1,2,\ldots,d$ . Si $L_t\left(n_1,n_2,\ldots,n_d\right)$ es el menor número entero positivo $\ell$ tal que como máximo $\ell$ se requieren movimientos para cambiar cualquier estado inicial al estado en el que todas las etiquetas son $0$ . Entonces, $$L_t\left(n_1,n_2,\ldots,n_d\right)=n_1n_2\cdots n_d\,(t-1)\,.$$ El problema del PO es un caso especial en el que $t=2$ , $d=2$ y $n_1=n_2=n$ .

Una prueba consiste en trabajar con el unitario $\mathbb{Z}/(t\,\mathbb{Z})$ -Módulo $\displaystyle\bigotimes_{\mu=1}^d\,\big(\mathbb{Z}/(t\,\mathbb{Z})\big)^{\oplus n_\mu}$ que está libre de rango $n_1n_2\cdots n_d$ (aquí $\otimes$ es el producto tensorial sobre $\mathbb{Z}/(t\,\mathbb{Z})$ ). Sea $E_{i_1,i_2,\ldots,i_d}\in\displaystyle\bigotimes_{\mu=1}^d\,\big(\mathbb{Z}/(t\,\mathbb{Z})\big)^{\oplus n_\mu}$ sea el elemento $e^{n_1}_{i_1}\otimes e^{n_2}_{i_2}\otimes\ldots\otimes e^{n_d}_{i_d}$ , donde $e^{n}_i$ denota $(0,\ldots,0,1,0,\ldots,0)\in\big(\mathbb{Z}/(t\,\mathbb{Z})\big)^{\oplus n}$ con $1$ para el $i$ -en la entrada. Escribe $T_{i_1,i_2,\ldots,i_d}$ para $\displaystyle\sum_{j_1=i_1}^{n_1}\,\sum_{j_2=i_2}^{n_2}\,\ldots\,\sum_{j_d=i_d}^{n_d}\,E_{j_1,j_2,\ldots,j_d}$ . Entonces, $$\Big\{T_{i_1,i_2,\ldots,i_d}\,\Big|\,i_\mu\in\left\{1,2,\ldots,n_\mu\right\}\text{ for all }\mu=1,2,\ldots,d\Big\}$$ es un $\mathbb{Z}/(t\,\mathbb{Z})$ -base de $\displaystyle\bigotimes_{\mu=1}^d\,\big(\mathbb{Z}/(t\,\mathbb{Z})\big)^{\oplus n_\mu}$ .

Una versión más generalizada de este problema se ha publicado aquí: Juego: Grupo y tablero de ajedrez multidimensional .