NIM

Nim is a game for 2 players, each alternating taking turns. Initially the players are given a position consisting of several piles, each pile having a finite number of tokens. On each turn a player picks a pile and then removes at least one token from that pile. The player who picks up the last token wins.

Assuming your opponent plays optimally, some positions cannot be won. Such positions are called "losing" (for the player whose turn it is to move next). The positions which are not losing are called winning. The following question has a mathematical answer:

QUESTION: Which positions are losing for the player whose turn it is to move?

The answer is determined by the "nim sum" of the piles. The "nim sum" of r piles with m1 elements in the 1st pile, m2 elements in the 2nd pile, ..., mr elements in the last (r-th) pile, is obtained as follows:

• write each of these numbers in binary and represent this binary number as a vector of 0's and 1's with 0's filled in on the end to make them all the same length: v1=[a11,a12,...,a1n], v2=[a21,a22,...,a2n], ..., vr=[ar1,ar2,...,arn],
• define the nim sum vector of the position vector to be the vector sum v1+v2+...+vr,
• define the nim sum G(m1,m2,...,mr) of the position to be the number whose binary digits are the entries in the nim sum vector reduced (mod 2).

If each of the coordinates of the nim sum vector is is even then we call the position even. Otherwise, we call the position odd. In the book by Hardy and Wright referenced below, one finds that odd positions are winning and even position cannot be won if your opponent plays optimally.

If an initial position is not a losing position, what strategy should one use to win? Make a move which leaves you in an odd position.

The MAPLEV4 nim package has routines to play nim solitaire or nim with the computer. There is a help worksheet which may be downloaded as well. If you have MAPLEV4 and Windows 3.1 or better then here is how to load the nim package:

• create a subdirectory "games" of your maplev4/share directory,
• create a subdirectory "nim" of your maplev4/share/games directory,
• copy nim.mpl into this nim subdirectory,
• read this text file into maple and save the resulting nim.m file in the "games" subdirectory created above,
• in a new session of maple type:

  with(share): readshare(nim,games);

• To play nim solitaire, type "playnim();". To play nim with the computer type "play_nim_with_PC();". MAPLE will ask you various questions on how to set up the piles and then prompt you to move.

W.W.R. Ball and H.S.M. Coxeter, Mathematical recreation and essays, 13th ed, Dover, 1987

G. Hardy and E. Wright, An introduction to the theory of numbers, 5-th ed, Oxford Univ Press, 1979