"Jon Perry" <perry@globalnet.co.uk> wrote:
Let there be n buttons. A player may take 1 or 2 buttons MORE than his/her opponent took. Player 1 can take either 1 or 2 buttons.
e.g. 28->27->25->21->15->7->0
(the last player must take either 8 or 9, as only 7 remain, they must take them all).
I threw this together quickly, so I apologize for any errors: In the case where winner takes the last button: I can model the Nim values as follows: f(n,k) is the Nim value for n buttons remaining, last player took k buttons. If n=0, value is 0 if 1 <= n <= k+1 value is 1 otherwise value is mex( f(n-k-1,k+1), f(n-k-2,k+2) ) where mex is the smallest nonegative integer not in the set [i.e. mex(0,0) = 1, mex(0,1) = 2, mex(1,1) = mex(1,2) = mex(2,2) = 0 With this I get for f(n,0) 1 : 1 2 : 2 3 : 0 4 : 0 5 : 2 6 : 1 7 : 1 8 : 1 9 : 2 10 : 2 11 : 0 12 : 0 13 : 0 14 : 0 15 : 2 16 : 2 17 : 1 18 : 1 19 : 1 20 : 1 21 : 1 22 : 2 23 : 2 24 : 2 25 : 0 26 : 0 27 : 0 28 : 0 29 : 0 30 : 0 For the zeroes of f(n,0) (those n from which the second player can win) I get: 3-4 11-14 25-30 45-52 71-80 103-114 141-154 185-200 235-252... The lower limits seem to follow the pattern: 3 3+8=11 11+14=25 25+20=45 ... with the increment going up by 6 each time. The size of the ranges: 2, 4, 6, 8... If player who takes the last piece loses: the analysis is similar: g(n,k): If n=0, value is 1 if 1 <= n <= k+1 value is 0 otherwise value is mex( g(n-k-1,k+1), g(n-k-2,k+2) ) 1 : 0 2 : 2 3 : 1 4 : 1 5 : 2 6 : 0 7 : 0 8 : 0 9 : 2 10 : 2 11 : 1 12 : 1 13 : 1 14 : 1 15 : 2 16 : 2 17 : 0 18 : 0 19 : 0 20 : 0 21 : 0 22 : 2 23 : 2 24 : 2 25 : 1 26 : 1 27 : 1 28 : 1 29 : 1 30 : 1 with zeroes at 1 6-8 17-21 34-40 57-65 86-96 121-133 162-176 Lower limits 1 1+5=6 6+11=17 17+17=34 ... again the increments incrementing by 6 the ranges being 1, 3, 5, 7... this time
What are the strategies for various n, with either last button wins/loses?
Well, I didn't go the extra distance to detail the strategy, but it doesn't look too difficult. Christian