Tag Archives: pebbles

Nim

Standard

Nim is a very old game with precise mathematical theory, and one player can always force a win.

The game is Nim is played as follows: Any number of matches/pebbles are arranged in heaps, the number of heaps and the number matches/pebbles in each heap, being arbitrary.  There are two players, A and B. The first player A takes any number of matches/pebbles from a heap, he/she may take only one or any number up to the whole of the heap, but he/she must touch one heap only. B then makes a move conditioned similarly, and the players continue to take alternate turns of picking matches/pebbles. The player who takes the last match/pebble wins the game.

We define a winning position as a position such that if one player P (A or B) can secure it by his/her move, leaving his/her opponent Q (B or A) to move next, then, whatever Q may do, P can play so as to win the game. Any other position we call a losing position.

Next, we express the number of matches in each heap in the binary scale and form a figure by writing down one under the other. Then we add up the columns. For example, consider the following position:

nim

Then, (1,3,5,7) position gives the following figure:

001
011
101
111

224

If the sum of each column is even (which is the case above), then the position is correct. An incorrect position is one which is not correct, thus (1,3,4) is incorrect.

Then we have the following result:

A position in Nim is a winning position if and only if it is correct.

For the proof/discussion/variations of rules, see § 9.8, of G. H. Hardy and E. M. Wright’s An Introduction to the Theory of Numbers.

But designing an elaborate winning strategy, i.e. ensuring that you always stay in winning position, is not so easy (though we know it exists!). For example, watch this video by Matt Parker:

Advertisements