Is it possible to switch positions of 2 distinct coins if we are only allowed to add or remove 2 of the same type of consecutive coins at a time

Question

Using two coins, one red and one blue (in that order from left to right). If you play a game whose rules are:
You can add or remove 2 consecutive, red or blue, adjacent coins, is it possible to arrive at a state where the coin on the left is blue and the one on the right is red
For example: Using R and B to represent red and blue coin respectively, your initial position is
RB
RBRR (on adding 2 consecutive red coins to the right of the initial arrangement)
RBBBRR
BBRBBBRR
BBRBRR (on removing the 2 consecutive blue coins in the middle).

My argument is that since one can only add and remove in consecutive pairs, there is no way to isolate a Blue or a Red coin such that we can swap their positions. Hence there is no way to reach a state where the position of the coins is BR.

Is this correct?

Answer 1

If you're faced with a problem "here are some possible transformations; prove that you can never reach such-and-such state", then one good strategy is to find an invariant. An invariant is some property that (you prove) never changes between steps. If it's different between your starting state and your desired ending state, then you can never get to that ending state.

In this case, for any state, count the number of ways to choose two coins such that the one further left is Red and the one further right is Blue.

For example:

• RB has one way.
• RBBB has three: RB.., R.B., and R..B.
• RBBBRR still has three: RB...., R.B..., R..B...
• RRRBBBRRR has nine: R..B....., R...B...., R....B..., .R.B....., .R..B...., .R...B..., ..RB....., ..R.B...., ..R..B....

You should prove that no matter how you insert or delete two adjacent coins of the same color, this quantity changes by an even number. (So the invariant is whether this quantity is odd or even.)

Since the quantity starts out odd, it always remains odd. But in the state BR, it is $0$, which is even; so the state BR can never be reached.