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 agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.