The Stone Game

We will start with small values of $n$ to see which positions are winning and which are losing. We will assume both players play optimally. For $n = 1, 2$ , the first player can win by taking the whole pile. If $n = 3$ , the first player cannot win, since he can only take one or two stones, leaving 2 or 1 respectively, from which we know the second player can win. In general, a position is a winning position if the player can either win the game from that position or move the game to a losing position. A position is a losing position if any move that player makes leaves the game in a winning position for the other player. Using this, and what we know about the game for $n = 1, 2, 3$ , we get the following table for the first several positions:

$\begin{array}{c|cccccccccc} n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15\\ \hline \mbox{Win/Lose} & W & W & L & W & W & W & L & W & W & L & W & W & L & W & W\\ \end{array}$

We will show by induction that for $k\geq 4$ , $3k+1$ is a losing position and $3k$ and $3k+2$ are winning positions for player 1. Note that we have established that base case for $k=2, 3$ , and we proceed by induction. For the case of $3k$ , we can remove 2 stones to get $3(k-1) + 1$ , which is a losing position. For the case of $3k+1$ , each possible moves takes us to a position of the form $3j$ or $3j+2$ for some $j$ . Since $k\geq 4$ in the induction step, we know that $j\geq 2$ even when half the stones are removed. For the case of $3k+2$ , we can remove 1 stone to get $3k + 1$ , which is a losing position.

Thus we have that from $1$ to $8 + 3k$ there are exactly $k +2$ losing positions. And $500 = 8 + 3 \times 164$ , so there are 166 losing positions between 1 and 500, and $500 - 166 = 334$ winning positions.

Let the first player is A and the second is B . First we think that A and B wanted to win the game and have a strategy to win the game. It’s clear that for n = 1,2 , A can win obviously. But for n = 3 , A cannot do the strategy and must be lose. First we can conclude if B win the game for n = k , so for n = k+1,k+2, 2k , there are no way B to win the game. Because A can take 1, 2 or half of the stones for k+1,k+2,2k respectively and give remainder n to B where B will be lose. The winner for n = ... is... n=1 \rightarrow A n=2 \rightarrow A n=3 \rightarrow B so n=4,5,6 \rightarrow A Because n=5,6 \rightarrow A .So we cannot ensure the winner is A for n =7 so n =7 \rightarrow B From n = 7, for n=8,9,14 \rightarrow A and n=10 \rightarrow B and so on So there is a pattern A,A,B,A,A,A,B,A,A,B,A,A,B,A,A,B,A,A,.... Which is B is periodic after n=7. We can see that there are 166’s B. And It’s clear that there are 500-166 = 334’s A

Let a -> b denote that there are a stones, then you can turn it into a position with b stones in one move.

1 -> 0

2 -> 0

3 -> (1,2) winning positions, so 3 is a losing position

4 -> 3

5 -> 3

6 -> 3

7 is a losing position. And now note that 10, 13, 16, ..., 499 are losing positions. (since the even numbers leaves remainder 1 when divided by 3, so half the number will not be any of the losing positions). So, there are 500 - 166 = 334 winning positions.

For n = 1 and n = 2, Player 1 picks up the 1 or 2 stones and wins. For n = 3, if Player 1 picks either 1 or 2 stones up, Player 2 is left with either 2 or 1 stone(s), and Player 2 wins. For n = 4, n = 5, and n = 6 Player 1 picks up 1, 2 or 3 stones (respectively), forcing Player 2 to pick from the 3 remaining stones. [Note that for n = 6, Player 1 can pick up 3 stones because the number of stones in the pile is even.] From the earlier argument for n = 3, Player 2 cannot win if Player 1 plays optimally. For n = 7, Player 1 can pick up 1 or 2 stones, and Player 2 will have either 6 or 5 stones remaining. From the earlier argument for n = 5 and n = 6, Player 2 is guaranteed to win if he plays optimally. A pattern can then be noticed if the process is continued, as for every game n where Player 2 wins, Player 1 can guarantee a win for games n+1 and n+2. Player 2 can therefore win games for n = 7, 10, 13, 16...499. This arithmetic sequence has 165 terms. Since Player 2 also wins for n = 3, Player 2 can win a total of 166 games. Therefore, Player 1 can win 500 - 166 = 334 games.

For the first player to win the game there are mainly 1 condition and 1 strategy. They are-

1. there should be in total, odd number of moves (considering both the players) for the first player to win when they play optimally. i.e consider $n=1$ then the first player wins, $n=2$ the first player wins but $n=3$ the first player has a chance of losing. this is because in first two conditions there were odd number of moves to complete. But when its $3$ stones, there are $2$ moves i.e if the first player draws $1$ or $2$ stones, the second player gets the chance to draw the last stone. So, making $2$ moves to remove all the stones. Hence, if the first player has to remove the last stone then there should be odd number of moves to finish it.

So, in order to have odd number moves $n \neq 3$ and other number similar to $3$ .

2. Now the strategy is that, the first player has to remove the favorable number of stones i.e either $1$ , $2$ or half of the stones if even such that after the removal, the number stones left for the second player to play should leave even moves to complete. For eg. if $4$ or $5$ are left then the first player has to remove $1$ or $2$ stones respectively so that $3$ stones are leftover for the second player. By doing so, every time the first player always wins.

Now considering $3$ stones the first player can't win. But when there are $4$ or $5$ stones the first player has a chance of winning. Generalizing it, if the first player can't win when there are $n$ stones then the player can win when there are $n+1$ or $n+2$ stones. So, the next number that the first player is unable to win is $n+3$ . But this is not true for $n + 3 = 6$ because it is possible to remove 6 stones with odd number of moves. So, the next number after $3$ is $7$ for which the first player can't win.

But there may or may not be other numbers similar to $6$ such that $n+3$ is the number of stones for which the first player can win. In order to know this, lets consider numbers after $7$ for which the first player can't win. They are of the form $7+3x=2y$ where $x,y \epsilon N$ . Here, $y$ should always have values for which the first player can’t win. This is because considering $6$ stones itself. The first player reduces it to half leaving 3 stones to second player. And thus ensuring that second player can’t win.( strategy ).

$\Rightarrow 7+3x=2(7+3z)$ where $z<x$ and $x,z \epsilon N$ . This is because $y=7+3z$ ( values for which the first player can’t win). Thus on simplifying we get $3x=7+6z$ . Here there are no positive integral value of $z$ , for which $7+6z$ is a multiple of $3$ . Thus numbers similar to 6 don’t exist.

Enough with explanation. Now coming to enumeration. $7+(n-1)3 \leq 500$ (Using A.P )

$n \leq 165.333$ Since, $n \epsilon N$ . $\Rightarrow n=165$ . Excluding $3$ .

Therefore, including $3$ there are $n=166$ values of $n$ from $1$ to $500$ (inclusive) for which the first player loses. Thus, there are $500-166=334$ values of $n$ for which the first player wins when played optimally.

So, the answer is $334$

It's strange that there are so many bad solutions here. I'll give this a try.

Here is our key argument: 1. A pile of 0 stones is a loosing position. 2. If there is at least one move that reduces the game to a loosing position, the current player will by all means take that move.

These leads us to the following pretty much declarative/functional algorithm: 1. If the pile contains 0 stones, this pile is a loosing position. 2. If the pile contains more than 0 stones, check if the available moves can reduce the pile to a loosing position. If so, this is a winning position; else, this is another loosing position.

Since every pile of n stones depends on the previous pile of (n-1),(n-2), etc piles: We should cache the values to avoid recomputation.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19

cache = {}
 def stonegame(n):
    if n in cache:
        return cache[n]
    if n==0:
        cache[n] = False
        return False
    if n >= 2 and not stonegame(n-2):
        cache[n] = True
        return True
    if n >= 1 and not stonegame(n-1):
        cache[n] = True
        return True
    if not n%2 and not stonegame(n/2):
        cache[n] = True
        return True
    cache[n] = False
    return False
sum(map(stonegame,range(1,501)))