More than Nim

Let $S$ be the set of nonnegative integers and $v : S \times S \to \{1,2\}$ be a function from pairs $(m,n)$ to two possible values : $1$ if player $1$ has a winning strategy in a current state where there are $m,n$ stones in pile $1,2$ respectively, and $2$ otherwise.

We can represent the possible set of moves as $v(a,0) = v(0,a) = v(a,a) = 1$ for any $a$ . Now we want to find all $(m,n)$ such that $v(m,n)=2$ .

One can see for $m \leq n$ (case $m \geq n$ will be similar), that $v(m,n) = 1$ if and only if $m = n$ or $m = 0$ or $(m,n)$ can be reduced to some $(p,q)$ after player $1$ makes his move, where $v(p,q) = 2$ . In other words, $v(m,n) = 2$ if and only if $v(p,q) = 1$ for all possible moves of player $1$ .

Now ,let's consider $(p,q)$ such that $v(p,q)=2, p<q$ (if the pair exists). The necessary conditions are :

I. $(p-x,q), x > 0$ , In other words $v(a,q) = 1$ for all $0 \leq a < p$

II. $(p,q-x), x > 0$ , In other words, $v(p,a) = 1$ for all $0 \leq a < q$ .

III. $(p-x,q-x), x > 0$ . Note that there is an invariant on the difference of the number of stones since $q-p = (q-x)-(p-x)$ In other words, if $D = q-p$ , then $v(a,a+D) = 1$ for all $0 \leq b < a$ .

Start with an originally empty set $A$ and $B$ . Claim that we can generate the next $(p,q)$ such that $v(p,q) = 2, p<q$ with the following method : Find the least natural number not in $A$ (let's say $x$ ), and also the least not in $B$ (let's say $y$ ). way.

By the way, 'next' means if the previous pair such that $v = 2$ is $(p',q')$ , then either $p > p'$ or $p = p', q = q'$

The next $(p,q)$ must be $(x,x+y)$ (The reasons are below). Then we add $x$ to $A$ and $y$ to $B$ .

Reasons :

i) The least $p$ must be equal to $x$ . Otherwise $p < x$ and so $p \in A$ . But it means that $v(p,p+d)=2$ for some $d \in B$ . Since any new $q$ must be such that $q-p > d$ for any $d \in B$ , then the state $(p.q)$ can be reduced to $(p,p+d)$ , by taking $q-p-d > 0$ stones from the 2nd pile and so $v(p,q) = 1$ . Hence, $p = x$ .

ii) Given $p$ , the least $q$ must be such that $q-p > d$ for any $d \in B$ (since otherwise $v(p,q)=v(p,p+d) = 1$ for some $d \in B$ as by the definition of the above's method, there is a $p' < p$ such that $v(p',p'+d) = 2$ and we can reduce get from $(p,q) = (p,p+d)$ to $p',p'+d)$ by taking $p-p'>0$ stones from the 1st pile. ). Hence $q-p = y$ .

With the above's method we will get $(1,2),(3,5),(4,7),(6,10),(8,13),(9,15),$ $(11,18),(12,20),(14,23),(16,26),(17,28),(19,31),\cdots$ and their reverses. We stop at $(17,28)$ since the next element $(19,31)$ has its 2nd number bigger than $30$ , We have $11 \times 2 = 22$ pairs of $(p,q)$ such that $v(p,q) = 2$ (losing positions for player $1$ ) where $p,q \leq 30$ .

Hence there are $900-22 = 878$ starting positions where first player have a winning strategy.

First I will present a proof, and then an interesting feature, involving the golden ratio, that you may not have seen or known, and want to try and prove.

Since this game is impartial (i.e. both players have identical abilities), and guaranteed to finish with a victory for one of the players, it is possible to identify each possible position as being either an N-position (advantageous to the next player, i.e. winning for the player to move) or a P-position (advantageous to the previous player). From an N-position, it is possible to make a move that results in a P-position, from a P-position all moves result in an N-position. The question is thus to determine the number of N-positions.

I will use the notation $(a,b)$ , with $a \leq b$ , to refer to game positions. (Note that the two piles are identical with respect to the rules of the game, so the constraint $a \leq b$ is justified.) I will call a position "smaller" than another position, if it preceeds the other in lexicographical order, i.e.

$(a,b) < (c,d) \iff a<b \text{ or (} a=b \text{ and } c<d \text{)}$

The point is that any move will always result in a smaller position. This ordering therefore provides a way to work bottom-up. With all that set up, we can get to work.

First of all, $(0,0)$ is obviously a P-position. Therefore, all positions of the form $(0,n)$ or $(n,n)$ , with $n>0$ , are N-positions, since the player to move can reach the P-position in one go. The smallest position from which it is not possible to reach $(0,0)$ is $(1,2)$ , which we can thus identify as a P-position. Now we find that all positions $(1,n)$ , $(2,n)$ and $(n-1,n)$ with $n>2$ are N-positions, since the player to move can reach $(1,2)$ . The smallest position that does not belong to any of these is $(3,5)$ . Again, it is a P-position. The next one you'll find is $(4,7)$ . The generalization might be obvious by now, but I'll prove it rigorously.

In general, the $n$ -th P-position (starting from $P_0 = (0,0)$ ) is $P_n = (a_n, b_n)$ , where $a_n$ is the smallest integer $x > a_{n-1}$ with $x \neq b_k$ for all $k<n$ , and $b_n = a_n+n$ . To prove this, we need to establish that this conforms to the properties of P-positions and N-positions given above.

First we demonstrate that from any P-position $P_i$ it is impossible to move to another P-position $P_j$ (with $i > j$ ). If it were possible, we would need to have $a_i = a_j$ , $b_i = b_j$ , $a_i = b_j$ , $b_i = a_j$ or $b_i - a_i = b_j - a_j$ . All of these trivially cannot be true based on the definition above (the second for instance follows from $b_i = a_i + i > a_j + i > a_j + j = b_j$ ).

Now to demonstrate that from any N-position $(x,y)$ one can move to a P-position. We can distinguish the following cases ( $k$ is always some integer):

• $x = a_k, y > b_k$ : one can move to $P_k$ by reducing $y$ to $b_k$
• $x = a_k, y < b_k$ : one can move to $P_{y-x}$ by reducing both piles (note that $y-x < k$ )
• $x = b_k$ : one can move to $P_k$ by reducing $y$ to $a_k$ (note that $y \geq x > a_k$ )
• $x \neq a_i, x \neq b_i$ for all $i$ : this is impossible based on the definition of $a_n$ : it is always the smallest "unused" number, so all numbers are "used" eventually.

This concludes the proof.

The algorithm for determining the $P_i$ 's can be easily applied to identify all P-positions (excluding $(0,0)$ ) for piles of at most 30 stones:

$(1,2), (3,5), (4,7), (6,10), (8,13), (9,15), \\ (11,18), (12,20), (14,23), (16,25), (17,28)$

There are thus 11 P-positions. Remember though that we asserted $a \leq b$ , so without this constraint there are 22. The number of N-positions is therefore $900 - 22 = \boxed{878}$

Now for an interesting feature: the $n$ -th P-position is given by

$P_n = (\lfloor n\phi \rfloor, \lfloor n(\phi+1) \rfloor)$ ,

where $\lfloor x \rfloor$ is the floor of $x$ , i.e. the largest integer smaller than or equal to $x$ , and $\phi$ is the golden ratio: $\phi = \frac12(1+\sqrt5) = 1.618\ldots$

Therefore, the general answer to this problem (replacing 30 with $N$ ), is

$\boxed{ N^2 - 2\lfloor \frac{N+1}{\phi+1} \rfloor }$

I happened to have heard of this game before, I don't know its name, but I remember this remarkable feature. I might present a proof later as a comment to this post, but I'll gladly let someone beat me to it.

The complete list of losing positions is: $\begin{aligned} L_1 &= (1, 2) \\ L_2 &= (3, 5) \\ L_3 &= (4, 7) \\ L_4 &= (6, 10) \\ L_5 &= (8, 13) \\ L_6 &= (9, 15) \\ L_7 &= (11, 18) \\ L_8 &= (12, 20) \\ L_9 &= (14, 23) \\ L_{10} &= (16, 26) \\ L_{11} &= (17, 28) \end{aligned}$ plus their reverses $(2, 1)$ , $(5, 3)$ , etc.

Proof: Let $L = \left\{ L_{k}, \text{(and their reverses)} \right\}$ be the set of positions listed above, and $W$ be the other positions. We will show that:

Case 1: If a position is in $L$ then there is no move that leaves another position in $L$

Case 2: If a position is in $W$ then there is always a move that takes all stones, or leaves a position in $L$

This will prove that all positions in $L$ are losing, and all positions in $W$ are winning.

Note - the winning condition "a player is unable to take a stone" can only happen if there are no stones (since taking one stone is a legal move), therefore a player wins if he takes the last remaining stone.

In the cases below we assume without loss of generality that the position $(m, n)$ has $m \leq n$ .

Case 1: No position in $L$ has a pile with the same number of stones as any other position in $L$ , therefore the move "take stones from one pile" cannot leave a position in $L$ .

Further, each position $L_k = (m, m + k)$ . So the move "Remove k stones from each pile" cannot leave a position in $L$ , since the value of $k$ is different for each of these members.

Case 2: (i) : If the position is $(m, m)$ then the move "take $m$ stones from each pile" wins.

(ii) : If the position is $(m, m+k)$ then we have sub-cases:

(a): If there exists $L_q = (m, m+q)$ and $k > q$ then the move "take $k - q$ stones from the second pile" leaves $L_q$ . Or if $q \gt k$ , then the move "remove $m - l$ stones from each pile" leaves $L_k = (l, l + k)$ . This works because the sizes of piles in $L_q$ are greater than those in $L_k$ whenever $q \gt k$ .

(b): If there exists $L_q = (m - q, m)$ then the move "take $k + q$ stones from the second pile" leaves the reverse of $L_q$ . We clearly must have $m+k \gt m-q$ ..

Since all values from $1$ through $18$ appear in a member of $L$ , those two cases are exhaustive for $m \lt 19$ . So we have remaining:

(c): If $m \ge 19$ we must have $k \le 11$ because of the stipulation of $30$ being the maximum pile size. In this case, the move "remove $m - l$ stones from each pile" leaves $L_k = (l, l + k)$ .

Conclusion: there are $22$ losing positions in $L$ : the $11$ listed above, and their reverses. So the number of winning positions is $900 - 22$ = $\boxed{878}$ .

Examples: $(9,12)$ wins by case 2(ii)(a) with $k = 3$ , $q = 6$ ; we remove $5$ stones from each pile to leave $L_3 = (4, 7)$ .

$(9, 22)$ wins by case 2(ii)(a) with $k = 13$ , $q = 6$ ; we remove $7$ stones from the second pile to leave $L_6 = (9, 15)$ .

$(24, 26)$ wins by case 2(ii)(c) , we remove $21$ stones to leave $L_2 = (3, 5)$ .

Within the 900 starting positions, there are 22 of them at which the second player has a winning strategy. (We will also refer this kind of positions as sure-lose positions . The positions such that the first player has a winning strategy are called sure-win positions ). Eleven of these sure-lose positions are:

$(1,2), (3,5), (4,7), (6,10), (8,13), (9,15),$ $(11,18), (12, 20), (14,23), (16,26), (17,28),$

and the other eleven losing positions are just the "reverse" of them, namely, $(2,1), (5,3), \cdots, (28,17)$ .

Since the game does not allow a draw, and it is terminating in a finite number of steps, the total number of sure-win and sure-lose positions is 900, therefore the number of sure-win is 900-22= 878 .

To see how we can get the list of sure-lose positions, one way is to use a tabular (or lattice) representation. Consider the set of coordinates $\{(m,n): m=0, 1, \dots 30; n=0, 1, \dots 30\}$ , and we assign to each pair $(m,n)$ a number $S(m,n)\in \{0,1\}$ , where $S(m,n) = 1$ if and only if it is a sure-win position (therefore $S(m,n)=0$ if it is a sure-lose position).

We observe the following: - $S(0,0)=0$ , since if on a player's turn there is no stone in both piles, the player loses by definition. - If $S(m,n) = 0$ then $S(m,n+x)=S(m+x,n)=S(m+x,n+x)=1$ for all $x>0$ because the first player can remove $x$ stones from either or both of the piles. So now we know that $S(0,x)=S(x,0)=S(x,x)=1$ for all $x>0$ (Draw a picture to see it :-) - $S(m,n)=0$ if and only if $S(m,n-x)=S(m-x,n)=S(m-x,n-x)=1$ for all admissible $x>0$ . This is because a position is sure-lose when all of the possible moves give a sure-win position to its opponent! For example, $S(1,2)=0$ because $S(0,2)=S(1,1)=S(1,0)=S(0,1)=1$ . - Similarly, $S(2,1)=0$ . Then one also knows that $S(2+x,1)=S(2,1+x)=S(2+x,1+x)=1$ for all $x>0$ . Again, please draw a picture in order to help our eyes to see the pattern.

Since there are only 31 rows and 31 columns, it is not hard to continue the observation above even if we don't generalize. Thus we get the 22 sure-lose positions mentioned above.

Some notes:

1. One can simplify the process above by noticing that the difference of the coordinates of the sure-lose positions are $0, 1, 2, 3, \dots$ . For example, the first one is $(0,0)$ with $0-0=0$ , the second (pair) is $(1,2), (2,1)$ , with |2-1|=1. The $n$ -th pair is determined by the following algorithm: take the smallest positive integer $a_n$ that has not been used in the previous pairs, then the new pair is $(a_n+n,a_n), (a_n,a_n+n)$ . For example, $a_2 = 3$ , so the second pair is $(3,5),(5,3)$ . Then $a_3=4$ , so the third pair is $(4,7),(7,4)$ , and so forth.

2. A more efficient algorithm to calculate $a_n$ is the integer part of

$n\cdot \frac{\sqrt{5}+1}{2}$ . (Verify it!)

We work backwards to find all losing positions with $m \le n$ . The key is that if $(x,y)$ is winning iff there exists $k\ge1$ such that one of $(x-k,y-k)$ , $(x,y-k)$ , and $(x-k,y)$ is losing.

For $m = 0$ , $(0,0)$ is losing, so $(0,n)$ is clearly winning for $n \ge 1$ .

For $m=1$ , $(1,1)$ is winning, so $(1,2)$ is losing and $(1,n)$ is winning for $n\ge3$ .

For $m=2$ , $(2,n)$ is winning for all $n\ge2$ , since $(2,1)$ is losing.

In general, it's easy to see that for fixed $m$ , there exists at most one value of $n$ such that $(m,n)$ is losing. Now order the losing pairs as $(m_0,n_0),(m_1,n_1),\ldots$ with $m_i \le n_i$ and $m_0 < m_1 < \cdots$ , starting with $(m_0,n_0) = (0,0)$ . A simple induction on $i$ shows that $(m_i,n_i)$ exists with $n_i - m_i = i$ and $m_i$ the least integer not in the set $\{m_0,n_0,\ldots,m_{i-1},n_{i-1}\}$ . Indeed, $m_i$ cannot lie in the set or else two losing pairs would intersect. On the other hand, if it is the smallest integer not in the set, then $(m_i,m_i),\ldots,(m_i,m_i+i-1)$ must all be winning by the inductive hypothesis, while $(m_i,m_i+i)$ is losing since the differences $i,i+1,i+2,\ldots$ do not belong to any losing pairs with smaller sum of coordinates and $m_i$ is too large to be in a smaller (previous) losing pair by construction.

It follows that $(1,2),(3,5),(4,7),(6,10),(8,13),(9,15),(11,18),(12,20),(14,23),(16,26),(17,28)$ are the $11$ losing pairs with both terms at most $30$ , so the answer is $30^2 - 2\cdot 11 = 878$ .

Denote the position where there are a stones in the first pike and b n the second pile by (a,b). We consider the case a < b, and the case a > b follows analogously. Note that (a,a), (a,0), (0,a) are winning positions for player 1. So this settles the case a = b.

First, we claim that (1,2) is a losing position for P1. Since P1 can only transform it into a winning position for P2, ((1,1),(1,0),(0,1),(0,2)), P1 loses. Then (m,m + 1) is a winning position for P1 where m > 1 since P1 can transform it into (1,2). Now consider (m, m + 2). (1,3), (2,4) are winning positions (can be transformed into (1,2) or (2,1)), and (3,5) isn't, since Move 1 can only transform one of the piles into less than 3 stones, with the other having 5, which is a winning position, or transform it into (m, m + 1), (m,m) , (m+1,m) or the previous case, and with m > 1. So P1 loses, (3, 5) is a losing position.

Continuing similarly, we can find that (4,7), (6,10), (8, 13), (9, 15), (11, 18), (12, 20), (14, 23), (16, 26), (17, 28). So there are a total of 11 losing positions in this case. If a > b, there are 11 losing positions too (namely (2,1), (5,3), etc...). So there are a total of 900 - 22 = $\boxed{878}$ winning positions.

Let us represent a position with $m$ stones in one pile, and $n$ stones in the other pile, with $m\leq n$ as the pair $(m,n)$ .

First of all I will define a sequence of pairs (which will turn out to be the losing positions). We start with $a_{0}=0, b_{0}=0$ and then define recursively:

• $a_{n}$ is the smallest number not in either sequence $(a_{0},a_{1},\dots, a_{n-1}), (b_{0},b_{1},\dots, b_{n-1})$
• $b_{n}=a_{n}+n$

This generates the set of pairs $L$ : $(0,0),(1,2),(3,5),(4,7),(6,10),(8,13)$ $(9,15),(11,18),(12,20),(14,23),(16,26),(17,28),(19,31)\dots$ .

Firstly, it is clear that any move from $L$ takes you out of $L$ . This is because the pairs in $L$ have disjoint elements (since $a_{n}$ and $b_{n}$ are disjoint and monotone increasing) and have different gaps (the sequence of gaps is just $(0, 1,2,3,\dots)$ ).

Secondly, let us show that if we start at a position $(\alpha,\beta)$ not in $L$ with $\alpha\leq \beta$ then you can always find a move into a position in $L$ .

Note that every number will eventually feature in the sequence $L$ . Defining $a_{n}$ as the smallest non-included number ensures there are no gaps. We must then have that $\alpha$ features in either the sequence of $a$ 's or $b$ 's, and we can consider these two cases separately.

• If $\alpha$ is one of the $a$ s, say $\alpha = a_{n}$ then there are two possibilities if $\beta< b_{n}$ then the gap between them, $k$ , is smaller than $n$ and by removing the same amount of stones ( $a_{n}-a_{k}$ ) from each pile we can reduce to $(a_{k},b_{k})$ . If $\beta> b_{n}$ then we can just remove $\beta-b_{n}$ ) stones from the $\beta$ pile to reduce to $((a_{n},b_{n})$ .

• If $\alpha$ is one of the $b$ 's, say $\alpha= b_{n}$ then we can just remove stones from the $\beta$ pile (noting that $a_{n} < b_{n}= \alpha \leq \beta$ ) to get to $(a_{n},b_{n})$ .

We now can define a very simple winning strategy for Player 1 for all starting positions not in $L$ . All he needs to do is move in such a way that after each of his move Player 2 is confronted with a position in $L$ . We have shown both that this is possible on the first move, and since Player 2 cannot return a position in $L$ It will also be possible on subsequent moves. Of course if Player 1 starts with a position of $L$ then he is forced to move out of $L$ , and player 2 can reproduce player 1's winning strategy.

We now know that any position in $L$ loses and all other position win. There are 11 elements of $L$ with piles of size between 1 and 30 or fewer (i.e. $(0,0)$ and $(19,31)$ and onward are outside the range ) each contributing two orders (e.g (1,2) could be $m=1, n=2$ or $m=2, n=1$ . Hence there are 22 losing positions from the 900 starting positions, leaving 878 winning positions.

(1,2) (3,5) (4,7) (6,10) (8,13) (9,15) (11,18) (12,20) (14,23) (16,26) (17,28)

Let (m,n) represent the configuration with m stones in pile 1 and n stones in pile 2. Let (m,n) be a WC (winning configuration) for player x (pX) if pX has a winning strategy for (m,n) Note that when m=n, p1 wins. If (m,n) is a WC for p2, note that for all (m,k), k > n, p1 can win by using his first move to reduce k to n. This is derived from p1's ability to remove stones from the pile with n stones Similarly, for (r,n), r > m, p1 will win. Lastly, for (m+q,n+q), q > 0, player 1 will be able to remove q stones from both piles and win. Note that (1,2) is a WC for p2. By continuing on, we find that (1,2), (3,5), (4,7), (6,10), (8,13), (9,16), (11,19), (12,21), (14,24), (15,26) and (17,29) [and the other order] are the only WC for p2. Hence, WC for p1 = 900 - 2*11 = 878