Maths Olympiad Prep

Library / /394 of 520

Combinatorics Difficulty 7.3 National olympiad, round 2 Prove it

In a remote island, a language in which every word can be written using only the letters aa, bb, cc, dd, ee, ff, gg is spoken. Let's say two words are [i]synonymous[/i] if we can transform one into the other according to the following rules:

i) Change a letter by another two in the following way: abc, bcd, cde, def, efg, fga, gaba \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, dfdfdfd \rightarrow f.

Show that all words in this language are synonymous.

Solution

1. Transforming Double Letters:
- Consider the sequence of transformations for double letters:
aabcbcbb aa \rightarrow bcbc \rightarrow bb
This shows that the double letter "aa" can be transformed into "bb". By applying the transformation rules cyclically, we can see that every double letter is equivalent to every other double letter. For example:
bbcdcdcc bb \rightarrow cdcd \rightarrow cc
ccdededd cc \rightarrow dede \rightarrow dd
ddefefee dd \rightarrow efef \rightarrow ee
eefgfgff ee \rightarrow fgfg \rightarrow ff
ffgagagg ff \rightarrow gaga \rightarrow gg
ggababaa gg \rightarrow abab \rightarrow aa
This completes the cycle, showing that any double letter can be transformed into any other double letter.

2. Transforming Single Letters:
- Consider the sequence of transformations for single letters:
abccddeccceeeceeceded a \rightarrow bc \rightarrow cdde \rightarrow ccce \rightarrow eece \rightarrow ec \rightarrow ede \rightarrow d
This shows that the letter "a" can be transformed into the letter "d". By applying the transformation rules cyclically, we can see that every letter is equivalent to every other letter. For example:
bcddeefddffdff b \rightarrow cd \rightarrow deef \rightarrow ddf \rightarrow fdf \rightarrow f
cdeeffgefggfgg c \rightarrow de \rightarrow effg \rightarrow efg \rightarrow gfg \rightarrow g
deffggafgagaaa d \rightarrow ef \rightarrow fgga \rightarrow fga \rightarrow gaa \rightarrow a
efggabgbbabb e \rightarrow fg \rightarrow gab \rightarrow gb \rightarrow bab \rightarrow b
fgaabbcabcbccc f \rightarrow ga \rightarrow abbc \rightarrow abc \rightarrow bcc \rightarrow c
gabbccdbcdcddd g \rightarrow ab \rightarrow bccd \rightarrow bcd \rightarrow cdd \rightarrow d
This completes the cycle, showing that any single letter can be transformed into any other single letter.

3. Algorithm to Transform Words:
- Given two words, we can lengthen the shorter word by adding equivalent letters until both words are of the same length.
- Once the words are of the same length, we can change the letters accordingly using the transformations described above.

Conclusion:
Since we have shown that any double letter can be transformed into any other double letter and any single letter can be transformed into any other single letter, it follows that all words in this language are synonymous.

\blacksquare

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.