What is Subtraction game?
The subtraction game is Nim with a limit on each move. You still take objects from one heap of your choice, but at least one and at most k, where k is 2, 3, 4 or 5, chosen in the table setup (3 by default). You may take a whole heap only when it holds k objects or fewer.
Everything else is as in the standard game: the starting heaps come from the same setup option (1, 3, 5 and 7 by default), and the misère switch decides whether taking the last object loses (the default here) or wins. The cap changes the arithmetic of the game. A large heap can no longer be emptied in one move, so it cannot be used to fix the position in a single stroke, and what matters about each heap is its size divided by k + 1: the remainder.
Rule changes
| Rule | Standard Nim | Subtraction game |
|---|---|---|
| Moves | Standard NimTake one or more objects from one heap, as many as you like, up to the whole heap. | Subtraction gameTake at least 1 and at most k objects from one heap; k is 2, 3, 4 or 5, chosen in the table setup (3 by default). |
| Heaps | Standard NimSeveral heaps: 1, 3, 5 and 7 objects by default, or another set chosen in the table setup. | Subtraction gameThe same heaps, chosen with the same option. |
| Goal | Standard NimMisère play by default: whoever takes the last object loses. The setup can switch to normal play, where taking the last object wins. | Subtraction gameThe same, with the same misère switch. |
| Winning play | Standard NimNormal play: leave the heaps with a nim-sum (the bitwise XOR of their sizes) of zero. Misère play: the same, until only heaps of one object would be left; then leave an odd number of them. | Subtraction gameNormal play: each heap counts as the remainder of its size divided by k + 1, and you leave those remainders with a nim-sum of zero; a single heap is lost for the player to move exactly when its size is a multiple of k + 1. Misère play: a single heap is lost for the player to move exactly when its size is one more than a multiple of k + 1. |
History
Counting games with a cap on each move are old. Claude-Gaspard Bachet de Méziriac's Problèmes plaisants et délectables, a collection of mathematical recreations first published in Paris in 1612, describes a game in which two players take turns adding a number from 1 to 10 to a running total, and the first to reach 100 wins. The winning plan is to reach the totals 12, 23, 34 and so on up to 89, in steps of 11: the same arithmetic as a single heap of 100 from which each move takes 1 to 10.
Nim itself got its name and its full theory from Charles L. Bouton in 1901. The work of Roland Sprague (1935) and Patrick Grundy (1939) showed that every game of this kind, the subtraction game included, behaves like a Nim heap of a certain size, which is how the version with several heaps is solved. Subtraction games are a standard example in the theory of combinatorial games, for instance in Winning Ways for your Mathematical Plays by Elwyn Berlekamp, John Conway and Richard Guy.