Lanzar monedas en un tablero de ajedrez

Question

Se colocan 64 monedas en un tablero de ajedrez; las monedas de las casillas negras salen cara, las de las casillas blancas salen cruz. En cada paso, se puede elegir tres monedas consecutivas en la misma fila o columna, y voltear estas tres monedas. ¿Es posible obtener todas las cabezas?

Me las arreglé para terminar con una cola y 63 cabezas. Creo que la respuesta es negativa, pero no conseguí encontrar una invariante fácil.

Answer 1

La idea detrás de esto, como sugirió OP, es encontrar una invariante. Lo que esto significa, es que necesitas encontrar una manera de expresar la suma en el tablero, y mostrar que cualquier paso que des no cambia la suma.
A veces (como en este caso), el invariante que has elegido no funciona, ya que los pasos siguen cambiando la suma. Si es así, fíjate en cómo los pasos cambian la suma, y utiliza otro argumento como la paridad (que se generaliza con la aritmética del módulo).
La parte difícil de la cuestión suele ser averiguar qué invariante utilizar, o por qué es probable que funcione.

Una pista: Dado que sus movimientos son sólo 3 monedas consecutivas en una fila o columna, una buena cosa para usar es la raíz cúbica de la unidad, ya que $\omega^2 + \omega + 1 = 0$ .

Una pista: Definir que la suma del tablero sea $\sum f_{(a, b)} \omega^{a + b }$ , donde $f_{(a, b)} = 1 $ si la moneda sale cara, -1 si sale cruz. Este va a ser nuestro invariante, como se mencionó anteriormente. La motivación para ello es de la pista anterior, y tenemos que entender cómo cambia este invariante.

Una pista: ¿Cómo cambia esta suma cuando haces algún movimiento? (Esta es la observación clave que debes hacer).

Elaboración: Para una moneda en escuadra $(a, b)$ simplemente nos importa el valor de $a+b \pmod{3}$ . En cada lanzamiento (de 3 monedas consecutivas), las monedas se encuentran en distintas clases de residuos.

Si lanzamos monedas que son (cabeza, cabeza, cabeza) en las clases de residuos 0, 1, 2, ahora son (cola, cola, cola), y la diferencia en la suma es $+1 + \omega + \omega^2 = 0$ a $-1 - \omega - \omega^2 = 0$ Así que nada cambia.

Si las monedas eran (cabeza, cabeza, cola) en las clases de residuos 0, 1, 2, ahora son (cola, cola, cabeza). La suma del tablero cambia de $+1 + \omega - \omega^2 = -2 \omega^2 $ a $-1 -\omega + \omega^2 = 2 \omega^2$ . Esta suma cambia por $+4 \omega^2$ , por lo que no tenemos un invariante exacto, pero esperamos tener suerte y poder utilizar un argumento de paridad adicional.

Mira los otros 6 casos (algunos de los cuales son reflexiones). Comprueba cómo cambia la suma. Afirmo que la suma cambia en $ \pm 4, \pm 4\omega, \pm 4\omega^2, 0$ .

Una pista: Sea (1, 1) un cuadrado negro. En la configuración original, la suma del tablero es $ - 3$ . Se puede comprobar esto mirando un cuadrado de esquina de 2 por 2 ya que 6 cuadrados consecutivos cualesquiera se anulan. Obtenemos $\omega^2 - 2 + \omega = -3$ .

Una pista: Si obtenemos todas las cabezas, entonces la suma de la tabla es $+3$ . Puedes comprobarlo mirando un cuadrado de 2 por 2 en una esquina, ya que 3 cuadrados consecutivos cualesquiera se anulan. Obtenemos $ \omega^2 + 1 +1 + \omega = +3$ .

Ahora, convéncete de que no hay forma de llegar desde $- 3$ a $+3$ si podemos cambiar los valores sólo por $ \pm 4, \pm 4\omega, \pm 4\omega^2, 0$ cada vez. Esto debería ser obvio.

Answer 2

Esto es esencialmente una versión más elemental del argumento de Calvin Lim. Colorea el tablero por diagonales en tres colores como se muestra a continuación:

$$\begin{array}{|c|c|} \hline 2&\color{red}{0}&1&\color{red}{2}&0&\color{red}{1}&2&\color{red}{0}\\ \hline \color{red}{0}&1&\color{red}{2}&0&\color{red}{1}&2&\color{red}{0}&1\\ \hline 1&\color{red}{2}&0&\color{red}{1}&2&\color{red}{0}&1&\color{red}{2}\\ \hline \color{red}{2}&0&\color{red}{1}&2&\color{red}{0}&1&\color{red}{2}&0\\ \hline 0&\color{red}{1}&2&\color{red}{0}&1&\color{red}{2}&0&\color{red}{1}\\ \hline \color{red}{1}&2&\color{red}{0}&1&\color{red}{2}&0&\color{red}{1}&2\\ \hline 2&\color{red}{0}&1&\color{red}{2}&0&\color{red}{1}&2&\color{red}{0}\\ \hline \color{red}{0}&1&\color{red}{2}&0&\color{red}{1}&2&\color{red}{0}&1\\ \hline \end{array}$$

Los números rojos marcan las casillas inicialmente ocupadas por las monedas que muestran cabezas; $12$ de las cabezas están en color $0$ , $10$ están en color $1$ y $10$ están en color $2$ . De los $32$ monedas que muestran la cola, $10$ están en color $0$ , $11$ están en color $1$ y $11$ están en color $2$ . Por lo tanto, para obtener cabezas en todos $64$ cuadrados, debemos cambiar la paridad del número de cabezas en los colores $1$ y $2$ sin cambiar la paridad del número de cabezas en color $0$ . Sin embargo, esto es imposible: cada movimiento cambia la paridad del número de cabezas de cada color, por lo que el número de movimientos debe ser impar para cuidar los colores $1$ y $2$ e incluso para cuidar el color $0$ .