Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
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.

Please help us if you have any idea of the strategy to a guaranteed 
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

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/