15th 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)\to (ab,ab)$) and $n=4$ (we can follow the scheme $(\underline{a},\underline{b},c,d)\to (ab,ab,\underline{c},\underline{d})\to (\underline{ab},ab,\underline{cd},cd)\to (abcd,\underline{ab},abcd,\underline{cd})\to (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{array}{rl}(a,a,a,\underline{a},\underline{b},b)& \to (a,a,\underline{a},\underline{ab},ab,b)\to (a,a,a^{2}b,\underline{a^{2}b},\underline{ab},b)\to (a,a,\underline{a^{2}b},a^3{b}^2,a^3{b}^2,\underline{b})\to \\ & \to (\underline{a},\underline{a},\underline{a^2{b}^2},a^3{b}^2,a^3{b}^2,\underline{a^2{b}^2})\to (a^3{b}^2,a^3{b}^2,a^3{b}^2,a^3{b}^2,a^3{b}^2,a^3{b}^2)\end{array}$$

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 $$\underset{2k+2}{\underbrace{(a,\dots ,a)}},\underset{2k+2}{\underbrace{(b,\dots ,b)}}$$

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 $$\underset{2k+2}{\underbrace{(a,\dots ,a)}}\underset{2k+4}{\underbrace{,b,\dots ,b)}}.$$ Now we perform $2k$ steps, always choosing one $a$ and one $b$, to obtain $$(a,a,\underset{4k}{\underbrace{ab,\dots ,ab)}},b,b,b,b).$$ After erasing each $a$ with one $ab$ we get $$(a^{2}b,a^{2}b,a^{2}b,a^{2}b,\underset{4k-2}{\underbrace{ab,\dots ,ab)}},b,b,b,b),$$ and after pairing each $b$ with one $a^{2}b$ we have $$(a^2{b}^2,a^2{b}^2,a^2{b}^2,a^2{b}^2,\underset{4k-2}{\underbrace{ab,\dots ,ab)}},a^2{b}^2,a^2{b}^2,a^2{b}^2,a^2{b}^2).$$ Finally, we perform $2k-1$ steps and replace $2k-1$ times two $ab$'s by two $a^2{b}^2$'s, which leads to $(a^2{b}^2,\dots ,a^2{b}^2)$.

---

Alternative solution.

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 $$\underset{k}{\underbrace{(a,\dots ,a,b,b)}}.$$ 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^{2}b,\dots ,a^{k-2}b,a^{k-2}b,b).$$ After selecting the last two numbers, we get $$(a,a,ab,a^{2}b,\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).$$