I'm stuck on the problem №6 from here. The handout deals with the diamond lemma, but I just can't see how it could be applied to the problem.
Alice has a sheet of paper with letter A written on it and Bob has a sheet of paper with letter B. Each second one of them (not necessarily by turns) adds to her/his sheet the word from the sheet of the other (it appends to the end of what is already written on the sheet). Prove that after an hour the word written on Alice's sheet can be cut in two parts in such a way that exchanging the order of the two parts produces the same word written backwards.
The meaning of the words "after an hour" is of course "after arbitrary amount of time".
Example: if Bob does nothing, Alice's word will be of the form ABB...B, which can be transformed to BB...BA
Note that one of two parts can be empty, for example, one possible Alice's word is ABA (first Bob adds A to his sheet, then Alice adds BA to her sheet). As it is already a palindrome, we take one of the parts to be empty.
I suspect that all possible Alice's words are concatenation of two palindromes (If it's true, the claim will follow immediately), but can't really prove it.
Any hints are welcome.
I'm not sure how to use the diamond lemma, but I think the following is a solution (and proves the "union of two palindromes" property as well).
It is based on two ideas:
1) We can consider any of the strings obtained in the problem (on either Alice's or Bob's sheet) as being produced by sequence of substitutions of type (0)$A\to AB$ or type (1)$B \to BA$ (if we record the sequence of (O)Alice's and (I)Bob's moves in the problem, then the sequence of substitutions producing the same result is coded by reversing the string of Os and Is and replacing them with 0s and 1s). Try it! The proof is by induction on the number of moves in the game, and is more or less clear, I think.
Example, as per request: Suppose the game proceeds for 3 seconds, with Alice making a move, then Bob, then Bob again, thus producing the states A, B -> AB, B -> AB, BAB -> AB, BABAB. We encode this as O, I, I. We reverse this to 1,1,0. This means we perform 3 substitution moves, with results: A, B-> A, BA-> A, BAA-> AB, BABAB. This gives the same end result. What I say above is that this is a general fact.
2) Call a sequence of As and Bs "reflective" if it is cyclically equivalent to its reversal. For example the string ABBABB is reflective, since it's reversal is BBABBA and it is cyclically equivalent to original ABBABB. In fact, this is the same as "string can be cut into two pieces, after swapping which it becomes its reversal".
Observe that being reflective is actually equivalent to saying that if we write the letters of the string in a circle, there is a reflection of the circle which leaves it invariant (hence the name).
For example, the string ABBABB looks like this:
or like this:
Finally, I claim that being reflective is preserved by the substitution $A\to AB$ (it follows by "renaming the letters" that it is also preserved by the substitution $B\to BA$). Since the initial string that Alice has (namely, "A") is reflective, the result follows.
To see the claim, simply note that if we view the circle of letters as being given by (possibly empty) segments of Bs separated by As, then to perform the substitution we must simply increases the length of each segment by 1. For the pairs of symmetric segments (those not passing through the symmetry axes) this can clearly be done without ruining the symmetry; if the symmetry axes passes through any segment of Bs then the new B can be added to the segment without breaking the symmetry (either making $|$ into $B \kern{-4pt}|$ or by making $B \kern{-4pt}|$ into $B|B$).
In our example, in the first representation of ABBABB the axis passes through the two As, so intersect no segment of Bs; the two symmetric segments BB and BB are both expanded to BBB:
In the second representation the axis passes through two segments of Bs, and after expansion the picture becomes:
Bonus: Alice's string starts (with an A, not that is matters). Continue along the circle until the reflected A. The resulting string is symmetric with respect to reflection - aka a palindrome. The rest is also symmetric; hence Alice's string is a concatenation of two palindromes.