Take the 2-minute tour ×
Computer Science Stack Exchange is a question and answer site for students, researchers and practitioners of computer science. It's 100% free, no registration required.

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 ?
share|improve this question
2  
How did you come up with this game? –  Yuval Filmus Feb 21 '13 at 14:27
1  
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
4  
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
show 13 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.