16
$\begingroup$

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.

$\endgroup$
  • 12
    $\begingroup$ 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. $\endgroup$ – Jeffε Apr 14 '14 at 12:31
  • 1
    $\begingroup$ 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. $\endgroup$ – Suresh Venkat Apr 14 '14 at 19:10
  • $\begingroup$ 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? $\endgroup$ – Rupei Xu May 10 '15 at 0:30
  • $\begingroup$ @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. $\endgroup$ – PyRulez Nov 19 '15 at 13:00
  • $\begingroup$ @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. $\endgroup$ – David Eppstein Mar 21 '16 at 19:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.