# NIM game variant - one pile, taking square number of objects

There are $n$ objects on the table. Two players take turns. In one move player can take $x^2$ ($x$ is any integer, players can change it) objects. Player who can't do any move loses and the other one wins. How many $n$ are there such that the second player has a winning strategy? I think there are infinitely many $n$, but I have no idea how to prove it.

• What is $x$???? May 13 '17 at 9:36
• $x$ is any integer. May 13 '17 at 9:37
• since taking $1$ is a valid move, do I understand correctlly that who takes the last object wins? May 13 '17 at 9:40
• Yes, the one who takes the last object wins. May 13 '17 at 9:40
• Incidentally, this game is very well known/studied. See en.wikipedia.org/wiki/Subtract_a_square for a lot of information going beyond the scope of this question. May 13 '17 at 10:59

Define "position $k$" as a scenario where there are $k$ objects on the table at a player's turn to move.

Call position $k$ winning if a player with that position has a winning strategy (i.e., a strategy which can guarantee a win, regardless of the moves chosen by the opponent).

If a position is not winning, call it losing.

Let $W$ be the set of all winning positions, and let $L$ be the set of all losing positions.

For example, $1, 3, 4 \in W$ and $0, 2, 5 \in L$.

If the game starts in a losing position, then player $2$ has a winning strategy.

The question being asked is: How many elements does the set $L$ have?

Claim $L$ is infinite.

Suppose otherwise.

Then $L$ has a largest element, $m$, say.

Clearly we must have $m >2$ (since $5 \in L$).

Now consider the position $n = m^2-1$.

Since $n > m$, position $n$ must be winning.

It follows that for some positive integer $k < m^2$, we must have $n - k^2 \in L$.

But $n-k^2$ can't be in $L$, since

$$n - k^2 \ge n - (m-1)^2 = (m^2-1)-(m-1)^2 = 2m - 2 > m$$

Therefore, as claimed, $L$ must be infinite.
• Since $n = m^2 - 1$, the player can't subtract $m^2$. May 13 '17 at 11:17
The game can be completely define recursively. Start at $n=1$, the first player takes that object and wins. At $n=2$, the first player has only one valid move, that is taking $1$ object, leaving the second player in a situation that has already been proven being a winning one. So first player loses. At $n=3$ the first player has at least one move (again, taking $1$ object) that sends the second player in a situation that has ben proven a losing one, so the first player wins. At higher $n$'s you go on checking whether the first player has at least one valid move to send the second player in a situation that has already been proven losing. If he doesn't have such a move, he is forced leaving the second player in a winning position so he loses.
Here is the winning table for $n$ up to $100$ (the rightmost number is one possible winning move for the first player):