Hints and Background - but NO CHEATING!!

Tile Nim
Close this window to go
back to the activity page.

Welcome to the Wonderful World of Nim!
First a lesson in binary numbers. The only digits that are used in binary numbers are 1 and 0. The place values are, starting at the right and going left, 1 2 4 8 16 32 64 128 and so on. For Nim, you don't need to know how to count very far. Here's how it works:

Base Ten Binary

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15 1
10
11
100
101
110
111
1000
1001
1010
1011
1100
1101
1110
1111 (One in the one's place)
(One in the two's place, zero in the one's place)
(One in the two's place, one in the one's place: 2+1=3)
(One in the four's place, zero in the two's and one's)
(One in the four's place, zero in the two's place, and one in the one's place: 4 + 1 = 5)
(One in the four's place, one in the two's place, and zero in the one's place: 4 + 2 + 0 = 6)
(One in the four's place, one in the two's place, and one in the one's place: 4 + 2 + 1 = 7)
(8 + 0 + 0 + 0 = 8)
(8 + 0 + 0 + 1 = 9)
(8 + 0 +2 + 0 = 10)
(8 + 0 + 2 + 1 =11)
(8 + 4 + 0 + 0 =12)
(8 + 4 + 0 + 1 = 13)
(8 + 4 + 2 + 0 = 14)
(8 + 4 + 2 + 1 =15)

At the end of each player's turn, the arrangement of sticks is either "safe" or "unsafe." When your turn ends in a safe position, you can win. If your turn ends in an unsafe position, you will lose (if you're playing against someone who is an expert at Nim).

Safe positions are made unsafe by any move. Unsafe positions can become either safe or unsafe depending on the move. The first step in playing the game is to decide if the opening position is safe or unsafe. If it is safe, there is nothing you can do to make it safe so let your opponent go first. If it is unsafe, you'll be able to make it safe with your move so you should go first.

Let's look at a sample game:

In binary notation the rows have 11, 100, and 101 tiles, respectively.

Now line up the binary notations in one column:

11
100
101

Now count the number of 1s in each column. To win using the binary notation, you have to take tiles so that, at the end of your turn, the number of ones in each column is even or zero. There are two in the first column, one in the second column, and two in the third column. This means that the position is unsafe but you can make it safe by getting rid of the one in the second column. To do that, take two of the tiles in the first row.

Now the binary numbers are:

1
100
101

There are 2 ones in the first column, zero in the second column, and two in the third column. Remember, when your turn is over, there needs to be an even number of ones in each column.

Your opponent, who isn't an expert in binary numbers, takes 3 tiles from the bottom row.

1
10
10

What should your move be?

The best move would be to remove the 1 in the top row. That will leave 2 ones in the first column and zero ones in the second column.

Your opponent now removes one from the row of four.

11
10

Now what is your move?

You need to make the row of 3 a row of 2.

Can you win at this point? Bet you can!!

Try this strategy using different numbers of tiles in different arrangements--you can always win (unless your opponent read this page!).

Base Ten	Binary
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15	1 10 11 100 101 110 111 1000 1001 1010 1011 1100 1101 1110 1111	(One in the one's place) (One in the two's place, zero in the one's place) (One in the two's place, one in the one's place: 2+1=3) (One in the four's place, zero in the two's and one's) (One in the four's place, zero in the two's place, and one in the one's place: 4 + 1 = 5) (One in the four's place, one in the two's place, and zero in the one's place: 4 + 2 + 0 = 6) (One in the four's place, one in the two's place, and one in the one's place: 4 + 2 + 1 = 7) (8 + 0 + 0 + 0 = 8) (8 + 0 + 0 + 1 = 9) (8 + 0 +2 + 0 = 10) (8 + 0 + 2 + 1 =11) (8 + 4 + 0 + 0 =12) (8 + 4 + 0 + 1 = 13) (8 + 4 + 2 + 0 = 14) (8 + 4 + 2 + 1 =15)