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.
Problem
Source: Central American Olympiad 2007, Problem 4
Tags: algorithm
t0rajir0u
12.06.2007 07:26
Edit: Hidden.
First, consider the sequence of transformations
$aa \to bcbc \to bb$
Applied cyclically, every double letter is equivalent to every other double letter. Next, consider the sequence of transformations
$a \to bc \to cdde \to ccce \to eece \to ec \to ede \to d$
Applied cyclically, every letter is equivalent to every other letter. Then the algorithm is trivial; lengthen the shorter word until it is the same length as the longer word, then change the letters accordingly.
Altheman
12.06.2007 07:56
This would be cool to do with graph theory. Just a note, t0rajir0u's 2nd transformation finishes the problem only because we have 7 letters, it moves 3 to the right, and (7,3)=1, so we can reach each other letter. If we had 6 letters, that process would not necessarily work.