# $m$-equivalence of words on the alphabet $\{a,b\}$

I am dealing with the test of the OBM (Brasilian Math Olympiad), University level, 2017, phase 2.

As I've said at others topic (questions 1, 2, 3, 4 and 6), I hope someone can help me to discuss this test.

The question 6 says:

We'll consider here words on the alphabet $$\{a,b\}$$: sequences of $$a$$'s and $$b$$'s with finite length. We write $$u\leq v$$ if $$u$$ is a subword of $$v$$, it means, we can get $$u$$ from $$v$$ by erasing some letters of $$v$$ (e.g.: $$aba\leq abbab$$). We say that a word $$u$$ discerns the words $$x$$ and $$y$$ if $$u\leq x$$ but it's NOT true that $$u\leq y$$ or vice versa (it's NOT true that $$u\leq x$$, BUT $$u\leq y$$).

Let be $$m$$ and $$l$$ positive integers. We say that two words $$x$$ and $$y$$ are $$m$$-equivalents if there is NOT $$u$$ with length $$\leq m$$ that discern $$x$$ and $$y$$.

a) Prove that if $$2m\leq l$$, so there are two different words $$x$$ and $$y$$ with length $$l$$ that are $$m$$-equivalents.

b) Prove that if $$2m>l$$, so two different words $$x$$ and $$y$$ with length $$l$$ cannot be $$m$$-equivalents.

Well, I've had some ideas and would like to discuss. I'll use the notation $$\sim^m$$ to indicate $$m$$-equivalences.

a) Result 1: $$\underbrace{baba...baba}_{2m\text{ letters}}\sim^m \underbrace{baba...baba}_{2(m+1)\text{ letters}}$$

Proof by induction:

To $$m=1$$

$$ba\sim^m baba$$, because the unique subwords of $$ba$$ and of $$baba$$ or the same: $$b$$ and $$a$$

To $$m=2$$

$$baba\sim^m bababa$$, because the unique subwords of length $$2$$ of $$baba$$ and of $$bababa$$ or the same: $$bb,ba,ab$$ and $$aa$$.

Consider $$\underbrace{baba...baba}_{2m\text{ letters}}\sim^m \underbrace{baba...baba}_{2(m+1)\text{ letters}}$$

If a word of length $$m+1$$ is a subword of $$\underbrace{baba...baba}_{2(m+1)\text{ letters}}$$, obviously is a subword of $$\underbrace{baba...baba}_{2(m+2)\text{ letters}}$$.

Conversely, if is subword of $$\underbrace{baba...baba}_{2(m+2)\text{ letters}}$$,

(i) Is on there $$\underbrace{\boxed{baba...ba}ba}_{2(m+2)\text{ letters}}$$ or on $$\underbrace{ba\boxed{ba...baba}}_{2(m+2)\text{ letters}}$$, so is a subword of $$\underbrace{baba...baba}_{2(m+1)\text{ letters}}$$;

or (ii) There's some letters from the first $$ba$$ in the beginning and from the last $$ba$$ in the ending. The others letters (at most $$m-1$$) are on $$\underbrace{ba\boxed{ba...ba}ba}_{2(m+2)\text{ letters}}$$, it means, on a word of type $$\underbrace{baba...baba}_{2m\text{ letters}}$$. By the hypothesis, this part is on a word of type $$\underbrace{baba...baba}_{2(m-1)\text{ letters}}$$, so the whole subword in on $$ba\underbrace{baba...baba}_{2(m-1)\text{ letters}}ba=\underbrace{baba...baba}_{2(m+1)\text{ letters}}$$

===========================

Well, let $$2m\leq l$$ and the words of legh $$l$$ of type $$abababab...$$ and $$babababa...$$. Consider $$l$$ even and the case odd is similar. So, $$abababab...ab$$ and $$babababa...ba$$.

They are $$m$$-equivalents. In fact, consider a subword $$x$$ of length $$m$$ to $$ababab...ab$$. If it's in the part $$\boxed{ababab...a}b$$ or in the part $$a\boxed{babab...ab}$$, so is on $$babababa...ba$$. If not, it is of type $$a\boxed{~~}b$$ where the $$m-2$$ letters of center is on $$\underbrace{baba...baba}_{\text{at least } 2(m-1)\text{ letters}}$$.

By the result 1, this center is on $$\underbrace{baba...baba}_{2(m-2)\text{ letters}}$$, so $$x\leq \underbrace{ababa...babab}_{2(m-1)\text{ letters}}\leq \underbrace{bababa...ba}_{\text{at least }2m\text{ letters}}$$.

The other implication is similar.

b) If $$2m>l$$, consider a word of length $$l$$ and note that or there is less than $$m$$ letters $$a$$ or less than $$m$$ letters $$b$$. Consider less $$a$$ and take subwords of length $$m$$ with all the $$a$$'s of the initial word. We can put $$b$$'s to "fill" the subwords indicating where the $$b$$'s are neighbors of the $$a$$'s. All of the subwords of this type will define all the neighborhoods, so will define whole word. Thus, it's unique, it means, there's no two different words of length $$l$$ that are $$m$$-equivalents.

What do you think?

Edit (September, 21)

As you can see at comments following, my initial ideia to b) is not correct. I think this type of subwords will define the blocks of $$a$$'s or $$b$$'s and can give us too the amount of $$a$$'s or $$b$$'s, but cannot define the word in some cases. I'd like to post here an example:

1) $$bbaba$$

Subwords of length $$3$$:

$$bba,bbb,baa,bab,aba$$

2) $$babba$$

Subwords of lenght $$3$$:

$$bba,bbb,baa,bab,aba,\boxed{abb}$$

It's correct?

I thinked this is interesting, because the subwords of length $$\leq 3$$ of the first word cannot discern it of the second word, but just a subword of this last.

• I do not quite understand your part (b). For instance, if $m=3$ and $l=5$, and you are trying to distinguish baabb and bbaab. it seems that your distinguishing word has to consist of 2 a's and 1 b. However, aba does not discern both words; while baa and aab discern both words. So you need some word containing only one a (like bba) to distinguish them. – Hw Chu Sep 19 '18 at 23:55
• @HwChu, Really! In that way I got the 'neighborhoods', but not the amount of $b$'s in each of them... Thanks for the rich pointing... I'll stay trying. – Na'omi Sep 20 '18 at 13:37