Problem 2122

Solution:
The answer is $n = k$.

We will first show that $n \geq k$. Let us count the number $C$ of times a red chip is directly to the right of a blue chip. In the final position this number equals $0$. In the position $b r b r b r \cdots b r$ this number equals $2k$. We claim that any move reduces this number by at most $2$. Denote by $R$ the group of red chips and by $B$ the group of blue chips that are interchanged. Any reduction in $C$ must involve a red chip getting rid of its blue left neighbour or a blue chip getting rid of its red right neighbour. This can only happen with the leftmost chip of $R$ (if its left neighbour is blue) and the rightmost chip of $B$ (if its right neighbour is red), but not with the rightmost chip of $R$ (and its right neighbour) or the leftmost chip of $B$ (and its left neighbour). Hence $C$ is reduced by at most $2$ in any move. Therefore the number of moves necessary to change $b r b r b r \cdots b r$ into the final position is at least $\frac{2k}{2} = k$.

We will now show that $n \leq k$, i.e. that it is always possible to perform at most $k$ moves in order to reach the state in which the first $2k$ chips are red. Consider the first $2k$ chips. If at most $k$ of these chips are blue, we can perform one move for each chip, switching it with one of the red chips of the last $2k$ chips. So then we are done in at most $k$ moves. Now suppose that of the first $2k$ chips, at least $k+1$ are blue. Then at most $k-1$ chips are red. Hence it is possible to perform at most $k-1$ moves to reach the situation in which the last $2k$ chips are red. We then perform one final move, switching the first $2k$ chips and the last $2k$ chips, ending in the situation in which the first $2k$ chips are red. Thus, it is always possible to reach the situation in which the first $2k$ chips are red in at most $k$ steps, hence $n \leq k$.

We have now shown that $n \geq k$ and $n \leq k$, hence $n = k$ as claimed.