Let A be a finite set of Naturals. NIM(A) is the following game: There are n stones on the board. Players I and II alternate removing a\in A stones. The first player who can't win loses. Note that if 1\in A then `can't move' means that the other player took the last stone. If (say) 2 is the min elt of A then its possible there is 1 stone on the board and a player can't move.
The following are known and easy to prove:
- If A={1,L} and L is even then II wins iff n\equiv 0,2,4,...,L-2 mod L+1
- If A={1,L,L+1} and L is odd then II wins iff n\equiv 0,2,4,...L-1 mod 2L+1
- If A={1,L,L+1} and L is even then II wins iff n\equiv o,2,4,...,L-2 mod 2L
- If A= {L,...,M} then II wins iff n\equiv 0,2,4,...,L-2 mod L+1
- For ANY set A there will be a mod pattern, after a certain point.
This raises the following computational problem: How hard is the problem of, given finite set A, find the mod pattern. I would want to know the complexity as a function of the size of the representation of A, or possibly just |A|log_2(max elt of A). Has this been looked at? Some Google searches and asking around did not yield anything. I'm hoping that asking my readers may yield something.
My first idea would be to look at R. Kannan: Lattice translates of a polytope and
ReplyDeletethe Frobenius problem, where he shows that to decide whether the Frobenius number of (a1,..,an) is at most t is NP-hard (but for fixed n it is in P).
Winning Ways calls these games subtraction games (after Ferguson (1974), "On sums of graph games with last player losing") which might help with searching for papers.
ReplyDeleteFor an upper bound on the complexity, Nathan Fox (2014), "On Aperiodic Subtraction Games with Bounded Nim Sequence", gives an algorithm, in appendix B, for computing the period of a subtraction game with a finite subtraction set. Is this the best known algorithm for the problem?
I am almost sure it is PSPACE-complete to decide who wins if the input is A (allowed moves) and N (number of stones).
ReplyDeleteI of course might be wrong, and, knwoing myself, the sketch below is certainly wrong...
A will be such that at every move the player whose turn it is has only two choices.
This can be achieved as follows.
We say that a number is small if it is =i, A will have two NORMAL elements that are of the form (k-1)*k^{i+n}+small.
It will also have for every n>=t>i+1 a PUNISH element, k^{t+n}-(k-1)*k^{i+n}.
Finally, A also has an END element k^n+1.
This guarantees that if the current player plays something other than one of the two NORMAL elements of the form (k-1)*k^{t-1+n}+small, then the other player can pick a PUNISH element and the current player cannot move.
Now we sketch a reduction from 1-in-3 TQBF, where we are given a totally quantified conjunctive normal formula such that in every clause there are 3 literals and the goal is to have exactly one true literal in every clause.
(I haven't proven that this is PSPACE-complete but I guess it should be.)
Suppose we are given an F formula with n variables.
The starting N will equal k^2n+k^{n-1}+..+1.
Here for i=0 to n-1 the k^i will correspond to the i-th clause of the formula, when it disappears, the cluase will be satisfied.
The moves correspond to selecting the values of the variables.
So in the elements of the form (k-1)*k^{t+n}+small, the small will be the sum of the k^i corresponding to the clauses that are satisfied if the t-th variable is true/false.
Eventually, after n steps, we arrive at a number M that is either k^n, or more.
If M=k^n, the formula has been satisfied, otherwise it is not.
Also, at this point the current player wins if and only if he can select the END element k^n+1, which is equivalent to M>k^n.
I think the 1-in-3 TQBF can be replaced by an ordinary TQBF if we add some rounds where the player whose goal is to make the formula satisfied, has some extra turns where he can add k^i -s to the small part of the number, this should not be hard to achieve.
The problem YOU state: given (a1,...,am,n) who wins is prob PSPACE complete and your proof or some version of it is prob right. But this is not what I am asking. I am quite intentionally asking about given (a1,...,am) find the actual mod pattern. This is a function not a set which makes it not quite in the `PSPACE complete' mode.
ReplyDeleteAnother difficulty- what if there are numbers a1,...,am that are small but the mod pattern involves a rather large mod (is this possible?). Then there may even be an issue writing down the answer.
Yes, I agree that this is not the same problem. The only bound I can think of for the mod is 2^am, where am is the largest ai.
DeleteNot sure if my previous comment came through. Let me try again.
ReplyDeleteYour conjecture (I think that if 1\in A then the mod pattern goes from the beginning, but if 1\notin A then its possible that it does not start for a while.) is incorrect. For example, when A = {1, 6, 9} there is a preperiod. Only starting from n = 11 does the corresponding nimsequence become periodic, in this case with period 5. Although the problem is unsolved, even when |A| = 3, I think I know the solution in the case A = {1, a, b}. If anyone is interested, let me know.
Great! Thanks! Conjectures are made to be proved OR disproved.
DeleteYES I would be interested in the {1,a,b} case.
bill g.
Cool! If I'm correct, with S = {1, a, b} we have to consider 12 different cases, depending on, for example, the parities of a and b and the modulus of b (mod (a+1)). For all 12 nimsequences (or rather, their periodic parts), you can check the newest post here: https://bylossofgenerality.wordpress.com, which might be a bit cryptic at first, but shouldn't be too bad.
DeleteVery kind regards,
Wouter van Doorn