17
$\begingroup$

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 ?
$\endgroup$
  • $\begingroup$ If you drop the tie condition, I think this is a candidate for the Sprague-Grundy theorem. $\endgroup$ – Paresh Feb 21 '13 at 14:42
  • 5
    $\begingroup$ 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) $\endgroup$ – Vor Feb 21 '13 at 18:55
  • $\begingroup$ 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 ;) $\endgroup$ – Dan Feb 23 '13 at 15:12
  • $\begingroup$ @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$. $\endgroup$ – frafl Feb 23 '13 at 21:15
  • 2
    $\begingroup$ 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?" $\endgroup$ – Vor Feb 24 '13 at 12:07

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.