baines@utecfc.UUCP (Ian Totman) (09/14/84)
I would be interested to know if anyone knows WHY the following solution
to a common type of game works.
The game: You have 'n' piles of sticks, each containing any number of sticks
You and another player alternate removing sticks (from any pile,
and any number up to the number in that pile) until one of you ends
up being able to take the last stick (or sticks, but again, remember
you can only take from one pile)
The person to take the last stick WINS
I saw a solution to this in an old BASIC programming manual actually, and
the method follows:
-convert the number in each pile into binary
-line them up vertically, right justified
-add each column (they will be either odd or even - 0 is even)
-the idea is to subtract a number from one pile to make it so that
each column becomes EVEN
-continue and you win
Two (obvious?) notes: If you get at least one 'odd' column, you can subtract
a number to make all columns even.
If all columns are 'even', whatever your opponent
takes away will make at least one column 'odd'.
Example: 3 piles with 5 4 and 3 sticks
this gives - 101
100 (binary)
011
If it is your move you have a forced win. Subtracting 2 from
the pile originally with three leaves you in an 'even' situation.
Anyone know why? THANKS
Ianmwm@ea.UUCP (09/28/84)
I'm not sure this should go to the net, but...
Take the two points about the sum you already have:
/***** ea:net.math / utecfc!baines / 3:25 am Sep 25, 1984 */
Two (obvious?) notes: If you get at least one 'odd' column, you can subtract
a number to make all columns even.
If all columns are 'even', whatever your opponent
takes away will make at least one column 'odd'.
Anyone know why? THANKS
Ian
/* ---------- */
Now, consider the nim-sum if you have just won the game. It's even. Therefore,
any move that leaves the game in an odd state *can't* be a winning move. So
by leaving the game in any even state, you insure that your opponent can't
win. Since somebody has to win (no loops), and your opponent can't win,
you win.
Note that most take-away games can be won by a similar strategy.
I recommend the books "Winning Ways" (two volumes) by Berlekamp, Conway and
Guy. You can get them from Academic Press, but they are expensive. The
first one ("Games in General") stands alone, and explains nim (among other
things). The second one ("Games in Particular") assumes that you've read
the first one.
<mikeecl@hocsj.UUCP (09/30/84)
> >I would be interested to know if anyone knows WHY the following solution >to a common type of game works. >The game: You have 'n' piles of sticks, each containing any number of sticks > You and another player alternate removing sticks (from any pile, > and any number up to the number in that pile) until one of you ends > up being able to take the last stick (or sticks, but again, remember > you can only take from one pile) > The person to take the last stick WINS > >I saw a solution to this in an old BASIC programming manual actually, and >the method follows: >-convert the number in each pile into binary >-line them up vertically, right justified >-add each column (they will be either odd or even - 0 is even) >-the idea is to subtract a number from one pile to make it so that >each column becomes EVEN >-continue and you win > >Two (obvious?) notes: If you get at least one 'odd' column, you can subtract >a number to make all columns even. > If all columns are 'even', whatever your opponent >takes away will make at least one column 'odd'. > >Example: 3 piles with 5 4 and 3 sticks >this gives - 101 > 100 (binary) > 011 > If it is your move you have a forced win. Subtracting 2 from >the pile originally with three leaves you in an 'even' situation. > >Anyone know why? THANKS > Ian > I don't know if anyone has answered this on yet. I get news very late. However since I answered this one for myself earlier this year, let me show you what I came up with. Define the OR of a set of natural numbers to be the result you get when you convert them to binary, put them in colunms so the digits line up as described above, and do an exclusive-or on the columns (or add them mod 2). Hence the OR of the set {2,3,4} is 5. See directly below. 10 11 100 --- 101 Call a set of numbers balanced if its OR is zero. {1,2,3} is balanced. Lemma I: If you have a balanced set of positive integers, any reduction or elimination of one of the integers leaves the set unbalanced. Proof: This comes out of the observation that in a balanced set each number is the result of OR-ing the all the other numbers together. Given n-1 numbers of an n-element balanced set, the n-th number is uniquely determined. Lemma II: Given any set that is not balanced, a single reduction or elimination of one of the numbers is all that is required to balance the set. Proof: The set is unbalanced, so OR it and get the result. Eliminate leading zeros on the result. If the result is k-binary digits with a 1 k-digits from the right, that 1 got there somehow, at least one of numbers in the set has also has a 1 k places from the right. In the {2,3,4} example above, there is only one choice. 101 has a its leftmost 1 three places from the right and in the list above only 100 has a 1 in the same place, so that is the number that must be chosen. exclusive-or the OR of the whole set with the chosen number. The result has to be to lower its value or eliminate it because you are affecting only the rightmost k binary digits and you are changing the k-th from the right from a 1 to a 0. In the example above we exclusive-or 100 with 101, get 001 (or 1) and replace 100 with the result. This turns {2,3,4} into {2,3,1} which is a balanced set. It follows from the above two lemmas that in the game, if you can ever give your opponent a balanced set, his move must unbalance it and on your move you can again balance it. The pair of moves will simply replace a balanced set with a somewhat reduced balanced set. In the game as described above, you simply follow this procedure until you leave your opponent with will smallest balanced set, the null set. The way I learned the game, you want to leave your opponent taking the last one. This calls for only a minor modification of strategy. You do not want to follow the above strategy all the way down since the smallest balanced set leads to your losing. You simply add an overriding rule that your must never leave your opponent with only ones and at the same time an even number of ones, but that is very easy to avoid on the last round in which you reduce the last number greater than two. You know it is you who will be doing that because a set with only one number greater than 1 cannot be balanced! I have implemented this strategy in a NIM playing program that always wins as long as its opponent does not always give it a balanced set. (Evelyn C. Leeper for) Mark R. Leeper ...ihnp4!lznv!mrl