CTK Insights

Tweet

The setup for the 2-players game described below consists of three checkers placed on a K×1 board:

A move consists in picking one of the outside checkers and placing it anywhere between the other two. Here's a sequence of two successive moves.

As usual, players take turns. The one who can't make a move loses the game. Is there a right strategy? How should one play? Would you want to make the first move?

Here are a few thoughts

The game has two parameters: the number of free squares between the first and the second, and the second and the third checkers. Let's call them M and N. A position is completely described by the set {M, N}.

Two small configurations will give a clue for a possible strategy.

You would certainly like to be faced with the {1, N} configuration, whatever N > 1. All it would take to win is to fill the 1-square gap between two checkers with the third one.

You would certainly not like to be faced with the {2, 2} configuration because, the only configuration you may leave is {1, 2} that augurs ill for your chances to win, unless of course, your opponent plays randomly. More generally, placing a checker into a gap with an even number of squares always leaves a configuration {odd, even}. Thus it may never be the last move. But it may be a losing move if the odd number left is exactly 1.

Placing a checker into an odd gap (unless it's of length 1) may create either an {odd, odd} or an {even, even} configuration. An {odd, odd} configuration may be dangerous, especially (as we've argued before) if one of the numbers is 1. On the other hand, an {even, even} configuration (where not both numbers are 0) is harmless in the sense that it may never lead to the fatal {0, 0} in one move. I.e., it is harmless for you, the player who leaves it to his opponent. For the opponent it is bad because it forces hime to place a checker into an even gap. What's bad about that? First, doing that could not be the last move. Second, it leaves your opponent in a vulnerable position where you can make a move (if not the winning one) that returns to him an {even, even} configuration.

The general theory of combinatorial games applies to the game at hand. From the foregoing discussion we can identify positions {even, even} as P-Positions - position that one would like to leave after one's move. Configurations {odd, N}, whatever N, are N-Positions; these are the positions you would like to face.

From an P-position, every move leads to a N-position. Every N-position admits moves that leave P-position.

It follows that the first player who starts with a configuration {M, N> in which one of the numbers is odd has a chance to win (by leaving a configuration with both gaps even), regardless of what the other player does. If in the starting configuration both numbers are even then you would prefer to play second.

References

1. XXX M. V. Lomonosov Competition, 2007, MCCME.