Modified Nim

Consider the generalised game [n, k], which is identical to the above game, except that starting with an initial n stones, the first player can take up to k stones. We denote a game by 1p or 2p, depending on whether the first or the second player has a winning strategy.

Generic considerations:

1. A game is 1p if there's a move to a 2p game.
2. Conversely, a game is 2p if all moves are to 1p games.

Obviously if $k\ge n$ , then the first player can remove all stones and so [n, k] is a 1p game. Recursively, we get:

[0, k] is 2p since the first player has no move and loses automatically.
[1, 1] is 1p;
[2, 1] is 2p, [2, 2] is 1p;
[3, 1] is 2p, [3, 2] is 2p, [3, 3] is 1p;
[4, 1] is 1p, [4, 2] is 1p, [4, 3] is 1p, [4, 4] is 1p;
[5, 1] is 2p, [5, 2] is 2p, [5, 3] is 2p, [5, 4] is 2p, [5, 5] is 1p; ...

First claim:

For each n>0, there's a j for which [n, k] is 1p for all $k \ge j$ and [n, k] is 2p for all k<j.

For this j, [n-j, 2j] is a 2p position.

Proof :

Let j be the smallest positive integer for which [n, j] is 1p. Since [n, n] is 1p such a j clearly exists. Since [n, j] is 1p, there's a move to a 2p position. By minimality of j, [n, j-1] is 2p so the said move is not available here. Hence, the move must be to [n-j, 2j]. This move is also available to [n, k] for all $k\ge j$ so [n, k] is a 1p position. (QED).

Let f(n) denote the j in the above claim. We thus have: - f(0) = infinity; - f(1) = 1; - f(2) = 2; - f(3) = 3; - f(4) = 1; - f(5) = 5 ...

From the claim, f(n) is the smallest k for which [n-k, 2k] is a 2p position. But [n-k, 2k] is 2p if and only if f(n-k) > 2k. Hence:

Main Result

f(n) = smallest positive integer k for which f(n-k) > 2k.

Second Claim:

Given a positive integer n, express n as a sum of Fibonacci numbers as follows: let $F_a$ be the largest Fibonacci term not exceeding n, then let $F_b$ be the largest Fibonacci term not exceeding $n - F_a$ etc... E.g.

75 = 55 + 13 + 5 + 2.

Then no two consecutive Fibonacci terms occur in the sum. We call this the Fibonacci representation of n.

Proof :

Suppose $F_a$ and $F_{a+1}$ both occur in the sum, and a is maximum. The next higher term is $F_b$ where $b \ge a+3$ . Then the above algorithm, after subtracting $F_b$ , leaves us with a number at least $F_a + F_{a+1} = F_{a+2}$ which contradicts the fact that $F_{a+2}$ is left out. (QED).

Now, the final result.

Third Claim :

f(n) = smallest term in the Fibonacci representation of n.

Proof :

Let $n = F_{a_1} + F_{a_2} + \ldots + F_{a_r}$ where $a_{i+1} \ge a_i + 2$ for each i. We'll prove our claim by induction on n.

Note that $m := n - F_{a_1}$ has Fibonacci representation $F_{a_2} + \ldots + F_{a_r}$ , so by induction hypothesis, f(m) is $F_{a_2} = F_{a_2-1} + F_{a_2-2} > 2F_{a_2-2} \ge 2F_{a_1}$ .

On the other hand, for any $k < F_{a_1}$ , the Fibonacci representation of $m := n-k$ has higher terms $F_{a_2} + \ldots + F_{a_r}$ together with terms strictly smaller than $F_{a_1}$ . By induction hypothesis, f(m) is the smallest term in the Fibonacci representation. Removing higher terms, it suffices to show that if $1 \le m < F_a$ , then the smallest term $F_b$ in the Fibonacci representation of m satisfies $F_b \le 2(F_a-m)$ . Rewrite this as $m + \frac{F_b} 2 \le F_a$ .

To prove that, suppose $F_b > 1$ (otherwise, it's obvious). Then the lowest term of $m + F_{b-1}$ is $F_b + F_{b-1} = F_{b+1}$ . Since the Fibonacci terms for m are spaced apart by at least 2, after simplification the result is at most $F_a$ , i.e. $m + F_{b-1} \le F_a$ which gives $m + \frac {F_b} 2 \le m+F_{b-1} \le F_a$ as desired. (QED).

Conclusion

[n, n-1] is a 2p game if and only if f(n) = n. Since f(n) is the smallest term in the Fibonacci representation of n, this holds if and only if n is a term in the Fibonacci sequence. Hence all numbers are 1p except 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987. Answer = 999 - 14 = 985.

Fibonacci numbers: $F_0=0, F_1=1, F_{k+1}=F_k + F_{k-1}$ If N is a Fibonacci number, then second player has a winning strategy. Proof: Cases N=2, N=3 are obvious. Let $N= F_{k+1}$ . If first player removes $F_{k-1}$ or more stones, the second player can remove the rest of the pile, since $F_{k+1}<3F_{k-1}$ . If first player removes less (or equal) than $F_{k-1}-1$ stones, the second player follows the winning strategy for $F_{k-1}$ to left in the pile $F_{k}$ stones.

If $N$ is not a Fibonacci number, then first player has a winning strategy. Proof: In case $N=4$ ( $N=6$ ) first player removes one stone to left Fibonacci number of stones (3,resp. 5). Let $F_{k}<N<F_{k+1}$ .

If $N-F_{k} \leq \lfloor \frac{F_{k}-1}2\rfloor$ the first player removes $N-F_{k}$ stones to put second in loosing position.

If $N-F_{k}>\lfloor \frac{F_{k}-1}2\rfloor$ then $F_{k-2}<N-F_{k}<F_{k-1}$ , i.e. $N-F_{k}$ is not a Fibonacci number, so first player follows the winning strategy for $N-F_{k}$ to left in the pile $F_{k}$ stones.

Since the Fibonacci numbers between 2 and 1000 are 14 (2, 3, 5, 8,13, 21, 34, 55, 89, 144, 233, 377, 610, 987) the answer is $999-14=985$ .

If you analyze the first few cases, you find that 2 is a first player loss, 3 is a first player loss, 4 lets you move to 3 and win, 5 is a first player loss, 6 lets you move to 6 and win, 7 lets you move to 5 and win, 8 is a first player loss, 9-11 let you move to 8 to win, 12 lets you move to 11 to win, and 13 is a first player loss. The losses are 2, 3, 5, 8, 13, Fibonacci numbers. If this pattern continues, then the first player losses continue 21, 34, 55, 89, 144, 233, 377, 610, and 987 and the complement has size 985. Let's prove this by induction.

Lemma 1: If starting at n is a first player loss, then moving to n either wins if your opponent can't win immediately.

Proof: If your opponent can't win immediately, then your opponent has fewer options than starting at n, which loses.

As a consequence, 14-19 are first player wins by moving to 13. This doesn't establish that 20 is a first player win, since moving to 13 is not a winning move as your opponent can take all 13.

Lemma 2: When you execute a winning strategy from n, your last move takes at most 2n/3 stones.

Lemma 3: For $F_n \ge 5, 2/3 F_{n-1} \lt 1/2 F_n$ where $F_n$ is the nth Fibonacci number.

To win from 20, we can emulate the strategy moving first from 7, ensuring that we move first to 13 and our opponent can't respond by taking all 13 stones left.

Theorem: For $n \ge 2$ , the first player wins iff n is not a Fibonacci number.

Proof: This is true for small cases, checked above. Inductively assume that this is true for all smaller piles. Let $A \lt B\ \lt C$ be the largest Fibonacci numbers smaller than n. $n-C \le B$ by the definition of Fibonacci numbers. If $n \lt 3/2 C$ then move to C and win by Lemma 1, and n is not a Fibonacci number. For $3/2 C \le n \lt C+B$ , $n \gt A+C$ so $n-C$ should be a first player win. Follow the strategy for $n-C$ to move to C with a move smaller than $\frac{2}{3} B \lt \frac{1}{2}C$ , which wins by lemmas 1, 2, and 3. If $n=C+B$ , n is the next Fibonacci number, so we are supposed to show that this is a first player loss. If the first player takes B or more stones, the second can win by taking the rest since $C \lt 2B$ . If the first player starts by taking fewer than B stones, then we emulate the second player winning strategy with C fewer stones to leave C stones while taking fewer than 2/3 B stones on the last move, which wins for us by lemmas 1, 2 and 3. This proves the inductive hypothesis, so the pattern of Fibonacci numbers as the only first player losses continues.

First, note that each positive integer can be written uniquely in Zeckendorf representation as a sum of distinct non-consecutive Fibonacci numbers (e.g. 20 = 2 + 5 + 13).

Second, define a function $f : \mathbb{N} \mapsto \mathbb{N}$ such that $f(n)$ is the smallest positive integer number such that, from a pile of $n$ stones, removing $f(n)$ guarantees a winning strategy. Thus losing positions satisfy $f(n) = n$ , winning positions satisfy $f(n) < n$ .

It is easy to observe that $f(n)$ is the smallest positive integer less than $n$ such that if $m = n - f(n)$ , $f(m) > 2f(n)$ (provided we set $f(0) = \infty$ , because when giving the opponent the pile of $m$ stones, they will have to remove fewer than $f(m)$ stones and thus not be able to guarantee a winning position.

The result we will show is that not only is $f(n)$ always a Fibonacci number, but it is the smallest Fibonacci number in the Zeckendorf representation of $n$ . We will use (strong) induction, noting that $f(1) = 1, f(2) = 2, f(3) = 3$ and $f(4) = 1$ .

Now, suppose that for any $i < k$ , $f(i)$ is as expected. Suppose that the smallest Fibonacci number in the representation of $k$ is $x$ . We will show that $f(k) = x$ .

Note that if we remove $x$ stones, then either $k = x$ and we’ve removed all stones (and so won), or the second smallest Fibonacci number in the representation of $k$ , which is the smallest in $k - x$ , is at least two Fibonacci numbers along from $x$ and thus more than $2x$ (obviously, by considering the recurrence), so $f(k-x) > 2x$ as required (induction hypothesis).

If we remove fewer than $x$ stones, then we will have, say, $(k - x) + y$ stones, and since $y < x$ , the smallest number in the representation of $k - x + y$ is the same as the smallest in $y$ , which is less than $x$ , and so we have thrown ourselves into a losing position.

Thus, the hypothesis is proven by induction, and we have the result. 14 of the 999 numbers in the range are Fibonacci, leaving 985 winning positions.

At first glance I tested if it's possible for the first player to win on a game with two rocks, which is impossible since the only move he can do is to take out one rock, leaving only one rock for the second player who takes it out and wins the game; with three rocks is impossible as well because whether the first player takes one or two rocks out, the second can take the rest, winning the game; for the first player to win he needs to leave the second player with a loser amount of rocks and also not able to take all of this rocks out at once; for example when there's four rocks the first player can leave the second with three rocks, making the second player lose the game; I observed that the first player can do that with all number which are not from the fibonacci sequence, in other words, he loses when there's 2,3,5,8,13,21...rocks and so on; since there are 14 numbers of the fibonacci sequence from 2 to 1000, there are 14 numbers in 999 possibilities in which the first player loses; 999-14=985; so 985 is the answer.

When investigating games it's always useful to pin down all the possible positions and moves between them. First some standard terminology -- we call the position winning or losing if the first player has winning or losing strategy for it. If the position is winning then there must be a move to a losing position (i.e. a move that forces the other player to only have a losing strategory in the new position). If there is no such forcing move then the position is losing.

Having that out of the way, let's describe the possible positions. Note that the position doesn't only depend on $N$ but also on how many stones can be taken, say $k$ . Let $P(N, k) \in \{W,L\}$ denote whether the position $(N,k)$ is winning or losing. For example, $P(2,1) = L$ and $P(N,N) = W$ for all $N$ . The position we are after to solve the problem are $P(N, N-1)$ . Now, to describe the moves, by taking $l \leq k$ stones we can go from $P(N,k)$ to $P(N-l,2l)$ . It's obvious that if $P(N,k) = W$ then also $P(N,k+m) = W$ (just take the same number of stones that worked for the $(N,k)$ position). Therefore it makes sense to introduce new notation: let $H_N$ be the smallest $k$ such that $P(N,k) = W$ . The significance of this is that the position $P(N, N-1)$ is losing precisely when $H_N = N$ .

First few values of $H_N$ can be checked by hand to be $1,2,3,1,5,1,2,8,1,2,3,1,13,1,2,3,1,5,1,2,21,\dots.$ Delighted, we see a pattern emerge. When $N$ is a Fibonacci number $H_N = N$ . And for other values of $N$ there is an obvious relation $H_N = H_{N-f}$ where $f = F_g$ is the closest Fibonacci number smaller than $N$ and moreover $N \leq F_{g-2}$ (for example the numbers between $13$ and $21$ are all less than $5$ ). Postponing a proof of these facts for a little while, we have just shown that the only losing positions are those where $N$ is a Fibonacci number. Because there $14$ such numbers between $2$ and $1000$ the answer to the problem must be $999 - 14 = {\bf 985}$ .

$\bf Proof$ . We'll use induction on $N$ . The base case is proved simply by having listed the start of the sequence above. So suppose we know that the description of the sequence holds for all $m < N$ . There are two cases -- if $N = F_n$ is a Fibonacci number then we know by the induction hypothesis that the values of $H_M$ for $F_{n-1} < M < F_n$ are the same as those for $1 \leq M < F_{n-2}$ . Therefore we have $H_N \geq F_{n-2}$ . So to find the value of $H_N$ we need to take at least $l = F_{n-2}$ stones. But such moves will take us to positions with $k \geq 2F_{n-2} \geq F_{n-1}$ and $N \leq F_{n-1}$ . Because all of these positions are winning (recall that $P(m,m) = W$ for any $m$ ), we must actually have $H_N = N$ as was to be shown.

It remains to analyze the case when $N$ is not a Fibonacci number. Denote by $f = F_g$ the nearest smaller Fibonacci number. By the induction hypothesis we have that the values of $H_M$ for $f < M < N$ are the same as those of $1 \leq M < N - f < F_{g-1}$ and moreover $H_M \leq F_{g-2}$ . But this means that $H_N \leq F_{g-2}$ and to find its value we can just repeat the same reasoning done for $H_{N-f}$ and obtain their equality. QED

We will proceed by finding all the starting pile sizes for which the second player has a winning strategy - we will call these losing sizes .

It then follows that any player who has to make a move when the pile size is a losing size and who is unable to take all the stones at once is in a losing position - his opponent will have a winning strategy.

We claim that the losing sizes are simply the numbers in the Fibonacci sequence starting from $2$ , i.e. $2, 3, 5, 8, 13, ...$

Firstly, it's clear that $2$ and $3$ are losing sizes .

Now for $m \geq 2$ , let the first $m$ losing sizes be $L_{1}, L_{2}, ... , L_{m}$ , such that they follow the Fibonacci sequence outlined above. Consider a pile of stones with more than $L_{m}$ stones.

A move that leaves $k$ stones in the pile by taking away at most $\lfloor \frac{k - 1}{2} \rfloor$ is a safe move because it does not allow the opponent to remove all remaining $k$ stones.

The strategy of both players will be to leave their opponent with exactly $L_{m}$ stones through a safe move . There is no incentive for either player to make the pile less than $L_{m}$ because if there is a safe move that does so, the player will also have a safe move to reduce the pile to $L_{m}$ which will guarantee a win.

For all starting sizes $k$ where $k - L_{m} \leq \lfloor \frac{L_{m} - 1}{2} \rfloor$ , the first player can simply take $k - L_{m}$ stones, leaving the second player with $L_{m}$ stones, a losing size through a safe move . Hence the first player has winning strategies for these starting sizes.

When $k - L_{m} > \lfloor\frac{L_{m} - 1}{2} \rfloor$ , the first player no longer has a safe move to bring the pile to $L_{m}$ stones. Hence this becomes a smaller version of the original game, with both players aiming to leave the opponent with $L_{m}$ stones through a safe move , i.e. aiming to take the $(k - L_{m})$ th stone. This reduces to a game with a starting size of $k - L_{m}$ , which gives the first player a winning strategy as long as $k - L_{m}$ is not a losing size and there are no other losing sizes between $L_{m}$ and $k$ . It can be checked that since the $L_{i}$ follow the Fibonacci sequence, the mini-game with $k - L_{m}$ stones will end with a safe move if $k \leq L_{m-1} + L_{m}$ (this is as much as we need since we only need to consider $k$ up to the next losing size ).

Letting $L_{i} \leq \lfloor \frac{L_{m} - 1}{2} \rfloor < L_{i+1}$ , it follows that for starting sizes $k$ such that $L_{m} < k < L_{i + 1} + L_{m}$ , the first player has a winning strategy while starting size $L_{i + 1} + L_{m}$ is a losing size . Therefore $L_{m+1} = L_{i + 1} + L_{m}$ .

Since $L_{1}, L_{2}, ... , L_{m}$ follow the Fibonacci sequence from $2$ onward, $L_{m - 2} \leq \lfloor \frac{L_{m} - 1}{2} \rfloor < L_{m - 1}$ , which implies that in fact, $L_{m+1} = L_{m-1} + L_{m}$ .

Therefore the losing sizes between $2$ and $1000$ are $2,$ $3,$ $5,$ $8,$ $13,$ $21,$ $34,$ $55,$ $89,$ $144,$ $233,$ $377,$ $610,$ $987$ and the number of winning moves is $999 - 14 = \boxed{985}.$

Motivation for Fibonacci numbers : While testing for small starting sizes and finding the optimal strategy, I discovered that the losing sizes follow a pattern, namely $L_{m+1} = L_{m-1} + L_{m}$ . The pattern was found after devising the strategy outlined above.

The solution is that if the number of stones remaining is $F_n$ (the $n$ -th Fibonacci number) then the player to move loses if he cannot remove all the stones on this turn. Otherwise the player to move wins. So the number of winning positions is the number of non-Fibonacci numbers in the given range, which is $\boxed{985}$ .

Motivation: To find this solution, we can't use Sprague-Grundy theory directly because that only applies to impartial games , i.e. games where each player has the same options available. However, in this game the player's available options depend on the previous move.

Perhaps it would be possible to consider the current "position" as a tuple of the number of stones remaining, and the number of stones that can be removed; and then find a Grundy score for this position. But I didn't try this approach, as I first tried solving directly without Sprague-Grundy theory, and that worked out.

Instead, I manually solved a small number of positions (up to N=21) and then the pattern was apparent, and I was able to come up with a logical argument as to why the pattern extends indefinitely.

Lemma: If there is a pile of $F_n$ stones, and the first player cannot remove all stones in one go, then the second player is able to remove the last stone. Further, the second player's winning move removes at most $2\lfloor \frac{F_n}{3} \rfloor$ stones.

Proof: I am using strong induction: assume the lemma holds for all values $k \lt n$ , then I will show that it also holds for $k = n$ .

We can write: $F_n = F_{n-1} + F_{n-2}$ .

If the first player removes $F_{n-2}$ stones or more , then the second player can immediately remove all remaining stones and win, because $F_{n-1} \le 2 \cdot F_{n-2}$ .

Otherwise, we can consider the subset of $F_{n-2}$ as a separate game. By the inductive hypothesis, regardless of how the first player opens, the second player can eventually remove the last stone of this sub-game , with the final move taking at most $2\lfloor \frac{F_{n-2}}{3} \rfloor$ stones. This leaves a position with $F_{n-1}$ stones. But since $4\lfloor \frac{F_{n-2}}{3} \rfloor \lt F_{n-1}$ , this new position also loses for the first player, by the inductive hypothesis.

Now we just have to check the boundary conditions. $F_4 = 3$ and $F_5= 5$ will do for this. In $F_4$ , the first player removes $1$ or $2$ stones, and then the second player wins by removing $2$ or $1$ respectively, and both of these cases satisfy the bound in the lemma. In fact this case uses the full size of the bound in the lemma, as $2 = 2\frac{F_4}{3}$ .

In $F_5$ , if the first player removes $2$ or more then the second player removes $3$ , satisfying the bound. Or if the first player removes $1$ then the second player also removes $1$ , leaving $F_4$ , so the second player ultimately wins by removing at most $2$ , satisfying the bound.

Thus we have shown by induction that the lemma holds for all $F_k$ where $k \ge 4$ . We can manually check that it also holds for $F_3 = 2$ .

Note: I used $F_4$ and $F_5$ instead of $F_3$ and $F_4$ as it seemed a bit clearer.

Having proven the lemma, we just have to show that all other positions win. To do this, break down the position as:

$N = F_{n-1} + (F_{n-2} - m)$

where $m \lt F_{n-2}$ . But we know that if the position was $N$ , then all moves lose, including the move of taking $m$ . So this must be a winning position.

I will try to find a recursive sequence that dictates when the first player has a winning strategy.

First we start observing that if N=2 or N=3, the second player has a winning strategy. I will call this a losing position.

Now, for N $\ge$ 3, the strategy the second player wants to use is to put the second player in a losing position. Thus, if N=4 for example, the first player removes one stone and leaves the second player in the N=3 position, which we already know it is a losing position. This only works, of course, because the second player cannot take all the 3 stones. In order for this to happen, it is necessary and sufficient to take always strictly less than 1/3 of the stones. Let's call this the 1/3 rule.

This strategy doesn't work for N=5, because in order for the first player to pass a losing position, it has to take 2 stones. But it can't do it directly, as 2 is above the 1/3 threshold, nor indirectly, because we know 2 is a losing position. In fact, for N=5, the second player has a winning strategy, as it can always put the first player in the losing position with 3 stones.

So the first player wants to put the second player in a losing position. It cannot be done if the difference between N and the last losing position is also a losing position. This hints the Fibonacci Sequence, i.e. the sum of 2 consecutive losing positions is also a losing position. I haven't proved this yet, as I ignored the 1/3 rule. So let's establish this hypothesis: The losing positions are those where N is a Fibonacci Number. Proof by induction:

Let F(i) be the i $^{th}$ Fibonacci Number. N=2 and N=3 are losing positions as already established. Suppose that the losing positions less than N are the Fibonacci Numbers less than N. Let m the greatest i such that F(i) $\le$ N.

Let's prove for N+1. If N+1 is a Fibonacci Number, then N+1=F(m+1)=F(m)+F(m-1). The first player doesn't have a winning strategy if it takes less than F(m-1) stones, as F(m-1) is a losing strategy by induction. If the first player takes F(m-1) or more stones, than the second player can take it all at once, since F(m-1) $\ge \frac{1}{3}$ F(m+1), which can be easily proved:

F(m)=F(m-2)+F(m-1) $\Rightarrow$ F(m) $\ge$ 2 F(m-1);

F(m+1)=F(m)+F(m-1) $\Rightarrow$ F(m+1) $\le$ 3 F(m-1) $\Rightarrow$ F(m-1) $\ge \frac{1}{3}$ F(m+1).

Therefore N+1 is a losing position. Suppose now that N+1 is not a Fibonacci Number. Then the first player have a winning strategy by giving the second player F(m) stones as follows: If N+1-F(m) is not a Fibonacci Number then the first player can take this difference according to induction hypothesis. If N+1-F(m) is a Fibonacci Number then it must be at most F(m-2), since F(m-1)+F(m) is a Fibonacci Number, while N+1 is not. So the first player can take it all at once leaving the second player with F(m), since F(m-2) $\le \frac{1}{2}$ F(m), which can be easily proved:

F(m)=F(m-2)+F(m-1) $\Rightarrow$ F(m) $\ge$ 2 F(m-2) $\Rightarrow$ F(m-2) $\le \frac{1}{2}$ F(m).

This completes the induction.

So now we know when the first player has a winning position: for every N that is not a Fibonacci Number. Since 1 is also a Fibonacci Number, it suffices to count how many Fibonacci Number are there less than 1000. They are 1,2,3,5,8,13,21,34,55,89,144,233,377,610,987_ that is 15 numbers, making the answer to the problem 985.

This game is called the Fibonacci NIM, because it is a NIM variant and Fibonacci numbers are closely related to its solution. A position during the game is characterized by two values: the maximum number of stones we may take in the next move $q$ and the current number of stones $s$ . To check whether $(q,s)$ is a winning position, one needs to write $s$ in the Fibonacci base . Let $F_k$ be the smallest Fibonacci number used in the representation of $s$ . The position $(q,s)$ is winning if and only if $F_k \leq q$ . In words, a position is winning if we can remove at least $F_k$ stones from the pile in our next move. Furthermore, in each winning position removing exactly $F_k$ stones is a winning move.

The initial positions are the positions $(n-1,n)$ for $2\leq n\leq 1000$ . Such a position is losing if and only if $n$ is a Fibonacci number. Thus the answer is 999 minus the count of Fibonacci numbers in $[2,1000]$ = 999 - 14 = 985.