Olympiad of May 2017

Question

Ababa plays a game with the letters of his name: If there is an AB, you can replace it with BAA. If there are two consecutive Bs, you can delete them. If there are three consecutive A's you can delete them. If at the beginning of the game there is the ABABABAABAAB sequence, find the least amount of letters that can be in the game at any time and explain why there can be no less.

SOLUTION (not complete)

Let's see that Ababa can get a 2-letter word as follows: ABABABAABAAB → BAAABABAABAAB → BBABAABAAB → ABAABAAB → BAAAABAAB → BABAAB → BBAAAAB → BBAB → AB

1) There is at least one B: Let's see that making move 1 or 3 does not change the amount of B's, and that when making move 2 the amount of B's ​​changes in 2, from this we have that the amount of B always maintains its parity and as it starts with 5 B's then B amount is always odd and we have what we wanted.

2) I don't know how to prove that there must be at least 1 A.

Answer 1

This is easy to solve if you are familiar with the group $S_3$ of all ($3!=6$) permutations of a $3$-element set. If the set is $\{a,b,c\}$, define the permutations $A$ and $B$ so that:

$$A=\begin{pmatrix}a&b&c\\b&c&a\end{pmatrix}$$ $$B=\begin{pmatrix}a&b&c\\b&a&c\end{pmatrix}$$

Also, define the "multiplication" of permutations as applying them in turn, first the one on the "right" side, then the one on the "left" side. Thus, for example:

$$AB=\begin{pmatrix}a&b&c\\c&b&a\end{pmatrix}$$ $$BAA=\begin{pmatrix}a&b&c\\c&b&a\end{pmatrix}$$

so you can see that $AB=BAA$. You may also want to define the permutation:

$$I=\begin{pmatrix}a&b&c\\a&b&c\end{pmatrix}$$

and, for it, it is valid that $IX=XI=X$ for any permutation $X$.

We will also use the symbols for exponentiation as it would come naturally: $A^1=A, A^2=AA, A^3=AAA$ etc. (similar for $B$), and you can also write $A^0=I$. As it happens, $A^3=AAA=I$ and also $BB=B^2=I$.

Now, you can see that, if two sequences of letters can be transformed to each other, then the corresponding permutations obtained by "multiplying" the permutation are the same. (You may always insert and remove any $I$'s between any two letters at any time, so you can treat an empty sequence of letters the same as if it was $I$.)

In other words, you have found an invariant that stays the same when you modify your sequence, and this invariant is not a number but a permutation, from $S_3$. (Incidentally, the parity of the number of $B$'s, which is also the invariant, is called the parity of the permutation.)

---

So, what you have done already is a proof that $ABABABAABAAB=AB$ as a permutation. You need to show that you cannot have any fewer than two letters. For that, note that $AB$, as a permutation, is a different from the permutations $A$, $B$ and $I$.

Answer 2

I found the following solution (not mine) but I don't understand it. Could someone restate the solution in a simpler way, please.

Solution:

2) There is at least one A:

Let X be a possible word, and let's call the B's as $B_1, B_2, ..., B_i$ from left to right, and let's call $x_1, x_2, ..., x_{i + 1}$ the amount of A's between two consecutive B's (or the left of the first ($x_1$) or the right of the last $(x_{i + 1}))$ in that order, now consider $S = \sum_{j=1}^{i+1}=(−1)^j x_j$ in (mod3), it is clear that we start with S = 2 in the first word, now let's see that S does not vary with any play, this because with move 1 and 3 the sum varies in 3 or -3 and as S− is in (mod3) does not vary , make play 2, then as 2 B's are eliminated in a row (say Br and Br + 1) then xr is added to xr + 2 and being xr + 1 = 0 the sum does not vary remains (mod 3). So S does not vary (mod 3) that is to say after any number of plays S≡2 $(mod 3)$ which would not be possible if the amount of A's were 0, since in this case S≡0 $(mod 3)$ and there would be contradiction, then there is always at least one A after any number of moves made by $Ababa$ then there is always at least one A and at least one B with what we would have that the minimum number of letters that can be in the game at any time is 2, with the initial example the problem ends.

Answer 3

I will try to clarify the proof you posted as your own answer. Would it help if you looked at your concrete example?

For the given word $ABABABAABAAB$, i.e.

$$\{\text{one } A\}B\{\text{one }A\}B\{\text{one }A\}B\{\text{two }A's\}B\{\text{two }A's\}B\{\text{zero }A's\}$$

write down the number made up as a sum of the number of $A$'s between $B$'s, with alternating signs: $$-1+1-1+2-2+0=-1$$

The allowed operations change that number by $0$ or $\pm 3$ - the rest of the proof is about proving that to be true in all cases. Therefore, taken $\pmod 3$, that number is an invariant.

In your example, you start with the number $-1\equiv 2\pmod 3$, you must end with another number $\equiv 2\pmod 3$. However, note that any sequence made up purely of $B$'s has that number equal to $0$ and so you can never end up with only $B$'s.