Date: 09/26/2000 at 03:26:40 From: Winarto Subject: Nim What is the principle of Nim, and what is its application?
Date: 09/26/2000 at 09:53:39 From: Doctor Anthony Subject: Re: Nim 1) You have three piles of coins, say 3 in the first pile, 4 in the second pile, and 5 in the third pile. 2) You alternate turns withdrawing one or as many coins found in any given pile. You may withdraw from only one pile at a time. For example: In the first pile, you or your opponent can withdraw 1, 2, or 3 coins... and the same with the other two piles. 3) The person who is left to draw the last coin loses. The technique is to express the number of coins in each pile in binary scale and add the coefficients of the various powers of 2. You then remove as many coins from some pile or other as necessary to leave the sum of the coefficients of each power of 2 an even number. When the opponent draws, he is bound to upset such an arrangement and you then repeat the process. The only exception is that you must not leave an even number of piles containing one coin each. We can lay out the problem as follows, with three piles containing, say, 3, 4, and 5 coins, respectively Pile(1) Pile(2) Pile(3) 11 (pile(1) in binary) ------- ------- --------- 100 (pile(2) in binary) *** **** ***** 101 (pile(3) in binary) ----- 212 = Sum of columns We want the sum of each column to be even (or zero), and we can do this by making pile(1) = 1 instead of 11. So we reduce pile(1) to 1. This means we must take 2 coins from pile(1). We then get: 1 100 101 ----- 202 This is now a winning position. When the opponent takes any coins he is bound to leave some column odd, and you can repeat above calculation to get back to each column having an even total. As mentioned before you must not leave an even number of piles with one coin in each (this does give an even sum to the column 2^0), and in this case you must leave an ODD number of piles with one coin in each pile. - Doctor Anthony, The Math Forum http://mathforum.org/dr.math/
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum