Proof by Example (Push & Pop I)

Here is Push & Pop, a puzzle with a very simple mechanics. It is played on a single strip with a fixed number of fields, occupied by tokens that are stacked on top of each other (as in checkers)

A move consists of taking some of the top tokens of a tower, and moving them onto a field that is as many steps away as you are taking tokens, within the limits of the game board. If the target field is occupied, just place your tokens on top. Note that you can take only pieces from the top, and are not allowed to change their order. In the position above, the possible moves are indicated by the arrows, and you can see the possible new positions below. 

You will gladly notice that the color of the tokens does not matter at all at this point. You will also notice that moves are reversible, because undoing a move is also a legal move. Games are in so many ways better than reality. 

A typical puzzle using this mechanic is given by two position, and the task is to transform the first into the second using only legal moves. Here is a simple example, played on a board of size three with two tokens of different color, placed on top of each other at the leftmost field. The task is to swap the position of the two tokens:

This is not possible on a board of size 2 (why?), and requires five moves on a board of size 3 like so:

Why should we care? Particular examples can often be used to gain universal insights. In this case, for instance, we have just essentially proven that any puzzle on a board of size at least three can be solved. How so?

We have shown that two adjacent tokens in a single tower can be swapped, if there are two fields available to the right. It does not matter if these fields are occupied or not, because we can just play on top of any existing pieces. It does also not matter if there are tokens below the two we want to swap, and not even if there are tokens on top, because we can move them temporarily out of the way (remembering that moves are reversible).

As the group of all permutations is generated by transpositions (use bubble sort), we can in fact permute the tokens in any single tower to our liking. Finally, to solve an arbitrary puzzle, we first move all tokens (piece by piece, if needed) onto a single tower on the leftmost field, then permute them into the order we need, and then move them into the desired target position.

Here is a puzzle on a board of size 5 with four tokens in 3 colors. You know now that there is a solution. But what is the shortest solution?

To be continued…