Solución a una moneda de puzzle

Question

Programa de instalación: Usted ha $n$ monedas colocadas en fila. Inicialmente, todas las monedas son los jefes. No está permitido acción: puede eliminar una moneda que no sea en uno de los extremos de una fila, y voltear sus vecinos. La quita de la moneda deben ser los jefes.

Ejemplo: HTHTH se convierte en HHHH si se quita la media de la moneda.

Problema: Para que $n$ puede llegar a un estado con sólo dos monedas restantes?

Mi intento: Dado cualquier 5 cabezas en una fila, siempre podemos eliminarlos de una manera tal que vamos a terminar con 2 cabezas en una fila, sin quitar cualquiera de los extremos. La eliminación de la 2ª a la moneda, el 3 de moneda y, a continuación, el 2º de la moneda:

HHHHH -> TTHH -> THT -> HH

y podemos ver fácilmente inductivamente para $n \equiv 0, 2 \mod 3$ que no hay una solución.

Parece que no hay una solución para$n \equiv 1 \mod 3$, pero estoy teniendo un tiempo difícil mostrar esto.

Answer 1

Demostramos que podemos llegar a un estado con sólo dos monedas restantes si y sólo si $n - 1$ no es divisible por $3$.

Si: Fácil de inducción. Sólo tenga en cuenta cómo$$\text{HHHHH} \to \text{TTHH} \to \text{THT} \to \text{HH}$$and apply repeatedly, with a final$$\text{HHH} \to \text{TT}$$si es necesario.

Sólo si: se tomará nota de dos semi-invariantes que probar esto imposible. Ambos son fáciles de comprobar, mediante la comprobación de los cuatro posibles transformaciones.

$\text{}$1. El número de colas es siempre igual. Por lo tanto, si queremos acabar con dos monedas deben ser del mismo color.

$\text{}$2. El conteo de cada una de las cabezas de $+1$ si aparece a la derecha de un número de colas y $-1$ si aparece a la derecha de un número impar de colas. A continuación, el total de estos $+1$'s y $-1$s'es la constante de mod $3$.

Por ejemplo,$$\text{HHHHTHHTHTTH} = 4 - 2 + 1 - 0 + 1 = 4.$$If $n - 1$ is divisible by $3$, then invariant 2 above is also congruent to $1$ mod $3$. But $\texto{HH}$ is $2$ mod $3$ and $\texto{TT}$ is $0$ mod $3$ así es imposible.