I think the answer is "no", but I'm really not sure about the solution. If the first word can't be turned into the second word by a series of transformations which include the initial transformations, then it can't be done with the given transformations either. I considered the transformations: $bb\leftrightarrow e,\ aaa\leftrightarrow e,\ aba\leftrightarrow b$, where $e$ is th identity, i.e. the null word. As you can already see, I considered $a,b$ as elements of a group with identity $e$ s.t. $a^3=b^2=e,\ bab=a^2=a^{-1}$. I consider two words equal if they can be obtained from one another by the three given transformations, i.e. if their corresponding elements in the group are equal. We need to show that the two given words aren't equal. We consider the smallest group generated by $a,b$. This is $S_3$. With this new, extended set of transformations the two given words are equal iff $aab=baa$, because $a^{2001}=e$, so it can be eliminated by the transformation $a^3\rightarrow e$. Take $a=\left (\begin{array}{ccc}1&2&3\\ 2&3&1\end{array}\right ),\ b=\left (\begin{array}{ccc}1&2&3\\ 2&1&3\end{array}\right )$. It's easy to see that $aba=b$ and $a^2b\neq ba^2$. I think this solves the problem, but I'm still not sure about the method. I keep thinking that maybe I'm missing something (I'm not sure about the equivalence: two words can be obtained from one another $\Leftrightarrow$ the corresponding elements of the group are equal). What do you think?

Yes, your solution is correct. The original proof is very simple: just note that the number of $a$'s on odd positions remains invariant modulo 2 under the given transformations, whereas this is not the case in the given two words. My own solution goes as follows. We will prove that, for any $n \geq 1$, it is not possible to obtain $ba^n$ from $a^nb$. Consider the group $G$ with presentation \[ G = \langle x,y \, | \, y^2 = (xy)^2 = 1 \rangle. \] In this group, we have the relations \[ y^2x = x, xyx = y. \] Assume now that $ba^n$ can be reached from $a^nb$ after finitely many transformations of the form $aba \leftrightarrow b$ or $a \leftrightarrow bba$. Then, $yx^n = x^ny$, because the relations $xyx = y$ and $x = yyx$ are true in $G$. Thus, \[ yx^n = x^ny. \] By performing a right multiplication by $x$ to this identity, we have \[ yx^{n+1} = x^nyx = x^{n-1}(xyx) = x^{n-1}y. \] If we multiply from the right by $x$ again, we get \[ yx^{n+2} = x^{n-1}yx = x^{n-2}(xyx) = x^{n-2}y. \] By induction, we have $yx^{n+k} = x^{n-k}y$ for all $k \geq 0$, so, for $k=n$, we get \[ yx^{2n} = y \, \Leftrightarrow \, x^{2n}=1. \] This shows that the order of $x$ is finite. On the other hand, we will show that the presentation (1) directly implies that $|x|= \infty$, which will finish the proof by obtaining a contradiction. Let us make a change of basis by letting $g=y$ and $h=yx^{-1}$. Then, $G$ also has the presentation \[ G = \langle g,h \, | \, g^2 = h^2 = 1 \rangle. \] A word of the form $ghgh \cdots gh$ cannot be reduced to a word of smaller length by using the generator relations $g^2=h^2=1$. Therefore, for each $k \in \NN$, $x^{-k} = (gh)^k \neq 1$, which means that the order of $x$ is infinite. This obtains the desired contradiction, and the proof is complete. In fact, this solution (together with grobber's and the original as well) shows, more generally, that, for any word $v$, we cannot reach $va^nb$ from $vba^n$.

Classical russian solution. Let $a(x)=x+1$ and $b(x)=-x$. Then $a\circ b\circ a=b$ and $b\circ b\circ a=a$; moreover $a\circ...\circ a\circ b(x)=-x+2003$ and $b\circ a\circ...\circ a(x)=-x-2003$. That's all.

i guess my group theory isn't strong - how do you change the basis? I don't understand, what conditions and steps are needed? Also I don't understand the first proof oops.

Please, write for whom your question is addressed.

well, just anyone who passes by and tell me about bases.... as this thread is very old

What bases are you referring to?

change of basis. why is $h^2=e$ (from the second group proof) and$bab=b$ (from the first group proof)? unless I am just missing something oops.

I did not read the second proof, and regarding the first proof, nobody said $bab=b$.

For the second proof, we have $h^2=(yx^{-1})^2 = (y^{-1}x^{-1})^2=(xyxy)^{-1}=1$, where the second equality follows from $y^2=1$ and the last from $(xy)^2 = 1$.

And in the first proof, if what you're asking is how you get from $aba=b$ to $bab=a^2$, just notice that $aba=b\iff (ab)^2=1\iff aba=b^{-1}=b$.

Myth wrote: Classical russian solution. Let $a(x)=x+1$ and $b(x)=-x$. Then $a\circ b\circ a=b$ and $b\circ b\circ a=a$; moreover $a\circ...\circ a\circ b(x)=-x+2003$ and $b\circ a\circ...\circ a(x)=-x-2003$. That's all. How did you find that pair of functions a,b? (Unless this one was "well known in Russia"). Added in editing: actually it may not be so hard. You just need to look for a representation of aba = b and bba = a, there is obviously a finite dimensional example (by setting various other words to 0) and if dimension is 2 or 3 you should get something like the above. Is that how you did it?

I was searching for geometric interpretation, but the problem is so straightforward, that geometrical transformations I found are simply translation and simmetry, hence I wrote them in a functional way. I remember I was solving similar problem many years ago, and my supervisor told me about this possible approach.

Saw a proof along these lines a while ago, so I thought I might post a write up here. A truly fantastic problem, although I do believe that this should have been more user friendly to those who don't know any group theory yet. We claim the answer is no. To do this though, we will need to impose even more conditions than what was given in the problem statement. This is perfectly fine though, since if we can prove the claim impossible using more restrictions, we can certainly disprove the original claim as well. To wit, we are proving something stronger that will be significantly easier to prove so don't get mad about what we're about to do To begin, we add inverses. We see that \begin{align*} bba=a&\implies b^2=e \\ b=aba &\implies e=abab^{-1}.\\ \end{align*}So we can construct the group presentation $G=\langle a,b~|~abab^{-1},b^2\rangle=\langle a,b~|~abab,b^2\rangle$ since $b^2=e\implies b=b^{-1}$. Finally, we add the relation $a^n=e$ to $G$ to get $$G=\langle a,b~|~abab^{-1},b^2,a^n\rangle.$$Thus it suffices to observe whether or not the equation $$\underbrace{a\ldots ab}_{2003~\text{many times}}=\underbrace{ba\ldots a}_{2003~\text{many times}}\implies a^{2003}b=ba^{2003}$$is true under this presentation. Since this presentation behaves like the Dihedral Group, we can pass $a$ through $b$ to get $$a^{2003}b=ba^{2003}\implies ba^{-2003}=ba^{2003}\implies b=ba^{4006}\implies e=a^{4006}.$$To prove that this is impossible, consider $D_3$ (the motivation here is that $n$ isn't a divisor of $2003$). The Dihedral Group $D_3$ has generators $a$ and $b$ and satisfy all $4$ conditions given in the original problem statement. Hence, if any two words are equivalent under the relations given in the problem statement, they must create the same words in $D_3$. This means we get $$a^{2003}b=a^2b\in D_3~\text{and}~ba^{2003}=ba^2=ba\in D_3$$but we see that $a^2b\ne ba$ in $D_3$ which means that the condition proposed is impossible $\square$