Nacional 1998 N2 P6

[Joacoini]

Cada casilla de un tablero de $8 \times 8$ está coloreada de blanco o de negro. Cada operación permitida consiste en elegir en el tablero cualquier rectángulo de $3 \times 4$ o de $4 \times 3$ que cubra exactamente $12$ casillas y cambiar simultáneamente los colores de esas $12$ casillas (las blancas pasan a negras y las negras pasan a blancas).
Diremos que una coloración es buena si es posible, mediante una sucesión de operaciones permitidas, obtener a partir de ella un tablero que tiene todas las casillas blancas. En caso contrario, la coloración es mala.
Demostrar que el número de coloraciones malas es mayor o igual que $15$ veces el número de coloraciones buenas.

[Fran5]

Spoiler: mostrar

Observemos que hay $2^{64}$ coloraciones.

Observemos también que aplicar dos veces la misma movida es lo mismo que no aplicarla.
Además hay $2 \cdot 5 \cdot 6 = 60$ movidas distintas que se pueden aplicar en el tablero (pues hay que elegir la casilla inferior izquierda del rectàngulo y su orientaciòn. $5$ filas y $6$ columnas si es de $4 \times 3$, y lo mismo si es de $4 \times 3$)
Luego hay como mucho $2^{60}$ coloraciones buenas (si aplicamos la movida o no en ese rectángulo)

Entonces la cantidad de coloraciones malas es al menos $2^{64}-2^{60} = 2^{60}(2^4-1) = 15 \times 2^{60}$

Y listo