Pebble Game

Define a game value $g(x)$ for a pile of size $x$ as follows.

• If $x\bmod6$ is $1$ or $2$, then $g(x)=0$.
• Otherwise, let $t=\lfloor(x-3)/6\rfloor$. Count the consecutive nonzero digits at the end of the base-three representation of $t$, stopping at the first zero digit. If the count is $c$, then $g(x)=c+1$. In particular, gives .

The answer is Second if $g(A_1)\oplus\cdots\oplus g(A_N)=0$, and otherwise.

The current player chooses a partition into three positive parts, while the opponent chooses which part survives. The current player can force a pile's game value to become $h$ exactly when a partition exists in which all three parts have value $h$. Hence define

$$S(x)=\{h\mid a+b+c=x,\ a,b,c\ge1,\ g(a)=g(b)=g(c)=h\}.$$

The stated formula satisfies $g(x)=\operatorname{mex}S(x)$: if $g(x)=k$, then every value $h<k$ can be forced, but itself cannot. To see this, write with . When all three parts have positive game value , write them as with . Their indices must satisfy or . If the last ternary digits of are nonzero and the next digit is zero, neither target can be represented by three indices of the same type. For any smaller , a representation can be constructed digit by digit. The case follows by using three parts congruent to or modulo . If , no three value-zero parts can sum to .

Now let $X$ be the XOR of the values of all piles. If $X\ne0$, choose a pile whose value contains the highest set bit of $X$. The other piles' XOR is smaller than this pile's value and can be forced using a suitable three-way split. Thus the opponent must move to a position with XOR zero. If $X=0$, no split can make all three choices retain the old value, so the opponent can always choose a pile that leaves a nonzero XOR. Therefore, the XOR rule determines the winner.

The time complexity is $O(\sum N\log_3\max A_i)$, and the auxiliary space complexity is $O(1)$.