# Complexity of deciding whether there is a winning strategy in the following game

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 ?
• If you drop the tie condition, I think this is a candidate for the Sprague-Grundy theorem. Feb 21, 2013 at 14:42
• 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, 2013 at 18:55
• 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 ;)
– Dan
Feb 23, 2013 at 15:12
• @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$. Feb 23, 2013 at 21:15
• 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, 2013 at 12:07

1. Is there an n>2, for which A has no winning strategy? To determine if there is an n>2 for which A has no winning strategy, we can analyze the rules of the game. Player A's goal is to select a number mi such that mi divides the sum of all previous numbers mk (where k < i). This means that Player A wants to select a number that results in a sum divisible by mi.

If we consider the case where n is a prime number, A will always have a winning strategy. This is because any prime number can only be divided by 1 and itself, and since A cannot choose the number 1, B will have no valid option to choose from in subsequent rounds. Therefore, A will always be able to choose a number mi such that the sum is divisible by mi.

However, if n is a composite number (not prime), there may be cases where A does not have a winning strategy. Let's consider an example: n = 4. A starts by choosing m1 = 4. Then B can choose m2 = 2, as 4 is divisible by 2. The game ends there, as M1 = ∅. B wins. Therefore, for values of n that are composites, it's possible for A to have no winning strategy.

1. 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, and A chooses no prime numbers? This problem can be approached by creating an algorithm that explores all possible game paths up to k steps, checking if there exists a winning strategy for A. This would involve generating all possible combinations of numbers, selecting valid dividers, and recursively checking the next steps until either A or B wins or the maximum number of steps is reached. The complexity of this algorithm would depend on the values of n and k. As n increases, the number of possible combinations grows exponentially, increasing the computation time. Additionally, as k increases, the number of steps to be explored grows, further increasing the time complexity. Therefore, the decision problem of whether there is a winning strategy for A in at most k steps can be considered difficult and may have high computational complexity, especially for large values of n and k.

However, if the given value of n is relatively small, it may be feasible to employ dynamic programming techniques and memoization to optimize the search for winning strategies. By storing intermediate results and avoiding redundant calculations, the overall computation time could be significantly reduced.

In summary, determining whether A has a winning strategy for a given n and maximum number of steps k, where A chooses no prime numbers, can be computationally difficult, especially for larger values of n and k. Employing dynamic programming techniques could potentially optimize the search process for smaller values of n.

• According to Vor in this comment and this comment, for $3 ≤ n ≤ 75$ player A always has a winning strategy (most often by picking $2$ as its first move), and this is conjectured to go beyond $n = 75$, invalidating your $n = 4$ example. Jan 19 at 14:24
• In answering popular unanswered questions, make sure you don't miss any detail and scrutinize its correctness, as the question is likely left unanswered because experts don't see a way to answer it. It might be easier to answer other questions. Thank you. Jan 19 at 14:31