Relay-Version: version B 2.10 5/3/83; site utzoo.UUCP
Posting-Version: version B 2.10 beta 3/9/83; site utecfc.UUCP
Path: utzoo!utcsrgv!utai!uthub!utecfa!utecfc!baines
From: baines@utecfc.UUCP (Ian Totman)
Newsgroups: net.math
Subject: game solution - why does it work?
Message-ID: <12@utecfc.UUCP>
Date: Fri, 14-Sep-84 00:06:12 EDT
Article-I.D.: utecfc.12
Posted: Fri Sep 14 00:06:12 1984
Date-Received: Fri, 14-Sep-84 13:35:16 EDT
Organization: U of T Mech Engg
Lines: 33


 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