The analysis below by "Christian G. Bower" <bowerc@usa.net> takes care of an isolated single heap. How does this variant behave in a sum of games? If each heap has its own last-number-taken counter, the Nim/Sprague/Grundy analysis below still applies. But what about a collection of piles, with the required-to-take counter incrementing globally for all piles? Or how would you play a required-to-take component along with some other component(s), where you increment the required-to-take component's minimum (by 1, say) when you move outside the required-to-take component? - Scott
"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