Czech-Polish-Slovak Mathematics Competition

We shall prove the claim by induction with respect to $n$. The claim is trivial for $n = 2$ (we can get the desired 2-tuple after a single step $(a, b) \rightarrow (ab, ab)$) and $n = 4$ (we can follow the scheme $(\underline{a}, \underline{b}, c, d) \rightarrow (ab, ab, \underline{c}, \underline{d}) \rightarrow (\underline{ab}, ab, \underline{cd}, cd) \rightarrow (abcd, \underline{ab}, abcd, \underline{cd}) \rightarrow (abcd, abcd, abcd, abcd)$).

To start the induction, we shall prove the claim also for $n = 6$. The algorithm begins with the 6-tuple $(a, a, a, a, b, b)$ – this form can be achieved thanks to the fact the claim is true for $n = 2$ and $n = 4$ (we can operate on the left 4-tuple and then independently on the right 2-tuple). To equalize all six numbers, perform the following steps:
$$\begin{aligned} (a, a, a, \underline{a}, \underline{b}, b) &\rightarrow (a, a, \underline{a}, \underline{ab}, ab, b) \rightarrow (a, a, a^2b, \underline{a^2b}, \underline{ab}, b) \rightarrow (a, a, \underline{a^2b}, a^3b^2, a^3b^2, \underline{b}) \rightarrow \\ &\rightarrow (\underline{a}, \underline{a}, \underline{a^2b^2}, a^3b^2, a^3b^2, \underline{a^2b^2}) \rightarrow (a^3b^2, a^3b^2, a^3b^2, a^3b^2, a^3b^2, a^3b^2) \end{aligned}$$

Now, suppose the claim is true for all even $n < 4k + 4$ (with $k \ge 1$). It suffices to prove the claim also for $n = 4k + 4$ and $n = 4k + 6$. The procedure for $n = 4k + 4$ is obvious: we first equalize the first $2k + 2$ numbers using the induction hypothesis, and then equalize the last $2k + 2$ numbers. We get an $n$-tuple of the form
$$\underbrace{(a, \dots, a)}_{2k+2}, \underbrace{(b, \dots, b)}_{2k+2}$$

and then perform $2k + 2$ steps to get $(ab, \dots, ab)$ (choosing one $a$ and one $b$ in each step).

For $n = 4k+6$, we first use the induction hypothesis for $n = 2k+2$ and $n = 2k+4$ to get
$$\underbrace{(a, \dots, a)}_{2k+2} \underbrace{, b, \dots, b)}_{2k+4}.$$
Now we perform $2k$ steps, always choosing one $a$ and one $b$, to obtain
$$(a, a, \underbrace{ab, \dots, ab)}_{4k}, b, b, b, b).$$
After erasing each $a$ with one $ab$ we get
$$(a^2b, a^2b, a^2b, a^2b, \underbrace{ab, \dots, ab)}_{4k-2}, b, b, b, b),$$
and after pairing each $b$ with one $a^2b$ we have
$$(a^2b^2, a^2b^2, a^2b^2, a^2b^2, \underbrace{ab, \dots, ab)}_{4k-2}, a^2b^2, a^2b^2, a^2b^2, a^2b^2).$$
Finally, we perform $2k-1$ steps and replace $2k-1$ times two $ab$'s by two $a^2b^2$'s, which leads to $(a^2b^2, \dots, a^2b^2)$.

Again, we shall proceed by induction. The claim is trivial for $n=2$. Suppose the claim is true for $n=k$ and take $n=k+2$. Using the induction hypothesis, we first construct an $n$-tuple of the form
$$\underbrace{(a, \dots, a, b, b)}_{k}.$$
For every $i=3, 4, \dots, k$, we perform the operation with the numbers at the positions $i$ and $k+1$. These $k-2$ steps change the $n$-tuple into
$$(a, a, ab, a^2b, \dots, a^{k-2}b, a^{k-2}b, b).$$
After selecting the last two numbers, we get
$$(a, a, ab, a^2b, \dots, a^{k-2}b, a^{k-2}b^2, a^{k-2}b^2).$$
Now, for every $i = 1, 2, \dots, \frac{1}{2}n$, we combine the numbers at the positions $i$ and $n+1-i$, getting the desired
$$(a^{k-1}b^2, a^{k-1}b^2, \dots, a^{k-1}b^2).$$