words

Valentin Vornicu

In a word formed with the letters $a,b$ we can change some blocks: $aba$ in $b$ and back, $bba$ in $a$ and backwards. If the initial word is $aaa\ldots ab$ where $a$ appears 2003 times can we reach the word $baaa\ldots a$ , where $a$ appears 2003 times.

**Posted:** Mon May 17, 2004 12:54 pm

_________________
We all use math everyday: to forecast weather, to tell time, to handle money; we also use math to analyze crime, reveal patterns, predict behavior. Using numbers we can solve the biggest mysteries we know.

grobber

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&am...$ . 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?

**Posted:** Fri May 21, 2004 12:47 am

vess

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

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,

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$ .

**Posted:** Sun May 23, 2004 6:37 am

Myth

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.

**Posted:** Fri Jul 02, 2004 9:08 am

_________________
Myth is out of here

kueh · Riemann Hypothesis Offline Joined: 26 May 2004 Posts: 417

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.

**Posted:** Mon Jan 31, 2005 10:12 am

Myth

Please, write for whom your question is addressed. Confused

**Posted:** Mon Jan 31, 2005 10:19 am

_________________
Myth is out of here

kueh · Riemann Hypothesis Offline Joined: 26 May 2004 Posts: 417

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

**Posted:** Mon Jan 31, 2005 11:19 am

grobber

What bases are you referring to? Confused

**Posted:** Mon Jan 31, 2005 11:25 am

kueh · Riemann Hypothesis Offline Joined: 26 May 2004 Posts: 417

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.

**Posted:** Mon Jan 31, 2005 12:53 pm

grobber

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

**Posted:** Mon Jan 31, 2005 1:10 pm

vess

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$ .

**Posted:** Mon Jan 31, 2005 1:18 pm

grobber

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$ .

**Posted:** Mon Jan 31, 2005 1:25 pm

fleeting_guest · Yang-Mills Theory Offline Joined: 14 Dec 2004 Posts: 900

**Posted:** Thu Feb 03, 2005 3:22 pm

Myth

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.

**Posted:** Thu Feb 03, 2005 9:14 pm

_________________
Myth is out of here