# 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 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 ?
• 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
• This game seems to me to be (more or less) a simple reachability game on a graph with $2^n$ nodes. One can solve such games in time linear in the number of edges, i.e., in time $\mathcal O((2^n)^2)$. I always struggle with complexity classes, thus I cannot help you further ;) – Dan Feb 23 '13 at 15:12
• @Dan Yes that's probably correct, $2^n$ vertices (i.e. the power set of $\{1,\dots,n\}$) are enough since we don't need the order of the previous elements. This corresponds to the class $E$. – frafl Feb 23 '13 at 21:15
• I'm currently running the program (I hope it doesn't contain an error) to exhaustively check the winning positions. For $3 \leq n \leq 75$ player A has always a winning strategy. So perhaps another good question is "Does exist $n > 2$ for which player B can win the game?" – Vor Feb 24 '13 at 12:07