Alice and Bob are playing a variant of Nim game. There are $n$ piles consisting of $a, b, c,\cdots$ coins respectively. On a move, a player can remove a square number of coins from either pile; e.g. one can remove $1,4,9,\cdots$ coins from either pile in one move. Empty moves are not allowed. The player unable to move loses. Suppose Alice goes first. Determine the condition that Alice wins, as well as devise a winning strategy for him. Assume both players play optimally.
Here are my efforts:
Define a set $G_n$ consisting of all possible partitions of a number $n$ into squares. For example, $$G_6 = \{1+1+1+1+1+1, \ 4+1+1\}$$ Now, note that if the total number of moves (till all piles become zero) is odd, Alice wins; if it is odd, Bob wins.
Now, if there is only one pile, then the pile may approach zero in some order, say $P$, then $P\in G$ by definition of $G$. Let us say the total number of numbers in a path $P$ will be $n(P)$. In a one-pile game, Alice wins if $n(P)$ is odd, else Bob wins.
Similarly, in a $n$-pile game, Alice wins if the sum of the values of $n(P)$ for each pile is odd, else Bob wins.
Now, in a one-pile game, Alice's strategy should be to choose that $P\in G$ that has the largest numbers, because if he chooses smaller numbers, Bob can break his path.
But I'm unable to figure out a strategy for him where $n> 1$. Can anyone help me out?
I computed the nimbers and searched on OEIS.
The result is this sequence and a useful link on that page is this paper that gives a fast algorithm (which is an improvement from the naive $O(n^{3/2})$ to a somewhat $O(n^{1 + \epsilon})$).
The paper is quite recent (from 2018), which probably means that there is no known better way of calculating the nimbers.
Examples:
Let's say we have three piles, of sizes $37, 51, 87$, respectively.
Looking at the OEIS sequence, we find that the corresponding nimbers are $3, 5, 6$, respectively.
We then calculate the xor of the three nimbers, which is $0$.
This means that the original game is equivalent to a pile of $0$ nim, hence Alice loses (as she moves first and there is no legal move).
On the other hand, if the three piles are $37, 51, 83$, then the nimbers are $3, 5, 4$ and the xor of them is $2$. This means that Alice wins.
In general, Alice loses if and only if the xor of all the nimbers is equal to $0$.