Sylver coinage
Sylver coinage is a mathematical game for two players, invented by John H. Conway.[1] The two players take turns naming positive integers greater than 1 that are not the sum of nonnegative multiples of previously named integers. The player who cannot name such a number loses. For instance, if player A opens with 2, B can win by naming 3.[2]
Sylver coinage is named after James Joseph Sylvester,[2][3] 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.[4] 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.[2] 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.[5]
Example
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. (Example: 27 = 4·3 + 5·3)
- A names 11. Now the only remaining numbers are 2, 3, 6, and 7.
- B names 6. Now the only remaining numbers are 2, 3, and 7.
- A names 7. Now the only remaining numbers are 2, and 3.
- B names 2. Now the only remaining number is 3.
- A names 3, leaving nothing for B, and wins.
Each of A's moves was to a winning position.
Analysis
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.[2][5]
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.[2][3]
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.[2][5] In 2017, Conway (2017) offered a $1000 prize for determining who wins in the first unsolved case, the opening move 16, as part of a set of prize problems also including Conway's 99-graph problem, the minimum spacing of Danzer sets, and the thrackle conjecture.[6]
References
- ^ Guy, Richard K. (1976). "Twenty questions concerning Conway's Sylver Coinage". Research Problems. American Mathematical Monthly. 83 (8): 634–637. doi:10.2307/2319892. JSTOR 2319892. MR 1538138.
- ^ a b c d e f Berlekamp, Elwyn R.; Conway, John H.; Guy, Richard K. (1982). "18. The Emperor and His Money" (PDF). Winning Ways for your Mathematical Plays, Vol. II: Games in Particular. Academic Press. pp. 575–606.
- ^ a b Sicherman, George (2002). "Theory and Practice of Sylver Coinage" (PDF). Integers. 2. G2.
- ^ Sylvester, James J. (1884). "Question 7382". Mathematical Questions. Educational Times. 41: 21.
- ^ a b c Guy, Richard K. (2004). "C7. The money-changing problem". Unsolved problems in number theory (3rd ed.). Springer-Verlag. pp. 171–174. ISBN 978-0-387-20860-2. Zbl 1058.11001.
- ^ Conway, John H. (2017). "Five $1,000 Problems (Update 2017)" (PDF). On-Line Encyclopedia of Integer Sequences. Retrieved 2019-02-12.
Further reading
- Michael, T. S. (2009). "6. From Stamps to Sylver Coins". How to Guard an Art Gallery and Other Discrete Mathematical Adventures. JHU Press. pp. 169–206. ISBN 9780801897047.