Swap

Enough of minimal surfaces, at least here, for a while. Time for a relaxing little game. Let’s put six tokens in a row, three showing a 1, the other three a 2. There are evidently 6 choose 3 = 20 possibilities for that. A move consists of swapping two neighboring tokens, which also evidently only makes sense if they are different.

Above is the graph that shows all possible states, the connections indicating the possible moves. What is interesting here? Not much. The graph is connected, which is easy to explain, and I mention all this only because it will serve as the 1-dimensional example of what we’ll do in two dimensions next week and in even higher dimensions later. So, to make things more complicated we are allowing the six tokens to show three values 1, 2, 3. We begin with two tokens of each kind.

The graph is more complicated but offers no interesting insights. Let’s forbid to swap neighbors 12 or 21. The game graph will have six identical components. This usually makes for hideous puzzles, asking the innocent victim to find moves that change say 112233 to 332211. But here this is too obvious, as we clearly cannot change the order of the 1s and 2s while the 3s can move freely among them.

To fix this, we make one more change: We arrange the tokens in a circle, still use 112233, and disallow a 12-21 swap.

Two different components. Why can’t we move from 112233 to say 132213? Again, order plays a role: There is just no way to get from 1133 to 1313, even if we allow cyclic permutations.

Finally, an example with just four tokens, having values 1 through 4, arranged in a square. We allow the swaps 12-21, 23-32, 34-43, and 41-14, but forbid 13-31 and 24-42.

This time we get two components as well. Why can’t we move from 1234 to 4123, i.e. rotate all tokens clockwise by 90 degrees? This time, the order still plays a role, but involves the orders of both pairs 13 and 24 simultaneously, which is hard to see. So this makes, in all its simplicity, a pretty nice puzzle.