Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Two players are playing a stone-picking game.

There are some piles of stones. The number of stones in each pile is given.

Every player takes action in turns as following rules:

  • The one in his turn chooses a pile of stones. Let's denote the number as A.
  • Then the same player chooses a number B with 0<2*B<=A.
  • 2B stones are moved from the original pile,
  • and a new pile with A-B stones is added.

Then one who can not take a action as above rules describe will lose the game.

Suppose everyone is clever enough. Determine whether the first one or the second one will win.

This problem is a very common stone game. The common solution is to calculate the Sprague-Grundy function value as the definition and then find some rules. After this try to prove the rules holds for all situations.

My problem is that the SG function values in small cases seem very irregular. Can anyone help me? Or if there is other solution?

sg[0] = 0, sg[1] = 0, sg[2] = 1, sg[3] = 0

sg[4] = 0, sg[5] = 1, sg[6] = 2, sg[7] = 2

sg[8] = 1, sg[9] = 0, sg[10] = 0, sg[11] = 1

sg[12] = 0, sg[13] = 0, sg[14] = 1, sg[15] = 2

sg[16] = 2, sg[17] = 1, sg[18] = 4, sg[19] = 4

sg[20] = 1, sg[21] = 4, sg[22] = 4, sg[23] = 1

sg[24] = 2, sg[25] = 2, sg[26] = 1, sg[27] = 0

sg[28] = 0, sg[29] = 1, sg[30] = 0, sg[31] = 0

sg[32] = 1, sg[33] = 2, sg[34] = 2, sg[35] = 1

sg[36] = 0, sg[37] = 0, sg[38] = 1, sg[39] = 0

sg[40] = 0, sg[41] = 1, sg[42] = 2, sg[43] = 2

sg[44] = 1, sg[45] = 4, sg[46] = 4, sg[47] = 1

sg[48] = 4, sg[49] = 4, sg[50] = 1, sg[51] = 2

sg[52] = 2, sg[53] = 1, sg[54] = 7, sg[55] = 7

sg[56] = 1, sg[57] = 7, sg[58] = 7, sg[59] = 1

sg[60] = 2, sg[61] = 2, sg[62] = 1, sg[63] = 7

sg[64] = 7, sg[65] = 1, sg[66] = 7, sg[67] = 7

sg[68] = 1, sg[69] = 2, sg[70] = 2, sg[71] = 1

sg[72] = 4, sg[73] = 4, sg[74] = 1, sg[75] = 4

sg[76] = 4, sg[77] = 1, sg[78] = 2, sg[79] = 2

sg[80] = 1, sg[81] = 0, sg[82] = 0, sg[83] = 1

sg[84] = 0, sg[85] = 0, sg[86] = 1, sg[87] = 2

sg[88] = 2, sg[89] = 1, sg[90] = 0, sg[91] = 0

sg[92] = 1, sg[93] = 0, sg[94] = 0, sg[95] = 1

sg[96] = 2, sg[97] = 2, sg[98] = 1, sg[99] = 4

share|improve this question
    
@WillieWong sorry, I forget it. The criterion is added. –  konjac May 14 '12 at 10:56
    
@WillieWong zero is not allowed, otherwise the game maybe never ends. –  konjac May 14 '12 at 11:04
add comment

1 Answer

up vote 2 down vote accepted

The SG-function is defined by $SG(n) := mex\{SG(n-2m) \stackrel{*}{+} SG(n-m) : 0 < 2m \leq n\}$. The following pattern emerges when you look at $SG(n)$ for $n$ mod $9$ fixed:

0 0 1 0 0 1 2 2 1
0 0 1 0 0 1 2 2 1
4 4 1 4 4 1 2 2 1
0 0 1 0 0 1 2 2 1
0 0 1 0 0 1 2 2 1
4 4 1 4 4 1 2 2 1
7 7 1 7 7 1 2 2 1
7 7 1 7 7 1 2 2 1
4 4 1 4 4 1 2 2 1
0 0 1 0 0 1 2 2 1
0 0 1 0 0 1 2 2 1
4 4 1 4 4 1 2 2 1
0 0 1 0 0 1 2 2 1
0 0 1 0 0 1 2 2 1
4 4 1 4 4 1 2 2 1
7 7 1 7 7 1 2 2 1
7 7 1 7 7 1 2 2 1
4 4 1 4 4 1 2 2 1
8 8 1 8 8 1 2 2 1
8 8 1 8 8 1 2 2 1
4 4 1 4 4 1 2 2 1
8 8 1 8 8 1 2 2 1
8 8 1 8 8 1 2 2 1
4 4 1 4 4 1 2 2 1
7 7 1 7 7 1 2 2 1
7 7 1 7 7 1 2 2 1
4 4 1 4 4 1 2 2 1
0 0 1 0 0 1 2 2 1
0 0 1 0 0 1 2 2 1
4 4 1 4 4 1 2 2 1
0 0 1 0 0 1 2 2 1
0 0 1 0 0 1 2 2 1
4 4 1 4 4 1 2 2 1
7 7 1 7 7 1 2 2 1
7 7 1 7 7 1 2 2 1
4 4 1 4 4 1 2 2 1
0 0 1 0 0 1 2 2 1
0 0 1 0 0 1 2 2 1
4 4 1 4 4 1 2 2 1
0 0 1 0 0 1 2 2 1
0 0 1 0 0 1 2 2 1
4 4 1 4 4 1 2 2 1
7 7 1 7 7 1 2 2 1
7 7 1 7 7 1 2 2 1
4 4 1 4 4 1 2 2 1
8 8 1 8 8 1 2 2 1
8 8 1 8 8 1 2 2 1
4 4 1 4 4 1 2 2 1
8 8 1 8 8 1 2 2 1
8 8 1 8 8 1 2 2 1
4 4 1 4 4 1 2 2 1
7 7 1 7 7 1 2 2 1
7 7 1 7 7 1 2 2 1
4 4 1 4 4 1 2 2 1

These are the first $486$ values. The next number is, unfortunately, $11$. Anyway, we can observe the following pattern:

  • Every row seems to have the form $x x 1 x x 1 2 2 1$.
  • Every $3k$th has $x=4$.
  • The other adjacent rows coincide.

If this is true, the whole function is determined by the values $a(k) := SG(9(3k+1)+1)$, which also follow a nice pattern when we fix $k$ mod $3$:

0  0  7
0  0  7
8  8  7
0  0  7
0  0  7
8  8  7
11 11 7
11 11 7
8  8  7
0  0  7
0  0  7
8  8  7
0  0  7
0  0  7
8  8  7
11 11 7
11 11 7
8  8  7
13 13 7
13 13 7
8  8  7
13 13 7
13 13 7
8  8  7
11 11 7
11 11 7
8  8  7
0  0  7
0  0  7
8  8  7
0  0  7
0  0  7
8  8  7
11 11 7
11 11 7
8  8  7
0  0  7
0  0  7
8  8  7
0  0  7
0  0  7
8  8  7
11 11 7
11 11 7
8  8  7
13 13 7
13 13 7
8  8  7
13 13 7
13 13 7
8  8  7
11 11 7
11 11 7
8  8  7
14 14 7
14 14 7
8  8  7
14 14 7
14 14 7
8  8  7
11 11 7

The pattern is similar to the one above: Every row has the form $x x 7$, where every third $x$ is $8$, and the other adjacent ones coincide. Now if this is also true, $a$ only depends on the values $a(3(3j+1)+1)$, which again satisfy a similar pattern (the rows now have the form $x x 11$, and every third $x$ is $13$). I don't know if this kind of analysis will solve the game, but it already shows that the SG-function contains a lot of "nested" periodicity. And perhaps this already suffices to determine when $SG(n)=0$, i.e. when the second player has a winning strategy.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.