stacks with odd number of cards

Question

Given $n$ stacks of cards, stack $i$ contains $a_i$ cards ($1\le i\le n$) such that each $a_i$ is odd. Two players $A$ and $B$ play a game. Players alternate turns. In a move, a player takes an arbitrary stack and splits it into $3$ new non-empty stacks, such that each of the new stacks still contain odd number of cards. The player who cannot make a move loses. If $A$ goes first, is there any condition on the $a_i$'s to determine who has a winning strategy? It is assumed that both players play optimally.

Thanks for any help.

Answer 1

Each $a_i$ takes exactly $\frac {a_i-1} 2$ moves to get down to all ones - easily shown by induction. $A$ wins iff the total number of moves in the game is odd $\Leftrightarrow \sum_{i=1}^n(a_i-1)=2 \mod 4$

Answer 2

Answer

A game is lost if and only if $$a_1 \cdot a_2 \cdot \ldots \cdot a_n \equiv 1 \pmod 4.$$

Reason

For a position $a = (a_1,\ldots,a_n)$, let $v(a) = a_1 \cdot a_2 \cdot \ldots \cdot a_n$. Since all $a_i$ are odd, $v(a)$ is odd, too. This means $v(a) \equiv \pm 1\pmod 4$.

Now check that:

1. The immediate losing positions have the form $a = (1,1,\ldots,1)$ and therefore $v(a) \equiv 1\pmod 4$.

2. For any legal position $a$ and any legal move, the value of $v(a)$ is negated.

For 2.: If $w = x+y+z$ where all numbers are odd, up to the order of the summands there are only the following possibilities mod $4$: $$ 1 \equiv 1 + 1 + (-1),\\ 1 \equiv (-1) + (-1) + (-1),\\ -1 \equiv 1 + 1 + 1,\\ -1 \equiv 1 + (-1) + (-1) $$

Surprisingly, he above argumentation implies that every legal move is optimal! If a position is won, there is no way to deliberately let the other player win.