Let $k \geq 1$ be an integer.

We consider $4 k$ chips, $2 k$ of which are red and $2 k$ of which are blue. A sequence of those $4 k$ chips can be transformed into another sequence by a so-called move, consisting of interchanging a number (possibly one) of consecutive red chips with an equal number of consecutive blue chips. For example, we can move from $r \underline{b b b r} \underline{r} b$ to $r \underline{r r} b r \underline{b b b}$ where $r$ denotes a red chip and $b$ denotes a blue chip.

Determine the smallest number $n$ (as a function of $k$) such that starting from any initial sequence of the $4 k$ chips, we need at most $n$ moves to reach the state in which the first $2 k$ chips are red.
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 brbrbr $\cdots$ br 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 neighbor or a blue chip getting rid of its red right neighbor. This can only happen with the leftmost chip of $R$ (if its left neighbor is blue) and the rightmost chip of $B$ (if its right neighbor is red), but not with the rightmost chip of $R$ (and its right neighbor) or the leftmost chip of $B$ (and its left neighbor). Hence $C$ is reduced by at most 2 in any move. Therefore the number of moves necessary to change brbrbr $\cdots$ br 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.