Olimpiadas de Matemáticas
Página de preparación y problemas

Solución. Por simplicidad identificaremos cada casilla con un par de enteros $(a,b)\in\mathbb{Z}\times\mathbb{Z}$ que denotarán sus coordenada en el tablero y también denotaremos por $C(a,b)$ al cuadrado $n\times n$ que tiene su esquina inferior izquierda en la casilla $(a,b)$. Si volteamos los cuatro cuadrados $C(a,b),C(a+1,b),C(a,b+1),C(a+1,b+1)$, cambiamos únicamente las monedas de las casillas $(a,b),(a+n,b),(a,b+n),(a+n,b+n)$ suponiendo que $n\geq 2$. Esto nos dice que siempre podemos obtener cualquier número de caras que sea múltiplo de $4$ (repitiendo esta construcción en distintas partes alejadas del tablero infinito) y también que podemos aumentar en dos caras cualquier configuración dada ya que basta aplicar estos cambios a la casilla $(a,b)$ con cara hacia arriba que tenga $a+b$ máximo de entre todas las casillas con cara hacia arriba (este proceso hace cambia la casilla $(a,b)$ de cara a cruz y las casillas $(a+n,b),(a,b+n),(a+n,b+n)$ de cruz a cara, lo que supone dos caras más). En particular, para todo $n$, podemos encontrar configuraciones con cualquier número par de caras mayor o igual que $4$.

Veamos ahora que no se pueden tener únicamente dos caras (suponiendo que $n\geq 2$). Esto es consecuencia inmediata de que no puede haber ninguna fila ni columna con una única cara. Para probar esto último, pensemos en una fila o columna y pensemos en cada volteo como cambiar en ella $n$ casillas consecutivas. Habrá cambios que anulen a otros cambios si se aplican a las mismas $n$ casillas, luego podemos suponer que cada conjunto de $n$ casillas consecutivas se ha volteado $0$ o $1$ veces y al menos uno se ha volteado $1$ vez ya que hay una casilla con cara hacia arriba. De entre los conjuntos que de $n$ casillas que se han volteado una vez, necesariamente la primera casilla del primer conjunto y la última casilla del último conjunto deben tener la cara hacia arriba (y no pueden ser la misma porque $n\geq 2$).

Con todo esto, vamos a plantear la solución distinguiendo la paridad de $n$.

• Cuando $n$ es par, cada cambio pasa de $k$ caras a $n^2-k$ caras y ambos números tienen la misma paridad, luego la paridad del número de caras no cambia en el proceso. Como empezamos con $0$ caras, no puede obtenerse un número impar de caras en ningún momento. Entonces, la solución para $n$ par es cualquier número par mayor que $2$.
• Cuando $n$ es impar, también podemos obtener cualquier número par mayor que $2$ de la misma manera, pero también es fácil obtener cualquier número impar mayor o igual que $n^2$ ya que podemos comenzar con $n^2$ caras y luego sumarle dos caras mediante el método descrito anteriormente. Habremos terminado si demostramos que no se puede obtener un número impar menor que $n^2$.

  A cada casilla $(a,b)$ le asignamos el resto $a+bn \pmod{n^2}$. De esta forma, cada vez que volteamos un cuadrado $n\times n$ estamos volteando una exactamente una casilla de cada uno de los restos módulo $n^2$. Si tuviéramos un número impar de caras menor que $n^2$, entonces habría algún resto en el que no habría caras. Podríamos pensar en que cada volteo cambia exactamente $n^2-1$ casillas si omitimos las que tienen resto $r$. Como $n^2-1$ es un número par y cambiamos $k$ caras por $n^2-1-k$ caras, no cambiamos la paridad del número de caras en este proceso, que equivale al original para esta configuración. Como empezamos con $0$ caras antes del primer volteo, el número siempre permanecerá par.

Nota. La última parte de la solución módulo $n^2$ está escrita a partir de la solución oficial.