linearnim

LinearNim is a variation of the game of Nim. In this version, the game is played with a single pile of tokens, and players can remove a number of tokens from the pile. The number of tokens that can be removed is restricted by a set of allowed moves. For instance, if the allowed moves are {1, 3, 4}, a player can choose to remove 1, 3, or 4 tokens from the pile. The player who takes the last token wins.

The game can be analyzed using the Sprague-Grundy theorem, which is a fundamental concept in combinatorial game theory. This theorem states that every impartial game under the normal play convention (last player to move wins) is equivalent to a Nim pile of a certain size. This size is called the nim-value or Grundy number (g-number) of the game. The g-number of a game position is the smallest non-negative integer that is not among the g-numbers of the positions reachable in one move. This is known as the mex (minimum excluded value) rule.

For LinearNim, the g-number of a pile of size n, denoted g(n), can be calculated recursively. g(n) = mex({g(n-m) | m is an allowed move and n-m >= 0}). A position is a losing position if its g-number is 0, and a winning position if its g-number is non-zero. The initial position of the game determines whether the first player has a winning strategy. If the g-number of the initial pile size is non-zero, the first player can win by always moving to a position with a g-number of 0. If the g-number is 0, the second player has a winning strategy, assuming optimal play from both sides. The sequence of Grundy numbers for LinearNim can exhibit periodic behavior, which can be used to determine the outcome for very large piles.