Subtraction Games

Subtraction Games

In general we may define a subtraction game in the following way: it is permitted in each move of a player to remove either n1, n2, n3, ..., nk toothpicks from any of the piles. Once again, the winner will be he who removes the last toothpick from the table. The value of a pile of n toothpicks is no longer *n, as seen in Nim, but is in fact calculated in the same way that that result was calculated: we determine the smallest number not included in a list of values obtained on a move. In other words, the mex rule continues valid in general subtraction games.

Consider a game in which either one, three or four toothpicks may be removed in each move. We designate this game by S(1,3,4). If there are no toothpicks at all, none may be removed and the value is mex { } = 0. From a pile of one toothpick, one may be removed, leaving none at all: mex {0} = *1, as “one” is the smallest number not contained in the set. From a pile of two, in this game, just one may be removed, so that mex {*1} = 0. From a pile of three toothpicks, one or three may be removed, leaving two or none: mex {0, 0} = *1. And in a pile of four, one, three or four may be removed, leaving three, one or none: mex {0, *1, *1} = 2. If we continue we find a sequence of values that will be written as a sequence called G(k). So for this game
G(k) = 0,1012320101232010123201012320...
which is in fact a periodic sequence, 0,1012320 of period seven.

The strategy to play is similar to that of Nim. The player wishes that the sum of the values of the piles be equal to zero after his move, for that implies that “he who plays in second place wins”. For example, suppose that this game is played with piles of 2, 3, 8 and 9 toothpicks. We see that G(2) = 0, G(3) = *1, G(8) = *1 and G(9) = 0, so that the sum is zero. Therefore, no player will want to be the first to play, for whatever the first player does, the sum afterwards will no longer be zero and the second to play can certainly move so that the sum returns to value zero after his move.

It can be proven that the mex sequence of any subtraction game is periodic.