Let $n$ be a positive integer and consider an arrangement of $2n$ blocks in a straight line, where $n$ of them are red and the rest blue. A swap refers to choosing two consecutive blocks and then swapping their positions. Let $A$ be the minimum number of swaps needed to make the first $n$ blocks all red and $B$ be the minimum number of swaps needed to make the first $n$ blocks all blue. Show that $A+B$ is independent of the starting arrangement and determine its value.
The answer is $n^2$
For simplicity, we will let the front of the line be on the left and the back to be on the right.
Define an a pair of distinct blocks to be reddy if the block nearer to the left is red and the block nearer to the right is blue and bluey if the block nearer to the left is blue and the block nearer to the right is red. Note that there are $n^2$ reddy or bluey pairs of blocks (which is obtained by taking any pair of blocks with distinct colours)
When we swap 2 consecutive blocks, we remove at most 1 reddy pair (which occurs when the 2 blocks we swap are a reddy pair).
Additionally, when not all of the first $n$ blocks are red, then there exists a blue block directly to the left of a red block (otherwise only red blocks are to the left of red blocks which implies that the first $n$ blocks are red).
Hence, $A$ is the number of reddy pairs at the beginning.
Similarly, $B$ is the number of bluey pairs at the beginning. Hence, $A+B = n^2$