1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Hw Chu Sep 19 '18 at 23:55
  • $\begingroup$ @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. $\endgroup$ – Na'omi Sep 20 '18 at 13:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.