Editing Nim (section)

=== Index-''k'' nim ===

A generalization of multi-heap nim was called "nim<math>{}_k</math>" or "index-''k''" nim by [[E. H. Moore]],<ref>Moore, E. H. ''A Generalization of the Game Called Nim''. [https://www.jstor.org/stable/1967321 Annals of Mathematics 11 (3), 1910, pp. 93–94]</ref> who analyzed it in 1910. In index-''k'' nim, instead of removing objects from only one heap, players can remove objects from at least one but up to ''k'' different heaps. The number of elements that may be removed from each heap may be either arbitrary or limited to at most ''r'' elements, like in the "subtraction game" above.

The winning strategy is as follows: Like in ordinary multi-heap nim, one considers the binary representation of the heap sizes (or heap sizes modulo ''r''&nbsp;+&nbsp;1). In ordinary nim one forms the XOR-sum (or sum modulo 2) of each binary digit, and the winning strategy is to make each XOR sum zero. In the generalization to index-''k'' nim, one forms the sum of each binary digit modulo ''k''&nbsp;+&nbsp;1.

Again, the winning strategy is to move such that this sum is zero for every digit. Indeed, the value thus computed is zero for the final position, and given a configuration of heaps for which this value is zero, any change of at most ''k'' heaps will make the value non-zero. Conversely, given a configuration with non-zero value, one can always take from at most ''k'' heaps, carefully chosen, so that the value will become zero.