0
$\begingroup$

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.

$\endgroup$
2
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ Which is the same as the answer below, since the $a_i\equiv 1\pmod 4$ contribute nothing to your sum, so you are saying that there are an odd number of $a_i\equiv 3\pmod 4$. Your answer is more intuitive, I think. $\endgroup$ – Thomas Andrews Oct 22 '15 at 16:15
0
$\begingroup$

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.

$\endgroup$

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.