Simulacro Nacional 2022 Politecnico - Nivel 1 Problema 5

[Fedex]

El alfabeto de los antiguos usa solo las letras $a,b,c,d,e,f,g$. Dadas dos palabras $p$ y $q$ cualesquiera, decimos que $q$ es un $p$-sinónimo si podemos llegar de $q$ a $p$ realizando las siguientes operaciones:

• Realizar cualquiera de los siguientes cambios:
  $$a\to bc,\quad b\to cd,\quad c\to de,\quad d\to ef,\quad e\to fg,\quad f\to ga,\quad g\to ab.$$

• Tomar $3$ letras consecutivas tales que la primera y la tercera son la misma y borrarlas. Por ejemplo: $cgc \to g$.

Demostrar que todas las palabras son sinónimos entre sí.

[Kechi]

Spoiler: mostrar

Consideremos $a=l_0$, $b=l_1$, $c=l_2$, $d=l_3$, $e=l_4$, $f=l_5$, $g=l_6$, tomando los subíndices en módulo $7$. Con esta notación podemos resumir la primer operación en
$$l_x\rightarrow l_{x+1}l_{x+2}$$
Notemos que podemos convertir cualquier letra $l_x$ en $l_{x+3}$ de la siguiente manera:
$$l_x\rightarrow l_{x+1}l_{x+2}\rightarrow l_{x+2}l_{x+3}l_{x+2}\rightarrow l_{x+3}$$
aplicando la primer operación en $l_x$, en $l_{x+1}$ y luego con la segunda operación. Con esto podemos formar un ciclo
$$l_x\rightarrow l_{x+3}\rightarrow l_{x+6}\rightarrow l_{x+2}\rightarrow l_{x+5}\rightarrow l_{x+1}\rightarrow l_{x+4}\rightarrow l_{x+0}\rightarrow l_{x+3}\rightarrow\cdots$$
que recorre todas las congruencias módulo $7$, es decir que pasa por todas las letras. Concluimos que podemos convertir una letra en cualquier otra a nuestro antojo.

Veamos ahora como partiendo de cualquier palabra $P$ podemos transformarla en otra palabra $Q$:

Primero necesitamos que $P$ tenga una cantidad impar de letras. Si esto no se da aplicamos la primer operación en cualquier letra y con esto agregamos una más.
Lo siguiente será tomar tres letras consecutivas $xyz$, convertir $x$ en $z$ (de ser necesario) y luego aplicar la segunda operación, es decir
$$xyz\rightarrow zyz\rightarrow y$$
Esto reduce la cantidad de letras de $P$ en $2$. Repetimos este proceso hasta que nos quede solo una letra.
Luego hay que tomar una letra al azar de $P$ (la primera vez solo vamos a poder elegir la única que queda) y aplicar la segunda operación. Esto aumenta la cantidad de letras de $P$ en $1$, por lo que repetiremos esto hasta que $P$ y $Q$ tengan la misma cantidad de letras. Hasta ahora tenemos
$$P=o_1o_2o_3o_4\ldots$$
$$Q=v_1v_2v_3v_4\ldots$$
Por último nos queda ir tomando cada letra $o_i$ y convertirla en $v_i$ como vimos al principio, nos va a ir quedando
$$o_1o_2o_3o_4\ldots\rightarrow v_1o_2o_3o_4\ldots\rightarrow v_1v_2o_3o_4\ldots \rightarrow v_1v_2v_3o_4\ldots\rightarrow \cdots$$
Hasta eventualmente convertir todas las letras y lograr que $P$ sea igual a $Q$. $\bigstar$