Lo que Lorenzo sugirió en los comentarios es mirar matrices sobre $\operatorname{GF}(2)$ (alias $\mathbb{Z}_2$ ). En concreto, para cada movimiento correspondiente a $(i, j)$ nos fijamos en el $01$ -que tiene $1$ en posiciones adyacentes e incluyendo $(i, j)$ y $0$ en todas partes.
Por ejemplo, la matriz correspondiente a $(1,2)$ es
\begin{pmatrix} 1 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 \end{pmatrix}
Llamemos a estas matrices $A(i,j)$ . Si nuestro estado inicial está representado por un $01$ -matriz $A_0$ añadiendo a continuación $A_0 + A(i,j)$ modulo $2$ da la matriz actualizada después de realizar el movimiento " $(1,2)$ ."
Cualquier estado que alcancemos puede describirse como $$ A_0 + \sum_{i = 1}^5 \sum_{j = 1}^5 c_{i,j} A(i,j) \pmod 2$$ y puesto que $1 + 1 \equiv 0 \pmod 2$ podemos suponer que $c_{i,j}$ es $0$ o $1$ .
Entonces podríamos pensar que la respuesta es $2^{25}$ ya que hay $25$ coeficientes $c_{i,j}$ pero no tan rápido porque podría haber algunas dependencias lineales entre las matrices $A(i,j)$ . Lo que queremos es la dimensión del espacio lineal $\operatorname{span}\{A(i,j) : 1 \le i, j \le 5\}$ .
Utilicé Mathematica para calcular esto ya que cada matriz tiene $25$ entradas y hay $25$ por lo que para calcularla formaríamos una $25 \times 25$ matriz y reducir filas (operaciones realizadas mod $2$ ) para encontrar su rango.
Adjacent[i_, j_] :=
Boole[
Table[
Abs[x - i] == 1 && y == j || x == i && Abs[y - j] == 1 || x == i && y == j,
{x, 5}, {y, 5}]]
MatrixRank[Flatten[Table[Flatten[Adjacent[x, y]], {x, 5}, {y, 5}], 1], Modulus -> 2]
(*output: 23*)
Estoy aplastando $A(i,j)$ primero para convertirlo en un vector. Así, la matriz $A(1,2)$ se convertiría en el vector $(1,1,1,0,0,0,1,0,0,0,\dots,0)$ (basta con escribir las filas en orden).
Así $\dim \operatorname{span}\{A(i,j) : 1 \le i, j \le 5\} = 23$ lo que significa que hay $2^{23}$ combinaciones lineales distintas de $A(i,j)$ en $\operatorname{GF}(2)$ .
Haciendo lo mismo con el módulo fijado en $3$ da una dimensión de $22$ y así habría $3^{22}$ si jugáramos el mismo partido otra vez $\operatorname{GF}(3)$ .
Si estás confundido en cuanto a por qué es módulo^dimensión imagina tomar una base. Así para $\operatorname{GF}(2)$ la dimensión es $23$ por lo que existe una base $E_1,\dots,E_{23}$ (que podríamos calcular a partir del RREF). A continuación,
$$ \left\{ \sum_{i = 1}^5 \sum_{j = 1}^5 c_{i,j} A(i,j) : c_{i,j} = 0 \text{ or } 1\right\} = \left\{ \sum_{k = 1}^{23} d_{k} E_k : d_k = 0 \text{ or } 1\right\} $$
(de nuevo, mod $2$ ). Pero a diferencia del primer conjunto, en el que podíamos escribir la misma matriz utilizando diferentes opciones de $c_{i,j}$ para el segundo conjunto, existe una única matriz para cada elección diferente de $(d_1,d_2,\dots,d_{23})$ . Y ahora por fin hay $2$ opciones para cada $d_k$ : o $0$ o $1$ .
Y si quieres las celdas diagonales también en $A(i,j)$ entonces en el código, podemos utilizar en su lugar
Adjacent[i_, j_] :=
Boole[Table[Abs[x - i] <= 1 && Abs[y - j] <= 1, {x, 5}, {y, 5}]]
Con las celdas diagonales, las dimensiones son ambas $16$ (mod $2$ o mod $3$ ).
Así, aquí sólo hay $2^{16}$ o $3^{16}$ estados que podemos alcanzar respectivamente.
