Starting with a string AB. Is it possible to obtain BA following these rules?

Question

Starting with a string AB. One is allowed to add, or remove any occurrence of AAA, BB, or ABAB anywhere in the string . Is it possible to obtain BA?

My attempt at proof of impossibility below:

In the proof, I will write about "creating a string X from scratch". That means applying a sequence of the rules to the empty string and ending up with X.

Note, for example, that it is possible to create BABA from scratch. $ -> BB -> BABABB -> BABA$

Also note, that since all the rules can be applied in reverse, if one can given a string A, produce a string B - one can also given a string B, produce string A.

One consequence of this is that if you can create a string X from scratch, you can also "destroy it" i.e. apply a sequence of operations to a string containing X until you get an identical string not containing X.

It is impossible, however, to create string B from scratch. After all, all the rules increment, or decrement the number of B's by $2$ so, starting with no B it is impossible to arrive at one B.

More generally, starting with a string with $n$ B's it is impossible to end up with a string containing $n+1$ or $n-1$ B's.

What about A? Can one create A from scratch? First of all, if one could create A from scratch than the puzzle would be solved. $AB -> B - > BA$

More importantly though, if you can solve the puzzle, you can create A.

Start with $AB -> ABABAB -> AABBAB -> AAAB -> B$.

This took AB and ended up with B, destroying A in the process. Of course one can also create A if the process is reversed.

Thus, by contrapositive, if A cannot be created, the puzzle cannot be solved.

There are only two ways one could conceivably create A. One of them is use AAA rule then do some magic and then remove ABAB.

The other way is to use ABAB twice getting ABABABAB then do some magic and subtract AAA.

The other ways are just simple variants of these.

Both of these are impossible because, in ABAB the A's are one B apart this distance cannot be reduced. None of the rules can be used to decrease this distance as you can just insert strings and remove them at will but reducing the distance would amount to the transformation $ABA -> AA$ which is impossible (as proved earlier).

So the A cannot be created from scratch and thus the puzzle cannot be solved.

Answer 1

As for the proof-verification, let me try to swallow your idea.

• A string is said to be created from scratch if it can be created from the empty string $\varnothing$ by applying the rules finitely many times.

• $B$ cannot be created from scratch because each rule preserves the parity of the number of $B$'s, and $B$ and $\varnothing$ have different parities.

• If $BA$ can be obtained from $AB$, then $A$ can be created from scratch by

  $$ \varnothing \to AAA \to AABBA \to ABABA \to A $$

  So it suffices to prove that $A$ cannot be created from scratch.

Now it is not entirely transparent to me how your argument on the impossibility of $\varnothing \to \cdots \to A$ works. Perhaps this is because I am not thinking hard enough to grasp the idea, but in any case, supplying some details seems no harm to the argument.

---

Meanwhile, here is another proof of the impossibility: Let $f_A(z) = 1 - \frac{1}{z}$ and $f_B(z) = 1 - z$. For each string $a_1\cdots a_n$ with $a_i \in \{A, B\}$, we define

$$ \phi(a_1\cdots a_n) = f_{a_1}\circ \cdots \circ f_{a_n}, \qquad \phi(\varnothing) = [z \mapsto z], $$

where $\varnothing$ is the empty string. Then we easily find that

1. For two strings $S_1, S_2$ and their concatenation $S_1 S_2$, we have $\phi(S_1 S_2) = \phi(S_1)\circ\phi(S_2)$.

2. $\phi(AAA) = \phi(BB) = \phi(ABAB) = \phi(\varnothing)$.

So the value of $\phi$ does not change when we apply the rules to the string, hence the value of $\phi$ is an invariant. But since

$$\phi(AB) = \left[ z \mapsto \frac{z}{z-1} \right], \qquad \phi(BA) = \left[ z \mapsto \frac{1}{z} \right], $$

we have $\phi(AB) \neq \phi(BA)$. Therefore $BA$ cannot be obtained from $AB$ by the rules.

Answer 2

A quick proof using group theory:

Construct group $G=\langle A,B\mid A^3=1,B^2=1,ABAB=1\rangle$.

Showing that $BA$ cannot be obtained from $AB$ using the rules specified in the questions is equivalent to showing that within $G$, $AB\neq BA$.

The latter follows directly from the fact that the dihedral group of order $6$, $D_3$, has presentation $\langle r,a\mid r^{3}=1,a^{2}=1,ara=r^{{-1}}\rangle $, and that $ar$ and $ra$ are distinct elements of $D_3$.

Q.E.D.

P.S. I can add the proof that $D_3$ has presentation $\langle r,a\mid r^{3}=1,a^{2}=1,ara=r^{{-1}}\rangle $ if needed.