Pares y nonesLas reglas del juego y los primeros desafíos pueden verse en
este enlace, otros desafíos pueden verse en
este otro enlace.
De los dos últimos desafíos planteados en la entrada original, uno de ellos pedía pasar de la cinta vacía a una que contuviera solamente la letra A, y el otro desafío, pasar de la letra A a la letra B. En los comentarios a esa misma entrada Marcos Donnantuoni conjeturó que estos objetivos son imposibles de alcanzar; mi intención aquí es demostrar que, en efecto, son imposibles.
La demostración de ambas imposibilidades pasa por un argumento de paridad. Recordemos que la primera regla dice que donde haya dos casillas vacías es posible "crear" dos letras iguales; la segunda regla enuncia la operación inversa, dos letras iguales y consecutivas pueden ser borradas. La tercera regla dice que dos letras diferentes consecutivas (AB, por ejemplo) pueden ser cambiadas por la letra restante (en el ejemplo, una C).
Pensemos ahora en las cantidades de letras que haya en la configuración inicial, y específicamente fijémonos en sus paridades. Las dos primeras reglas no alteran la paridad de esas cantidades, ya le suman o le restan un 2 a una de ellas. La tercera regla, en cambio, cambia las tres paridades a la vez, ya que le suma un 1 a una cantidad y le resta 1 a las otras dos. Es decir, al aplicar cualquiera de las reglas, o bien las tres paridades no cambian, o bien cambian todas a la vez.
Esto significa que, si al comenzar, las cantidades de dos de las letras tenían la misma paridad (ambas cantidades eran pares o ambas eran impares) entonces a lo largo de todo el proceso esas cantidades seguirán teniendo la misma paridad (porque, en caso de cambiar, ambas paridades cambiarán al mismo tiempo); y si esas dos cantidades, al comenzar, tenían diferente paridad entonces la paridad seguirá siendo siempre diferente (por la misma razón). Podemos decir, en resumen, que las
paridades relativas de las cantidades de letras no cambiarán nunca.
Ahora bien, si quisiéramos pasar de la cinta vacía a la letra A entonces al comenzar las cantidades de A y de B tendrían la misma paridad (ambas cantidades serían pares, ya que valen cero), mientras que al terminar habría una cantidad impar de A (una letra) y una cantidad par de B (cero). La paridad relativa de A y B habría cambiado, lo cual es imposible. Luego, no puede pasarse de la cinta vacía a una sola A. Lo mismo sucede si queremos pasar de A a B, porque al comenzar A y C tendrían diferente paridad (uno y cero son las cantidades iniciales de esas letras), pero al terminar tendrían la misma (cero y cero, ambas pares).
Una pregunta que queda pendiente es si vale la afirmación recíproca; es decir, si tenemos dos configuraciones de letras en las cuales las paridades relativas de A, B y C son las mismas (es decir, dos paridades que sean iguales/diferentes en una configuración son también iguales/diferentes en la otra configuración) entonces ¿es siempre posible pasar de una configuración a la otra? Creo que la respuesta es que sí, aunque no he podido encontrar una demostración elegante de ese hecho.
