Sylver coinage

Last updated

Sylver coinage is a mathematical game for two players, invented by John H. Conway. [1] The two players take turns naming positive integers that are not the sum of nonnegative multiples of previously named integers. The player who names 1 loses. For instance, if player A opens with 2, B can win by naming 3 as A is forced to name 1. [2] Sylver coinage is an example of a game using misère play because the player who is last able to move loses.

Contents

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:

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]

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. [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]

Related Research Articles

<span class="mw-page-title-main">Nim</span> Game of strategy

Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps or piles. On each turn, a player must remove at least one object, and may remove any number of objects provided they all come from the same heap or pile. Depending on the version being played, the goal of the game is either to avoid taking the last object or to take the last object.

<span class="mw-page-title-main">Prime number</span> Number divisible only by 1 or itself

A prime number is a natural number greater than 1 that is not a product of two smaller natural numbers. A natural number greater than 1 that is not prime is called a composite number. For example, 5 is prime because the only ways of writing it as a product, 1 × 5 or 5 × 1, involve 5 itself. However, 4 is composite because it is a product (2 × 2) in which both numbers are smaller than 4. Primes are central in number theory because of the fundamental theorem of arithmetic: every natural number greater than 1 is either a prime itself or can be factorized as a product of primes that is unique up to their order.

In mathematics, for given real numbers a and b, the logarithm logb a is a number x such that bx = a. Analogously, in any group G, powers bk can be defined for all integers k, and the discrete logarithm logb a is an integer k such that bk = a. In number theory, the more commonly used term is index: we can write x = indra (mod m) (read "the index of a to the base r modulo m") for r x ≡ a (mod m) if r is a primitive root of m and gcd(a,m) = 1.

Misère, misere, bettel, betl, beddl or bettler is a bid in various card games, and the player who bids misère undertakes to win no tricks or as few as possible, usually at no trump, in the round to be played. This does not allow sufficient variety to constitute a game in its own right, but it is the basis of such trick-avoidance games as Hearts, and provides an optional contract for most games involving an auction. The term or category may also be used for some card game of its own with the same aim, like Black Peter.

<span class="mw-page-title-main">Combinatorial game theory</span> Branch of game theory about two-player sequential games with perfect information

Combinatorial game theory is a branch of mathematics and theoretical computer science that typically studies sequential games with perfect information. Study has been largely confined to two-player games that have a position that the players take turns changing in defined ways or moves to achieve a defined winning condition. Combinatorial game theory has not traditionally studied games of chance or those that use imperfect or incomplete information, favoring games that offer perfect information in which the state of the game and the set of available moves is always known by both players. However, as mathematical techniques advance, the types of game that can be mathematically analyzed expands, thus the boundaries of the field are ever changing. Scholars will generally define what they mean by a "game" at the beginning of a paper, and these definitions often vary as they are specific to the game being analyzed and are not meant to represent the entire scope of the field.

In mathematics, Dickson's lemma states that every set of -tuples of natural numbers has finitely many minimal elements. This simple fact from combinatorics has become attributed to the American algebraist L. E. Dickson, who used it to prove a result in number theory about perfect numbers. However, the lemma was certainly known earlier, for example to Paul Gordan in his research on invariant theory.

In combinatorial game theory, the strategy-stealing argument is a general argument that shows, for many two-player games, that the second player cannot have a guaranteed winning strategy. The strategy-stealing argument applies to any symmetric game in which an extra move can never be a disadvantage. A key property of a strategy-stealing argument is that it proves that the first player can win the game without actually constructing such a strategy. So, although it might prove the existence of a winning strategy, the proof gives no information about what that strategy is.

<span class="mw-page-title-main">Richard K. Guy</span> British mathematician (1916–2020)

Richard Kenneth Guy was a British mathematician. He was a professor in the Department of Mathematics at the University of Calgary. He is known for his work in number theory, geometry, recreational mathematics, combinatorics, and graph theory. He is best known for co-authorship of Winning Ways for your Mathematical Plays and authorship of Unsolved Problems in Number Theory. He published more than 300 scholarly articles. Guy proposed the partially tongue-in-cheek "strong law of small numbers", which says there are not enough small integers available for the many tasks assigned to them – thus explaining many coincidences and patterns found among numerous cultures. For this paper he received the MAA Lester R. Ford Award.

<span class="mw-page-title-main">Angel problem</span>

The angel problem is a question in combinatorial game theory proposed by John Horton Conway. The game is commonly referred to as the angels and devils game. The game is played by two players called the angel and the devil. It is played on an infinite chessboard. The angel has a power k, specified before the game starts. The board starts empty with the angel in one square. On each turn, the angel jumps to a different empty square which could be reached by at most k moves of a chess king, i.e. the distance from the starting square is at most k in the infinity norm. The devil, on its turn, may add a block on any single square not containing the angel. The angel may leap over blocked squares, but cannot land on them. The devil wins if the angel is unable to move. The angel wins by surviving indefinitely.

<span class="mw-page-title-main">Chomp</span> Abstract strategy game

Chomp is a two-player strategy game played on a rectangular grid made up of smaller square cells, which can be thought of as the blocks of a chocolate bar. The players take it in turns to choose one block and "eat it", together with those that are below it and to its right. The top left block is "poisoned" and the player who eats this loses.

In mathematics, Euclid numbers are integers of the form En = pn # + 1, where pn # is the nth primorial, i.e. the product of the first n prime numbers. They are named after the ancient Greek mathematician Euclid, in connection with Euclid's theorem that there are infinitely many prime numbers.

Determinacy is a subfield of set theory, a branch of mathematics, that examines the conditions under which one or the other player of a game has a winning strategy, and the consequences of the existence of such strategies. Alternatively and similarly, "determinacy" is the property of a game whereby such a strategy exists. Determinacy was introduced by Gale and Stewart in 1950, under the name "determinateness".

<span class="mw-page-title-main">Grundy's game</span> Mathematical game

Grundy's game is a two-player mathematical game of strategy. The starting configuration is a single heap of objects, and the two players take turn splitting a single heap into two heaps of different sizes. The game ends when only heaps of size two and smaller remain, none of which can be split unequally. The game is usually played as a normal play game, which means that the last person who can make an allowed move wins.

In mathematics, a Størmer number or arc-cotangent irreducible number is a positive integer for which the greatest prime factor of is greater than or equal to . They are named after Carl Størmer.

The vast majority of positive results about computational problems are constructive proofs, i.e., a computational problem is proved to be solvable by showing an algorithm that solves it; a computational problem is shown to be in P (complexity) by showing an algorithm that solves it in time that is polynomial in the size of the input; etc.

<span class="mw-page-title-main">Conway's 99-graph problem</span>

In graph theory, Conway's 99-graph problem is an unsolved problem asking whether there exists an undirected graph with 99 vertices, in which each two adjacent vertices have exactly one common neighbor, and in which each two non-adjacent vertices have exactly two common neighbors. Equivalently, every edge should be part of a unique triangle and every non-adjacent pair should be one of the two diagonals of a unique 4-cycle. John Horton Conway offered a $1000 prize for its solution.

<span class="mw-page-title-main">Danzer set</span> Set of points touching all convex bodies of unit volume

In geometry, a Danzer set is a set of points that touches every convex body of unit volume. Ludwig Danzer asked whether it is possible for such a set to have bounded density. Several variations of this problem remain unsolved.

In combinatorial game theory, a subtraction game is an abstract strategy game whose state can be represented by a natural number or vector of numbers and in which the allowed moves reduce these numbers. Often, the moves of the game allow any number to be reduced by subtracting a value from a specified subtraction set, and different subtraction games vary in their subtraction sets. These games also vary in whether the last player to move wins or loses. Another winning convention that has also been used is that a player who moves to a position with all numbers zero wins, but that any other position with no moves possible is a draw.

References

  1. ↑ 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.
  2. 1 2 3 4 5 6 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.
  3. 1 2 Sicherman, George (2002). "Theory and Practice of Sylver Coinage" (PDF). Integers. 2. G2.
  4. ↑ Sylvester, James J. (1884). "Question 7382". Mathematical Questions. Educational Times. 41: 21.
  5. 1 2 3 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.
  6. ↑ Conway, John H. (2017). "Five $1,000 Problems (Update 2017)" (PDF). On-Line Encyclopedia of Integer Sequences . Retrieved 2019-02-12.

Further reading

This page is based on this Wikipedia article
Text is available under the CC BY-SA 4.0 license; additional terms may apply.
Images, videos and audio are available under their respective licenses.