6
$\begingroup$

Sylver's coinage is an example of an unbounded finite (if slightly modified) combinatorial impartial game. Quoth wikipedia:

The two players take turns naming positive integers that are not the sum of nonnegative multiples of previously named integers. After 1 is named, all positive integers can be expressed in this way: 1 = 1, 2 = 1 + 1, 3 = 1 + 1 + 1, etc., ending the game. The player who named 1 loses.*

This can be made to have the normal play convention if we make $1$ an illegal move.

In Conway's ONAG, it is shown that Grundy's number can be generalized to ordinal numbers for unbounded impartial games.

Is anything known about Grundy's ordinal for Sylver's Coinage and its various positions?

*Wikipedia contributors. "Sylver coinage." Wikipedia, The Free Encyclopedia. Wikipedia, The Free Encyclopedia, 21 Oct. 2014. Web. 27 Mar. 2015.

Improve this question
$\endgroup$
2
  • 2
    $\begingroup$ I seem to remember this cropping up in one of the Games Of No Chance collections, but I'll have to dig around for it a bit. AFAIK the value of the initial position is unknown and no position is known to have value $\geq \omega+\omega$ (there are positions known to have value $\omega$ and I believe there are some with value $\omega+n$ for various $n$), but don't hold me to either of those. $\endgroup$
    – Steven Stadnicki
    Commented Mar 27, 2015 at 2:11
  • $\begingroup$ It's my impression that explicitly finding the ordinals even for finite positions of Sylver Coinage is a very difficult question; even an explicit (impractical) recipe to decide whether an infinite position has ordinal value 0 would be a major advance in our knowledge. $\endgroup$
    – Gabriel C. Drummond-Cole
    Commented Mar 27, 2015 at 2:13

1 Answer 1

Reset to default
3
$\begingroup$

One thing we do know about the Grundy number of a position is that it is less than or equal to the ordinal representing the maximum length of the game starting from that position; to be precise, define $\ell(p)$ to be 0 if the position $p$ is an ending position, and

$$ \ell(p) = \sup_{q \in p}\{\ell(q)+1 \} $$

otherwise. (by $q \in p$ I mean that from position $p$ the acting player can move to position $q$) Then the Grundy number $G(p) \le \ell(p)$.

For Sylver Coinage, $\ell(p)$ is rather easy to determine. $\ell$ of the starting position is $\omega^2$; for any other position, the players will have selected some nonzero finite set of positive integers. Let $d$ be the GCD of all the numbers in the set, and let $m$ be the number of (not necessarily distinct) primes dividing $d$. Let $n$ be the number of possible next moves that are divisible by $d$. Then $\ell(p) = \omega m + n$. The Grundy number must be less than or equal to this ordinal.

Improve this answer
$\endgroup$
2
  • $\begingroup$ The condition for 0 is unnecessary as sup{}=0. $\endgroup$
    – Christopher King
    Commented Apr 1, 2015 at 10:25
  • 1
    $\begingroup$ I prefer to keep it for clarity. $\endgroup$
    – Deedlit
    Commented Apr 3, 2015 at 4:50

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .