# Complexity of deciding whether there is a winning strategy in the following game

The sum divider game for $n$ starts with the set $M_0 = \{1,\dots,n\}$. Player A chooses a number $m_1$ from $M_0 \setminus \{1\}$ and B has to choose a divider $m_2$ of $m_1$ from $M_1 = M_0 \setminus \{m_1\}$. The players continue to choose a number $m_i$ from $M_{i-1} = M_{i-2} \setminus \{m_{i-1}\}$ alternatingly, where every $m_i$ has to divide $\sum_{k=1}^{i-1} m_k$. A player wins, if the other player is unable to do so and $M_{i-1} \neq \emptyset$, $M_{i-1} = \emptyset$ is considered a tie.

My questions:

• Is there an $n > 2$, for which A has no winning strategy?
• Given some $n$ (in binary unary representation), how hard is it to decide whether there is a winning strategy for A
• where A wins in at most $k$ steps ?
• where A chooses no prime numbers ?
-
How did you come up with this game? –  Yuval Filmus Feb 21 '13 at 14:27
Perhaps I don't understand the definition, but what stops player $A$ from always choosing 2? –  Shaull Feb 21 '13 at 14:35
@Shaull Once a number is selected, it is removed from the set, and added to the running total of selected numbers. In the next move, the other player has to select a number which divides this running total. –  Paresh Feb 21 '13 at 14:40
If you drop the tie condition, I think this is a candidate for the Sprague-Grundy theorem. –  Paresh Feb 21 '13 at 14:42
I quickly ran a program to check the winning positions of the game and in the range $1..59$ the only wins for B are $n=1$ and $n=2$ (in most of the games but not all games, player A can win picking number 2 as the first move) –  Vor Feb 21 '13 at 18:55