🚀 go-pugleaf

ajayshah@almaak.usc.edu (Ajay Shah) writes:
+ vic@vulcan.anu.edu.au (Glenn Dickins) writes:
+ 
+ +Hi Im not sure if this is the correct group I
+ No it's not.
+ 
+ +there are 3 piles of stones 1 pile with 3 stones 1 with 5 stones and the last with 7 stones.
+ +Anyway, u can take anynumber of stones from 1 pile must be + 1, and u go first, and someone else
+ +then takes 1 or more stones from a pile, the person taking the last stone loses.
+ This game is called nim.
+ The winning strategy works as follows:
+ you throw the other guy into losing positions.
+ They are: n,n; 1,1,1; 3,2,1; 5,4,1
+ To get there, move first, and take one stone (from any pile).
+ 
+ I calculated this the painful way 15 years ago.  Is there a good theory
+ for it?
+ 
+         -ans.
+ -- 
+ Ajay Shah, (213)749-8133, ajayshah@usc.edu

Yes, there's an algorithm for it, for an arbitrary starting condition.
(Picked it up from Fun With Mathematics, by Jerome S.  Meyer, in the
50s.  If I could just remember what's going on now as well as I remember
the things I happened on before I was 20...)  Much modified from Meyer's
presentation:

If there's one pile, or 2 piles, of which has just one stone, you can
reduce it to a single stone.  Go for it.

Otherwise, express the number of stones in each pile in binary and take
the bitwise exclusive-OR of the numbers.  If this is all zeroes, you've
got a losing position; take a stone and hope he blunders.

If it's not all zeroes, take stones from the largest pile to make it all
zeroes.


Try it.

Proof is left to the reader.  That is, it's not hard to see that if you
present him with even parity, he has to break it an present you at least
one odd bit; not too hard to see how to create all even parity if you're
given any odd bit; but the induction steps that prove that this will
win the game are too much work.

--
Dan Drake
drake@Autodesk.com