Re: [[math-fun] Nim-like game]
"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
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
If each heap has its own last-number-taken counter, the Nim/Sprague/Grundy analysis below still applies [for sums]
The misere analysis may not go through for sums so simply (although it may; I haven't checked). Here's an example of a similar, probably simpler game that is easy to work out in normal and misere play for single heap positions (each one has grundy number 0,1, or 2 in both normal and misere play), but for which heavier weapons need to be shouldered to handle misere sums: On Pascal's triangle, place a bean. Two players take turns move it up and to the left, or up and to the right, until the boundary is reached (binomial coefficient 1). This can be solved for multiple beans in misere play but one has to drag out the genus theory of disjunctive sums (or something equivalent) to do it... Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.qxmail.com/ehome.htm ----- Original Message ----- From: "Scott Huddleston" <scotth@ichips.intel.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Wednesday, July 30, 2003 10:06 PM Subject: Re: [[math-fun] Nim-like game]
If each heap has its own last-number-taken counter, the Nim/Sprague/Grundy analysis below still applies.
Illustration of the pascal triangle genus computation, for the genus-theoretic cognoscenti http://www.qxmail.com/journal/pascaltriangle.jpg Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.qxmail.com/ehome.htm ----- Original Message ----- From: "Thane Plambeck" <thane@best.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Wednesday, July 30, 2003 10:26 PM Subject: Re: [[math-fun] Nim-like game]
If each heap has its own last-number-taken counter, the Nim/Sprague/Grundy analysis below still applies [for sums]
The misere analysis may not go through for sums so simply (although it may; I haven't checked).
Here's an example of a similar, probably simpler game that is easy to work out in normal and misere play for single heap positions (each one has grundy number 0,1, or 2 in both normal and misere play), but for which heavier weapons need to be shouldered to handle misere sums:
On Pascal's triangle, place a bean. Two players take turns move it up and to the left, or up and to the right, until the boundary is reached (binomial coefficient 1).
This can be solved for multiple beans in misere play but one has to drag out the genus theory of disjunctive sums (or something equivalent) to do it...
Thane Plambeck 650 321 4884 office 650 323 4928 fax http://www.qxmail.com/ehome.htm ----- Original Message ----- From: "Scott Huddleston" <scotth@ichips.intel.com> To: "math-fun" <math-fun@mailman.xmission.com> Sent: Wednesday, July 30, 2003 10:06 PM Subject: Re: [[math-fun] Nim-like game]
If each heap has its own last-number-taken counter, the Nim/Sprague/Grundy analysis below still applies.
_______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
Neat. What do 1 and 2 imply? If the increase range is generalised to l<=i<=r (l=1, r=2 is my original example - generally l>=0), how can you predict which player will win? For the multiple heaps version, if a player can only remove from 1 heap at a time, which the additional play that if a player can exhaust a heap this signifies the end of their turn (i.e. they can pre-empt having to take k buttons), there are 2 options - the next player only need take i more buttons than the previous player took, or the pre-empting player can state how many they took and the next player must take more than this. Jon Perry perry@globalnet.co.uk http://www.users.globalnet.co.uk/~perry/maths/ http://www.users.globalnet.co.uk/~perry/DIVMenu/ BrainBench MVP for HTML and JavaScript http://www.brainbench.com -----Original Message----- From: math-fun-bounces@mailman.xmission.com [mailto:math-fun-bounces@mailman.xmission.com]On Behalf Of Christian G. Bower Sent: 30 July 2003 22:09 To: math-fun Subject: Re: [[math-fun] Nim-like game] "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 _______________________________________________ math-fun mailing list math-fun@mailman.xmission.com http://mailman.xmission.com/cgi-bin/mailman/listinfo/math-fun
participants (4)
-
Christian G. Bower -
Jon Perry -
Scott Huddleston -
Thane Plambeck