The Game of NIMDate: 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 |
Search the Dr. Math Library: |
[Privacy Policy] [Terms of Use]
Ask Dr. Math^{TM}
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/