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

### The Game of NIM

Date: Tue, 31 Jan 1995 09:14:09 -0800 (PST)
From: Chianne Chen
Subject: Brain Bender

My calculus teacher Ms.McComb gave up this problem.  Please help me solve it.

The game of NIM is played with a bunch of beans.  The first player
separates the total number of beans into separate piles (anyway he or she
wants).  The second player specifies whether winning consists of taking
the last bean or avoiding the last bean.  The second player also gets to
move first.

Each move, the player whose turn it is, must choose one pile of beans and
remove anywhere from one bean to all the beans in the pile.  She or he
may not pass, and may not remove beans from two or more different piles.

My teacher claims she can always win the game if she gets to be the
second player.  Is she telling the truth?  If no, give an example, where
no matter how she plays, she loses.  If yes, what specific strategy might
she use to guarantee success?

Thank you, I, Chianne Chen, am at cchen@walrus.mvhs.edu

From: Dr. Ken
Date: Thu, 2 Feb 1995 21:32:14 -0500 (EST)
Subject: Re: Brain Bender

Hello there!

Before starting on this problem, I need to clarify one rule of the game.
When you say "whether winning consists of taking the last bean or avoiding
the last bean," do you mean the last bean in any one pile, or the last bean
in _any_ pile?

From: Chianne Chen
Date: Mon, 6 Feb 1995 08:42:03 -0800 (PST)

Going back to your rule, I mean the last bean in "any one pile"
Please write back soon, thank you

Chianne Chen

From: Dr. Ken
Date: Sat, 25 Mar 1995 16:39:21 -0500 (EST)
Subject: Re: Brain Bender

Hello there!

I must apologize for talking such an incredibly long time in answering your
question.  Our service is relatively new, and we've been trying to figure
out how best to deal with processing the questions.  Hopefully we'll work
out the kinks soon.

I'll adopt the following notation: {1,2,4} means that there is one pile with
1 bean in it, one pile with 2 beans in it, and one pile with 4 beans in it.
{1,2,4,4} would be the same thing, but now there are two piles with 4 beans
in them.

Here are some thoughts about your problem.  In problems like this (where one
player is competing _against_ another player, instead of cooperating), it's
often helpful to look at the final few moves of the game.  For instance, if
it's {1,1,1} and it's your teacher's move, can she win?  I suppose that
depends on what she has declared to be the object of the game.  If the
object is to take the last bean, she's got it.  If the object is to not take
the last bean, she's sunk.  So if this were the very first move of the game,
she could guarantee winning just by determining the object of the game.
Moreover, if there are any number of piles with only one bean in each pile,
she can guarantee winning just by choosing the object of the game.

Let's look at another configuration: {n,1,1} where n>1.  Then your teacher
could guarantee winning by taking all but one bean in the first pile
(leaving {1,1,1}) and saying that the object is to not take the last bean.
Of course, this same strategy (perhaps changing the object of the game)
could be applied whenever all but one of the piles have only one bean, where
there are any number of piles.

It gets a little more interesting when there is more than one pile with
several beans.  What will end up being something to look at, though, is the
number of piles that have more than one bean.  For example, consider
{2,2,1}.  I found a strategy in which the second player can always win with
this configuration.  Can you find it, and see how you could apply it to
{n,m,1}, where n>m>1?

I'm not sure whether you'll be able to come up with a proof of the
winnability of the game, but you may be able to convince yourself of it.  I
hope it's not too late and you've stopped thinking about the problem!

Ken - Dr. Math

Associated Topics:
High School Discrete Mathematics

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