¿Es posible cambiar las posiciones de 2 monedas distintas si sólo podemos añadir o quitar 2 monedas consecutivas del mismo tipo a la vez?

Question

Usando dos monedas, una roja y otra azul (en ese orden de izquierda a derecha). Si juegas a un juego cuyas reglas son:
Se pueden añadir o quitar 2 monedas consecutivas, rojas o azules, adyacentes, ¿es posible llegar a un estado en el que la moneda de la izquierda sea azul y la de la derecha roja
Por ejemplo: Usando R y B para representar la moneda roja y azul respectivamente, su posición inicial es
RB
RBRR (al añadir 2 monedas rojas consecutivas a la derecha de la disposición inicial)
RBBBRR
BBRBBBRR
BBRBRR (al retirar las 2 monedas azules consecutivas del centro).

Mi argumento es que como sólo se puede sumar y quitar en pares consecutivos, no hay manera de aislar una moneda Azul o una Roja de manera que podamos intercambiar sus posiciones. Por lo tanto, no hay manera de alcanzar un estado en el que la posición de las monedas sea BR.

¿Es esto correcto?

Answer 1

Si te enfrentas a un problema "aquí hay algunas transformaciones posibles; demuestra que nunca puedes alcanzar tal o cual estado", una buena estrategia es encontrar un invariante. Un invariante es alguna propiedad que (demuestras) nunca cambia entre pasos. Si es diferente entre tu estado inicial y tu estado final deseado, entonces nunca podrás llegar a ese estado final.

En este caso, para cualquier estado, cuente el número de formas de elegir dos monedas de manera que la que está más a la izquierda sea roja y la que está más a la derecha sea azul.

Por ejemplo:

• RB tiene una forma.
• RBBB tiene tres: RB.. , R.B. et R..B .
• RBBBRR todavía tiene tres: RB.... , R.B... , R..B.. .
• RRRBBBRRR tiene nueve: R..B..... , R...B.... , R....B... , .R.B..... , .R..B.... , .R...B... , ..RB..... , ..R.B.... , ..R..B... .

Debes comprobar que, independientemente de cómo insertes o elimines dos monedas adyacentes del mismo color, esta cantidad cambia en un número par. (Así que el invariante es si esta cantidad es impar o par).

Dado que la cantidad comienza en impar, siempre permanece en impar. Pero en el estado BR Es decir, es $0$ que es par, por lo que el estado BR nunca puede ser alcanzado.