[tex]va^nb \not\to vba^n[/tex]

[jordan]

Consideriamo un alfabeto composto solo da "a" e "b", e sia $ v $ una stringa di a e b fissata. Presa una parola, ci è consentito:
i) se esistono tre lettere consecutive nelle forma "aba", possiamo cambiarle in "b", e viceversa;
ii) se esistono tre lettere consecutive nelle forma "bba", possiamo cambiarle in "a", e viceversa.

Mostrare che partendo dalla parole $ va^nb $, non possiamo arrivare alla parola $ vba^n $, con le trasformazioni di sopra.



Ps. La notazione $ a^n $ indica una stringa di n lettere a consecutive

[dario2994]

aba-> abbaa -> aababaa -> aabba -> aab
E questo contraddice la tesi.
Probabilmente il testo è sbagliato... ma anche così è relativamente interessante il problema:

Bonus del re: Con le trasformazioni b<->bba e b<->aba; trovare il minimo numero $N$ tale che se prendo $N$ stringhe di a,b di lunghezza minore di $2012$ di sicuro esiste una di queste che può essere trasformata in un'altra di queste.

[jordan]

Probabilmente il testo è sbagliato...

Scusami, sono un idiota: la seconda trasformazione va in (a) altrimenti non avrebbe avuto senso mettere i) e ii)..

Ps. Il caso $v=\emptyset$ e' stato assegnato anni fa come un tst bulgaro..

[dario2994]

Allora data una stringa $ s $ compio queste operazioni:
Step 1: Le sequenze di b consecutive ($b^n$) se sono di lunghezza pari le cancello, altrimenti le sostituisco con 'b'.
Step 2: Siano $a_1,a_2,\dots , a_k$ le lunghezze dei blocchi di 'a' consecutive rimasti (contando l'eventuale blocco vuoto prima della prima 'b', e l'eventuale blocco vuoto dopo l'ultima 'b'). Allora dico che $f(s)=a_1-a_2+a_3\dots \pm a_k$.

Giusto per far capire se $s=babbbabbaaababbabbb$, dopo lo step 1 diventa $babaaaabaab$, allora ottengo $f(s)=0-1+4-2+0=1$.

Si verifica più o meno facilmente che in effetti le 2 mosse di cui dispongo non modificano $f(s)$ che quindi è invariante. (insomma sapendo chi è $f$ è proprio facile da verificare!).

Ora resta solo da vedere che $f(vba^n)\not= f(va^nb)$. E anche questo è un attimo, basta distinguere in 2 casi in base a come finisce $v$ (se per 'a' o per 'b'), e ottenere che $f(vba^n)=f(v)\pm n$ e $f(va^nb)=f(v)\mp n$. (con i segni in base a come finisce $v$).

E propongo anche questo:

Bonus della regina:
Con le trasformazioni a<->bba e b<->aba; trovare il minimo numero N tale che se prendo N stringhe di a,b di lunghezza minore di 2012 di sicuro esiste una di queste che può essere trasformata in un'altra di queste.

E ci metto anche 1 hint:

Testo nascosto:

Date 2 stringhe $s_1,s_2$ entrambe non vuote è possibile trasformare l'una nell'altra sse $f(s_1)=f(s_2)$ e la parità del numero di $b$ è uguale in entrambe.