Associated Topics || Dr. Math Home || Search Dr. Math

### Winning at NIM

```
Date: 06/09/97 at 19:22:39
From: Brett Wilson
Subject: Puzzles

Dear Dr. Math,

Our teacher gave us a game called NIM. In the game you are given a
series of dots in rows. There can be any number of dots per row and
any number of rows. Each player must remove any amount of dots, but
they must all be from the same row. The winner of the game is the
person who takes the last dot out of the game.

For example:   .
...
....
.....
.......

With this diagram, I might take the one dot on top and then, you could
take any other dot/dots from another row.

winning game.

Thanks
```

```
Date: 06/10/97 at 11:18:01
From: Doctor Anthony
Subject: Re: Puzzles

The strategy for winning the game of Nim has been extensively studied.

Express the number of dots in any row in binary notation, so if we had
three rows with 3, 4, 5 dots respectively we could write this as:

3      1 1
4    1 0 0
5    1 0 1
----------
2 1 2

This position is 'unsafe' because one of the columns sums to an odd
number. This can be made 'safe' by the first player by taking two dots
from the top row leaving the table in the form:

1        1
4    1 0 0
5    1 0 1
----------
2 0 2

This is 'safe', but the next player by making any move whatever will
of necessity go to an 'unsafe' position, and the first player can
again calculate column totals and get back to a 'safe' position.

The winning strategy requires that if you have the next move, the
situation be 'unsafe', i.e. that there be an odd number in one of the
column totals, and you then take dots from one of the rows so as to
make all the column totals even. You are now safe, because the next
move will of necessity go back to an unsafe position. You continue in
this way, such that AFTER your move, the column totals will be even,
and you will win.

-Doctor Anthony,  The Math Forum
Check out our web site!  http://mathforum.org/dr.math/
```
Associated Topics:
High School Discrete Mathematics
High School Puzzles

Search the Dr. Math Library:

 Find items containing (put spaces between keywords):   Click only once for faster results: [ Choose "whole words" when searching for a word like age.] all keywords, in any order at least one, that exact phrase parts of words whole words

Submit your own question to Dr. Math
Math Forum Home || Math Library || Quick Reference || Math Forum Search