0
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ You only need to figure out the nimber of an $n$-coin pile for each $n$, which is the minimal excluded nimber of its subgames. Do this for the first several $n$ and try to find a pattern. See Sprague-Grundy theorem. $\endgroup$ – WhatsUp Oct 21 '20 at 14:47
  • $\begingroup$ I read that page, and came to know much things. But could you provide a solution or a working procedure, at least? (Btw were my efforts legit?) $\endgroup$ – ultralegend5385 Oct 22 '20 at 2:25
2
$\begingroup$

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$.

$\endgroup$
10
  • $\begingroup$ Sorry, but I don't understand how to use nim-values here? $\endgroup$ – ultralegend5385 Oct 22 '20 at 2:35
  • 1
    $\begingroup$ I added examples. $\endgroup$ – WhatsUp Oct 22 '20 at 3:29
  • $\begingroup$ Oh, so I understand that the sum of all $n(P)$'s is equivalent to the nim-sum of the size of piles, which if zero, makes Alice lose, else he wins. By the way, is there a proof for this? I studied the proof of normal Nim strategy, but couldn't understand it. $\endgroup$ – ultralegend5385 Oct 22 '20 at 3:33
  • $\begingroup$ And is there a way for obtaining Nim value? Or we have to always look at the OEIS sequence? $\endgroup$ – ultralegend5385 Oct 22 '20 at 3:34
  • 1
    $\begingroup$ I believe the proof is somewhere in the above wiki page on Sprague-Grundy theorem. It is not hard to calculate the nimbers: have a look at this and you'll see that they are calculated recursively using the mex on the nimbers of the subgames. See also this pdf which explains things in detail, and has some more interesting games for you to solve. $\endgroup$ – WhatsUp Oct 22 '20 at 3:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.