The Ababi alphabet consists of letters A and B, and the words in the Ababi language are precisely those that can be formed by the following two rules: 1) A is a word. 2) If s is a word, then $ s \oplus s$ and $ s \oplus \bar{s}$ are words, where $ \bar{s}$ denotes a word that is obtained by replacing all letters A in s with letters B, and vice versa; and $ x \oplus y$ denotes the concatenation of x and y. The Ululu alphabet consists also of letters A and B and the words in the Ululu language are precisely those that can be formed by the following two rules: 1) A is a word. 2) If s is a word, $ s \oplus s$ and $ s \oplus \bar{s}$ are words, where $ \bar{s}$ is defined as above and $ x \oplus y$ is a word obtained from words x and y of equal length by writing the letters of x and y alternatingly, starting from the first letter of x. Prove that the two languages consist of the same words.
Problem
Source: Final Round Grade 12 Pro 5
Tags: induction, combinatorics unsolved, combinatorics
30.07.2008 22:09
Both languages seem to consist of all possible strings starting with $ A$ and having length $ 2^n$. That follows by induction, since for Ababi and $ n=0$ this is clearly the case. Then for words of length $ 2^{n}$ consider their first character (A) and the remaining block of $ 2^{n}-1$ characters (which by assumption ranges through all possible strings of As and Bs); then $ s$ can range over all strings of length $ 2^{n}$ starting with $ A$, while $ \bar{s}$ can range over all strings of length $ 2^{n}$ starting with $ B$. Then $ s \oplus s$ constructs all words of form $ A\underbrace{\cdots}_{2^{n}-1} A \underbrace{\cdots}_{2^n-1}$, while $ s \oplus \bar{s} = A\underbrace{\cdots}_{2^{n}-1} B \underbrace{\overline{\cdots}}_{2^n-1}$; which together covers all strings of length $ 2^{n+1}$ beginning with $ A$. The Ululu language follows similarly.
03.08.2008 18:17
azjps wrote: Both languages seem to consist of all possible strings starting with $ A$ and having length $ 2^n$. That follows by induction, since for Ababi and $ n = 0$ this is clearly the case. This is why the word "clearly" should be used as absolutely sparingly as possible. How, exactly, do you plan to get the word AABA (or AAAB, ABAA, and ABBB)? (You only get $ 2^{n - 1}$ words of length $ 2^n$ with these rules, not the $ 2^{2^n - 1}$ you seem to be imagining .) I'm going to use $ \otimes$ for the second operation (and if the original problem uses the same notation for two different operations, that's really bad form). For words of length 1, it's trivial. Take a word $ s$ in language $ U$, and assume that $ s = t \oplus t'$ for some $ t'$ equal to either $ t$ or $ \overline{t}$. Let $ s^*$ be equal to either $ s$ or $ \overline{s}$. Then $ s \otimes s^* = (t \oplus t') \otimes (t \oplus t')^* = (t \otimes t^*) \oplus (t \otimes t^*)' \in A$, where the last step is by the induction hypothesis. Then $ U \subseteq A$. A nearly identical computation can be done in the other direction, giving us our result.