18

A game in which the players alternately name positive integers that are not sums of previously named integers (with repetitions being allowed). The person who names 1 (so ending the game) is the loser.

The question is: If player 1 names ‘16’, and both players play optimally thereafter, then who wins?

It has been known that if player 1 name "5n," then player 1 wins. If player name "5n+2", the result is known(maybe palyer 2 wins, but I haven't found the source yet). 16 is the minimum number of "5n+1".

I guess that this problem is PSPACE-hard, but I haven't proved it yet.

  • 13
    Apparently it's open whether Sylver Coinage is decidable. Cool. And at least as of 2002, even Conway didn't know who wins from 16. – Jeffε Apr 14 '14 at 12:31
  • 1
    Is it even efficient (i.e P time) to check if someone has lost ? Seems like the "you lost" test is an unbounded knapsack problem. – Suresh Venkat Apr 14 '14 at 19:10
  • I am considering using the construction of sum-free set, for example, the set of odd numbers is a sum-free subset of the integers, and the set ${N/2+1, ..., N}$ forms a large sum-free subset of the set ${1,...,N}$ ($N$ even). Fermat's Last Theorem is the statement that the set of all nonzero nth powers is a sum-free subset of the integers for $n > 2$.However, some basic problems of sum-free set are still unknown. How many sum-free subsets of ${1, ..., N}$ are there, for an integer $N$? Ben Green has shown that the answer is $O(2^{N/2})$. Can this help? –  May 10 '15 at 00:30
  • @SureshVenkat It is efficient. For example, if the current coins are $4$, $5$, and $7$, you effectively have a regex of (aaaa)*(aaaaa)*(aaaaaaa)*, which can be matched against efficiently. – Christopher King Nov 19 '15 at 13:00
  • @PyRulez just writing down that regex is exponential time. However, there's an easy polynomial time test for whether you have to name 1 as your next move (and lose): it's true iff both 2 and 3 have already been named (and 1 hasn't). For if they have, then no higher numbers are available, and if they haven't, then one of those two numbers can be named next. – David Eppstein Mar 21 '16 at 19:08
  • Here's an updated link for Jeffε's comment (as of May 2017). Although I read Conway's comment as suggesting the problem is decidable: "Is there an algorithm for Sylver Coinage that tells you, by looking over all (possibly infinite) options, what the status of the a position is and what if any are the winning moves? The answer is yes (see Winning Ways) but I do not know what the algorithm is." – Neal Young May 21 '17 at 19:04
  • @NealYoung The algorithm in Winning Ways only gives whether an opening move is winning or not -- in accordance with Conway's comment, it relies on a theorem saying finitely moves of the form 2^a 3^b win, and I imagine (Conway having told me of that fact before) that this is what he meant when he said that an algorithm exists. If so, he was being unclear; however, this means that Jeffe's original comment was still correct. – Caleb Stanford Jul 08 '17 at 18:06

0 Answers0