🚀 go-pugleaf

drake@Autodesk.COM (Dan Drake) writes:
< 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:
 
[Statement of rules omitted]

But of course I got it wrong in my previous post.  Piles consisting of
a single stone are a special case.  Here we go again.

If all piles consist of a single stone, you have no control: you'll win
if and only if you're presented with an even number of them, obviously.

If exactly one pile has more than one stone, remove either the whole
pile or all but one stone, ending with an *odd* number of single stones.

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.

Maybe you could consdense these rules by treating the low-order bit as a
special case, but I've wasted enough time and bandwidth on this already,
no?

--
Dan Drake
drake@Autodesk.com