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