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 acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.