21
$\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 ?
Improve this question
$\endgroup$
9
  • $\begingroup$ If you drop the tie condition, I think this is a candidate for the Sprague-Grundy theorem. $\endgroup$
    – Paresh
    Feb 21, 2013 at 14:42
  • 6
    $\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, 2013 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, 2013 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, 2013 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, 2013 at 12:07

0

Reset to default

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.