Editing Nim (section)

=== The subtraction game ===
<imagemap>
File:Subtraction_game_SMIL.svg|thumb|Interactive subtraction game: Players take turns removing 1, 2 or 3 objects from an initial pool of 21 objects. The player taking the last object wins.
default [http://upload.wikimedia.org/wikipedia/commons/4/4d/Subtraction_game_SMIL.svg]
</imagemap>
In another game which is commonly known as nim (but is better called the [[subtraction game]]), an upper bound is imposed on the number of objects that can be removed in a turn. Instead of removing arbitrarily many objects, a player can only remove 1 or 2 or ... or ''k'' at a time. This game is commonly played in practice with only one heap.

Bouton's analysis carries over easily to the general multiple-heap version of this game. The only difference is that as a first step, before computing the nim-sums we must reduce the sizes of the heaps [[modular arithmetic|modulo]] ''k''&nbsp;+&nbsp;1. If this makes all the heaps of size zero (in misère play), the winning move is to take ''k'' objects from one of the heaps. In particular, in ideal play from a single heap of ''n'' objects, the second player can win [[if and only if]]

* ''0''&nbsp;=&nbsp;n&nbsp;(mod&nbsp;''k''&nbsp;+&nbsp;1) (in normal play), or
* ''1''&nbsp;=&nbsp;n&nbsp;(mod&nbsp;''k''&nbsp;+&nbsp;1) (in misère play).

This follows from calculating the [[nim-sequence]] of ''S''(1, 2, ..., ''k''),

<math display="block">0.123\ldots k0123\ldots k0123\ldots = \dot0.123\ldots\dot{k}, </math>

from which the strategy above follows by the [[Sprague–Grundy theorem]].