Sylver coinage

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search

Sylver coinage is a mathematical game for two players, invented by John H. Conway. It is discussed in chapter 18 of Winning Ways for Your Mathematical Plays. This article summarizes that chapter.

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.

Sylver coinage is named after James Joseph Sylvester, who proved that if a and b are relatively prime positive integers, then (a − 1)(b  − 1) − 1 is the largest number that is not a sum of nonnegative multiples of a and b. Thus, if a and b are the first two moves in a game of sylver coinage, this formula gives the largest number that can still be played. More generally, if the greatest common divisor of the moves played so far is g, then only finitely many multiples of g can remain to be played, and after they are all played then g must decrease on the next move. Therefore, every game of sylver coinage must eventually end. When a sylver coinage game has only a finite number of remaining moves, the largest number that can still be played is called the Frobenius number, and finding this number is called the coin problem.

Example[edit]

A sample game between A and B:

  • A opens with 5. Now neither player can name 5, 10, 15, ....
  • B names 4. Now neither player can name 4, 5, 8, 9, 10, or any number greater than 11.
  • A names 11. Now the only remaining numbers are 1, 2, 3, 6, and 7.
  • B names 6. Now the only remaining numbers are 1, 2, 3, and 7.
  • A names 7. Now the only remaining numbers are 1, 2, and 3.
  • B names 2. Now the only remaining numbers are 1 and 3.
  • A names 3, leaving only 1.
  • B is forced to name 1 and loses.

Each of A's moves was to a winning position.

Analysis[edit]

Unlike many similar mathematical games, sylver coinage has not been completely solved, mainly because many positions have infinitely many possible moves. Furthermore, the main theorem that identifies a class of winning positions, due to R. L. Hutchings, guarantees that such a position has a winning strategy but does not identify the strategy. Hutchings's Theorem states that any of the prime numbers 5, 7, 11, 13, …, wins as a first move, but very little is known about the subsequent winning moves: these are the only winning openings known.

When the greatest common divisor of the moves that have been made so far is 1, the remaining set of numbers that can be played will be a finite set, and can be described mathematically as the set of gaps of a numerical semigroup. Some of these finite positions, including all of the positions after the second player has responded to one of Hutchings' winning moves, allow a special move that Sicherman calls an "ender". An ender is a number that may only be played immediately: playing any other number would rule it out. If an ender exists, it is always the largest number that can still be played. For instance, after the moves (4,5), the largest number that can still be played is 11. Playing 11 cannot rule out any smaller numbers, but playing any of the smaller available numbers (1, 2, 3, 6, or 7) would rule out playing 11, so 11 is an ender. When an ender exists, the next player can win by following a strategy-stealing argument. If one of the non-ender moves can win, the next player takes that winning move. And if none of the non-ender moves wins, then the next player can win by playing the ender and forcing the other player to make one of the other non-winning moves. However, although this argument proves that the next player can win, it does not identify a winning strategy for the player. After playing a prime number that is 5 or larger as a first move, the first player in a game of sylver coinage can always win by following this (non-constructive) ender strategy on their next turn.

Question dropshade.png Unsolved problem in mathematics:
Are there any non-prime winning opening moves in sylver coinage?
(more unsolved problems in mathematics)

If there are any other winning openings, they must be 3-smooth numbers (numbers of the form 2i3j for non-negative integers i and j). For, if any number n that is not of this form and is not prime is played, then the second player can win by choosing a large prime factor of n. The first few 3-smooth numbers, 1, 2, 3, 4, 6, 8, 9, and 12, are all losing openings, for which complete strategies are known by which the second player can win. By Dickson's lemma (applied to the pairs of exponents (i, j) of these numbers), only finitely many 3-smooth numbers can be winning openings, but it is not known whether any of them are.

References[edit]

External links[edit]