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.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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|cite|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
5  
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
1  
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

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.