El acertijo MU es un buen ejemplo de un problema lógico donde es útil determinar el invariante. El acertijo consiste en buscar si es posible convertir MI a MU, utilizando las siguientes operaciones.
- Si una cadena termina con una I, se le puede agregar una U (xI -> xIU).
- Cualquier cadena luego de una M puede ser totalmente duplicada (Mx -> Mxx).
- Donde haya tres Is consecutivas (III) se las puede reemplazar por una U (xIIIy -> xUy).
- Dos Us consecutivas, pueden ser eliminadas (xUUy -> xy).
Para resolver este problema, es posible pasar horas aplicando estas reglas a distintas cadenas. Sin embargo, puede ser más fácil encontrar una afirmación que sea invariante para todas las reglas y que muestre si es o no posible llegar a obtener MU.
Al analizar las reglas, la forma de deshacerse de las Is es conseguir tener tres Is consecutivas en la cadena. La única forma de deshacerse de todas las Is es que haya un cantidad de Is consecutivas múltiplo de tres.
Es por esto que es interesante considerar la siguiente afirmación como invariante: el número de Is en la cadena no es múltiplo de tres.
Para que esta afirmación sea invariante al acertijo, para cada una de las reglas se debe cumplir que: si el invariante era verdadero antes de aplicar la regla, seguirá siendo verdadero luego de aplicarla.
Para ver si esto es cierto o no, es necesario considerar la aplicación del invariante para cada una de las reglas.
- Se agrega una U, la cantidad de Is no varía, por lo cual se mantiene el invariante.
- Se duplica toda la cadena luego de la M, siendo n la cantidad de Is antes de la duplicación, si n no es múltiplo de 3, 2n tampoco lo será.
- Se reemplazan tres Is por una U. Al igual que antes, siendo n la cantidad de Is antes del reemplazo, si n no es múltiplo de 3, n − 3 tampoco lo será.
- Se eliminan Us, la cantidad de Is no varía, por lo cual se mantiene el invariante.
Todo esto indica claramente que el invariante se mantiene para cada una de las posibles transformaciones. Esto significa que sea cual fuere la regla que se elija, si la cantidad de Is no es un múltiplo de tres antes de aplicarla, no lo será luego de hacerlo.
Teniendo en cuenta que hay una única I en la cadena inicial MI, y que uno no es múltiplo de tres, es imposible llegar a MU con estas reglas, ya que MU tiene cero Is, que sí es múltiplo de tres.