A Generalization of the Game Called Nim
Eliakim Hastings Moore · Annals of Mathematics · 1910
IN the third volume of the second series of the ANNALS OF MATHEMATICS Professor Bouton described and gave the complete mathematical theory of a known game for which he proposed the name Nim. I propose to describe a generalization of Nim, which may be called Airnk, read Nim index k. Here k is any positive integer, and the game Nim1 is the original game Nim. Nimk has likewise a complete mathematical theory which I shall content myself with formulating. Description of the Game NiMk. There are two players A and B and an assortment of objects of any kind, say counters. The dealer A takes as many counters as he wishes and separates them at will into any number (2 1) of pilee. The players draw alternately from this deal of say n piles, B drawing first; the player drawing the last counter (or counters) wins. In each draw the player must draw one or more counters from some one pile and he may draw at will from any number of piles not to exceed k. (Thus, in Nim1 each draw is from one pile.) 1Mathematical Theory of the Game Nimk. It is clear that, if A deals to B fewer than k + 1 piles, B may win on the first draw by drawing all the counters. Such a deal is an unsafe combination (to adopt a term used by Bouton) for A to deal to B. There are in fact two kinds of combinations: safe and unsafe comibinations, the fundamental properties being that every unsafe combination by a suitable draw may be made safe, while every safe combination by every draw is made unsafe. Thus, if A deals a safe combination to B, B by drawing cannot avoid making it unsafe, A by drawing suitably makes it again safe, and so on until finally B is obliged to reduce the number of piles below k + 1, when A wins. On the other hand, if A deals an unsafe combination to B, B by drawing suitably makes it safe, and then the game proceeds as before, until B finally wins. Formula for safe combinations. Let the combination be of n piles containing respectively cl, c2, **., nC. counters. (93)