Problem

Source: Central American Olympiad 2007, Problem 4

Tags: algorithm



In a remote island, a language in which every word can be written using only the letters $a$, $b$, $c$, $d$, $e$, $f$, $g$ is spoken. Let's say two words are synonymous if we can transform one into the other according to the following rules: i) Change a letter by another two in the following way: \[a \rightarrow bc,\ b \rightarrow cd,\ c \rightarrow de,\ d \rightarrow ef,\ e \rightarrow fg,\ f\rightarrow ga,\ g\rightarrow ab\] ii) If a letter is between other two equal letters, these can be removed. For example, $dfd \rightarrow f$. Show that all words in this language are synonymous.