Conference rusure::math

    With 127 markers, the second player to go wins.
    
    Let f(x,y) = 1 if a player can win the position with x markers in
    the pile and the last move was to take y markers out of the pile,
    and let f(x,y) = 0 otherwise.  Then if any of f(x-i,i)
    0 < i <= y+1 are 0, then taking i markers will put the opponent
    into a losing position.  Next, define f(0,i) = 0 for all i, since
    if you want to move and there are no markers left, you just lost.
    Now, we have a recurrence which a program will be happy to crank
    out, which will show that f(127,0) = 0, and the first player to
    move loses.
    
    As an interesting note, looking at who wins as a function of the
    size of the starting pile, there is a cycle with a period of 5:
    
    A = first player wins, B = second player wins
    
    		0	B
    		1	A
    		2	B
    		3	B
    		4	A
    		    .
    		    .
    		    .
    
    This is all empirical evidence.  As of yet, I don't have any math
    to back up these observations.
    				Jeff
    

    If M is divisible by N+1 then the second player can force a win.
    
    Strategy:
    
    	No matter how much the first player takes, always take enough to
    add up to N+1. This is always possible.  Eventually the pile will
    be reduced to N+1 stones.  Using the same rule, the second player
    will force a win.
    
    
    If M is not divisible by N+1 then #1 can force a win.
    
    Strategy:
    
    	Let R = Mod (M)
    		       N+1
    	Player number 1 should take R stones the first time.  Now since
    there are X*(N+1) stones remaining, and ity is #2's turn, #1 can
    use the first strategy listed here.
    
    -- Barry
    
                    
    

But N varies -- it's the number of markers removed by the previous player.

You're probably thinking of a similar NIM-like game, in which each player
removes from 1 to N markers, where N is fixed.

    As already noted, if you start with 127 markers then the second
    player wins. The way I've worked it out, assuming correct play,
    the following starting numbers are forced losses for the first
    player :
    	5     10     15      20     25     30  .....
    2,3   7,8   12,13  17,18   22,23  27,28    .....
    
    And the following are forced wins for the first player :
    
  1    4 6    9 11   14 ............
    
    The strategy would be to take the minimum no. so that you force
    you opponent to stay on the losing nos. 
    
    I tried this is a pub, yesterday, with coins, and the winner keeps
    the coins, and got chased out of the pub !.
    
    What I still need to work out is why the multiples of 5 is siginficant.
    I can see it instinctively, but cant put in maths yet.
    
    Off the subject, 4 or 5 years back, I remembe writing a program
    to play NIM, ( N piles, M(I) on each pile, take as many from pile
    except can only empty a pile if only 1 in it. ). The program used
    to represent the piles in binary and do a sort of binary addition
    "across" the piles, to work out the correct move. In that case I
    never did work out the significance of binary representation.
    The "how to " seems to be easy, the "why" not so easy.
    
    Regards,
    Shantanu Karve @REO
    

    	The solution presented here was incomplete. It assumed that both 
    players move optimally. But if your opponent makes a wierd (and losing) 
    move, how do you respond? As the pattern extends, its apparent symmetry
    mod 5 disappears, and in fact there's a rather interesting shape.
    
    	As in .1, let's define:
    
    	f(x,y) = value of the game if there are x markers, and the last
    move took y markers from the pile. Let the value be 1 if the position
    is a win, 0 if its a loss.
    
    	Trivial remarks include:
    
    	f(0,y) = 0 for all y
    	f(x,x-1) = 1 for all x > 0
    	f(x,y) =< f(x,y+1) for all x & y
    
    	Define m(x) = min{y|f(x,y)=1}
    
    	m(x) is well-defined for all x > 0. Let's write m(0) = % (infy)
    
    
    Allegation:
    
    	m(5k+1) = 0
    	m(5k+2) = 1
    	m(5k+3) = 2
    	m(5k+4) = 0
    	m(5k) = 5d-1, where d is the largest power of 2 dividing k
    

    Proof by induction:
    
    Base case:
    	m(0) = %, as desired
    
    Inductive step:
    We will take the following approach. We will forget for a moment about
the history of a position. We will just attempt to find out what is the
smallest number of markers we need to remove to win. This tells us what m(x)
must be, to render that winning move legal!
    	x=5k+1:
    		f(5k,1) = 0, so m(5k+1) = 0
    	x=5k+2:
    		f(5k+1,1) = 1
    		f(5k,2) = 0, so m(5k+2) = 1
    	x=5k+3:
    		f(5k+2,1) = 1
    		f(5k+1,2) = 1
    		f(5k,3) = 0, so m(5k+2) = 2
    	x=5k+4:
    		f(5k+3,1) = 0, so m(5k+4) = 0
    	
    	x=5k: (The trickier one.) Say q = 1,2,3 or 4
    		f(5k+5-(5m+q),5m+q) >= f(5k+5-(5m+q),q) = f(5-q,q) = 1
	So the only possibly safe move is to remove a multiple of 5.
	Let d be the largest multiple of 2 dividing k.

	Suppose we remove 5l < 5d markers.
	f(5k-5l,5l) = f(5(k-l),5l)
	The highest multiple of 2 dividing l is d' < d
	Since 5l > m(5(k-l)) = 5d'-1, f(5(k-l),5l) = 1
	So removing 5l markers is a losing move.
	
	Suppose on the other hand that we remove 5d markers.
	f(5k-5d,5d) = f(5(k-d),5d). 
	The highest multiple of 2 dividing k-d is 2d. 
	Since 5d < m(5(k-d)) = 10d-1 (the critical value), f(5(k-d),5d) = 0.
	So removing 5d markers is a winning move.

	Therefore m(5k) = 5d-1
    
    	I have a feeling that I looked at this puzzle when I was 13 or 14
    on holiday near Dubrovnik, in what was then Yugoslavia. I got the mod 5
    business, but not the abacabad stuff for 5k.
    
    Cheers,
    Andrew.