Title basically says it all

Attachments:
page 1.pdf (349kb)
page 2.pdf (511kb)

Let $s^r$ denote the reverse $s$. Claim: for every good pair $(u, v)$, $$\begin{cases} u=ace, v=c^rb, e=e^r, ac=c^ra, ec^rb=bce\text{ if }|u|\geq|v|;\\ u=ac, v=ec^rb, e=e^r, ace=ec^ra, c^rb=bc\text{ if }|u|\leq|v|. \end{cases}$$for some string $c, e$. (Note that $c, e$ can be empty.) We can see that in the claim: 1. When $|u|=|v|$, the two equations are equivalent since $|e|=0$. 2. The two equations are symmetric. (That is: change $(u, v, a, b)$ in one of the equations to $(v^r, u^r, b, a)$ and it will be equivalent to the other equation.) Proof: induct on $|uv|$. For $|uv|=2$, the only case is $u=a$ and $v=b$, and the claim trivially holds. For $|uv|\geq3$, from the definition, $(u, v)$ is one of the form $(u_0v_0, v_0), (u_0, u_0v_0)$ for a good pair $(u_0, v_0)$. Case 1: $|u_0|\geq|v_0|$. By induction hypothesis, $\exists c_0, e_0$ such that $u_0=ac_0e_0, v_0=c_0^rb, e_0=e_0^r, ac_0=c_0^ra, e_0c_0^rb=bc_0e_0$. Case 1a: $(u, v)=(u_0v_0, v_0)$ ($|u|>|v|$). Let $c=c_0, e=e_0c_0^rb$, we get $u=ac_0e_0c_0^rb=ace, v=c_0^rb=c^rb, e=e_0c_0^rb=bc_0e_0=e^r, ac=ac_0=c_0^ra=c^ra, ec^rb=e_0c_0^rbc_0^rb=bc_0e_0c_0^rb=bce$, the claim holds. Case 1b: $(u, v)=(u_0, u_0v_0)$ ($|u|<|v|$). Let $c=c_0e_0, e=ac_0$, we get $u=ac_0e_0=ac, v=ac_0e_0c_0^rb=ec^rb, e=ac_0=c_0^ra=e^r, ace=ac_0e_0ac_0=ee_0c_0^ra=ec^ra, c^rb=e_0c_0^rb=bc_0e_0=bc$, the claim holds. Case 2: $|u_0|\leq|v_0|$, which is symmetric to Case 1, so similarly the claim holds. $\therefore$ for all good pairs $(u, v)$, the claim holds. $\Rightarrow uv=acec^rb$ for some $c, e$ and $(cec^r)^r=ce^rc^r=cec^r$ is a palindrome.

Let a word be nice if it can be written as $a\gamma b$ where $\gamma$ is a palindrome Induct over the number of operations $n$ ($(u,v)\rightarrow (uv,v)$or$(u,uv)$ is one operation.) $n= 0$ case is trivial. Now, we shall prove that the given statement holds for $n=k+1$ assuming that it holds for $n=k$ WLG, let the first operation make the pair of words $(a,ab)$. Let $\gamma$ denote $ab$ After $k$ operations, we reach a pair $(\alpha,\beta)$. By the induction hypothesis, $\alpha\beta$ is nice in terms of $a,\gamma$. Observe that replacing $\gamma$ by $ab$ is the same as replacing $\gamma$ by $b$ and increasing the sizes of blocks of continuous $a$'s by one. Now it is easy to see that $\alpha\beta$ is good in terms of $a,\gamma$ implies $\alpha,\beta$ is nice in terms of $a,b$ and we are done!

Also Brazil Undergraduate 2021