Subtract a square

Last updated October 23, 2023

Subtract-a-square (also referred to as take-a-square) is a two-player mathematical subtraction game. It is played by two people with a pile of coins (or other tokens) between them. The players take turns removing coins from the pile, always removing a non-zero square number of coins. The game is usually played as a normal play game, which means that the player who removes the last coin wins.^[1]^[2] It is an impartial game, meaning that the set of moves available from any position does not depend on whose turn it is. Solomon W. Golomb credits the invention of this game to Richard A. Epstein.^[3]

Example

A normal play game starting with 13 coins is a win for the first player provided they start with a subtraction of 1:

player 1: 13 - 1*1 = 12

Player 2 now has three choices: subtract 1, 4 or 9. In each of these cases, player 1 can ensure that within a few moves the number 2 gets passed on to player 2:

player 2: 12 - 1*1 = 11        player 2:       12 - 2*2 = 8               player 2: 12 - 3*3 = 3 player 1: 11 - 3*3 =  2        player 1:        8 - 1*1 = 7               player 1:  3 - 1*1 = 2                                player 2:  7 - 1*1 = 6 or: 7 - 2*2 = 3                                   player 1:  6 - 2*2 = 2     3 - 1*1 = 2

Now player 2 has to subtract 1, and player 1 subsequently does the same:

player 2:  2 - 1*1 = 1 player 1:  1 - 1*1 = 0   player 2 loses

Mathematical theory

In the above example, the number '13' represents a winning or 'hot' position, whilst the number '2' represents a losing or 'cold' position. Given an integer list with each integer labeled 'hot' or 'cold', the strategy of the game is simple: try to pass on a 'cold' number to your opponent. This is always possible provided you are being presented a 'hot' number. Which numbers are 'hot' and which numbers are 'cold' can be determined recursively:

the number 0 is 'cold', whilst 1 is 'hot'
if all numbers 1 .. N have been classified as either 'hot' or 'cold', then
- the number N+1 is 'cold' if only 'hot' numbers can be reached by subtracting a positive square
- the number N+1 is 'hot' if at least one 'cold' number can be reached by subtracting a positive square

Using this algorithm, a list of cold numbers is easily derived:

0, 2, 5, 7, 10, 12, 15, 17, 20, 22, 34, 39, 44, … (sequence A030193 in the OEIS )

A faster divide and conquer algorithm can compute the same sequence of numbers, up to any threshold $n$ , in time $O(n\log ^{2}n)$ .^[4]

There are infinitely many cold numbers. More strongly, the number of cold numbers up to some threshold $n$ must be at least proportional to the square root of $n$ , for otherwise there would not be enough of them to provide winning moves from all the hot numbers.^[3] Cold numbers tend to end in 0, 2, 4, 5, 7, or 9. Cold values that end with other digits are quite uncommon.^[3] This holds in particular for cold numbers ending in 6. Out of all the over 180,000 cold numbers less than 40 million, only one ends in a 6: 11,356.^[5]

No two cold numbers can differ by a square, because if they did then a move from the larger of the two to the smaller would be winning, contradicting the assumption that they are both cold. Therefore, by the Furstenberg–Sárközy theorem, the natural density of the cold numbers is zero. That is, for every $\epsilon >0$ , and for all sufficiently large $n$ , the fraction of the numbers up to $n$ that are cold is less than $\epsilon$ . More strongly, for every $n$ there are

O(n/(\log n)^{{\frac {1}{4}}\log \log \log \log n})

cold numbers up to $n$ .^[6] The exact growth rate of the cold numbers remains unknown, but experimentally the number of cold positions up to any given threshold $n$ appears to be roughly $n^{0.7}$ .^[4]

Extensions

The game subtract-a-square can also be played with multiple numbers. At each turn the player to make a move first selects one of the numbers, and then subtracts a square from it. Such a 'sum of normal games' can be analysed using the Sprague–Grundy theorem. This theorem states that each position in the game subtract-a-square may be mapped onto an equivalent nim heap size. Optimal play consists of moving to a collection of numbers such that the nim-sum of their equivalent nim heap sizes is zero, when this is possible. The equivalent nim heap size of a position may be calculated as the minimum excluded value of the equivalent sizes of the positions that can be reached by a single move. For subtract-a-square positions of values 0, 1, 2, ... the equivalent nim heap sizes are

0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 0, 1, 0, 1, 2, 3, 2, 3, 4, … (sequence A014586 in the OEIS ).

In particular, a position of subtract-a-square is cold if and only if its equivalent nim heap size is zero.

It is also possible to play variants of this game using other allowed moves than the square numbers. For instance, Golomb defined an analogous game based on the Moser–de Bruijn sequence, a sequence that grows at a similar asymptotic rate to the squares, for which it is possible to determine more easily the set of cold positions and to define an easily computed optimal move strategy.^[3]

Additional goals may also be added for the players without changing the winning conditions. For example, the winner can be given a "score" based on how many moves it took to win (the goal being to obtain the lowest possible score) and the loser given the goal to force the winner to take as long as possible to reach victory. With this additional pair of goals and an assumption of optimal play by both players, the scores for starting positions 0, 1, 2, ... are

0, 1, 2, 3, 1, 2, 3, 4, 5, 1, 4, 3, 6, 7, 3, 4, 1, 8, 3, 5, 6, 3, 8, 5, 5, 1, 5, 3, 7, … (sequence A338027 in the OEIS ).

Misère game

Subtract-a-square can also be played as a misère game, in which the player to make the last subtraction loses. The recursive algorithm to determine 'hot' and 'cold' numbers for the misère game is the same as that for the normal game, except that for the misère game the number 1 is 'cold' whilst 2 is 'hot'. It follows that the cold numbers for the misère variant are the cold numbers for the normal game shifted by 1:

Misère play 'cold' numbers: 1, 3, 6, 8, 11, 13, 16, 18, 21, 23, 35, 40, 45, ...

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.

In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a one-heap game of nim, or to an infinite generalization of nim. It can therefore be represented as a natural number, the size of the heap in its equivalent game of nim, as an ordinal number in the infinite generalization, or alternatively as a nimber, the value of that one-heap game in an algebraic system whose addition operation combines multiple heaps to form a single equivalent heap in nim.

Golden ratio base is a non-integer positional numeral system that uses the golden ratio as its base. It is sometimes referred to as base-φ, golden mean base, phi-base, or, colloquially, phinary. Any non-negative real number can be represented as a base-φ numeral using only the digits 0 and 1, and avoiding the digit sequence "11" – this is called a standard form. A base-φ numeral that includes the digit sequence "11" can always be rewritten in standard form, using the algebraic properties of the base φ — most notably that φ¹ + φ⁰ = φ². For instance, 11_φ = 100_φ.

<span class="mw-page-title-main">Subtraction</span> One of the four basic arithmetic operations

Subtraction is one of the four arithmetic operations along with addition, multiplication and division. Subtraction is an operation that represents removal of objects from a collection. For example, in the adjacent picture, there are 5 − 2 peaches—meaning 5 peaches with 2 taken away, resulting in a total of 3 peaches. Therefore, the difference of 5 and 2 is 3; that is, 5 − 2 = 3. While primarily associated with natural numbers in arithmetic, subtraction can also represent removing or decreasing physical and abstract quantities using different kinds of objects including negative numbers, fractions, irrational numbers, vectors, decimals, functions, and matrices.

Golomb coding is a lossless data compression method using a family of data compression codes invented by Solomon W. Golomb in the 1960s. Alphabets following a geometric distribution will have a Golomb code as an optimal prefix code, making Golomb coding highly suitable for situations in which the occurrence of small values in the input stream is significantly more likely than large values.

In mathematics, the nimbers, also called Grundy numbers, are introduced in combinatorial game theory, where they are defined as the values of heaps in the game Nim. The nimbers are the ordinal numbers endowed with nimber addition and nimber multiplication, which are distinct from ordinal addition and ordinal multiplication.

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 and computing, the method of complements is a technique to encode a symmetric range of positive and negative integers in a way that they can use the same algorithm for addition throughout the whole range. For a given number of places half of the possible representations of numbers encode the positive numbers, the other half represents their respective additive inverses. The pairs of mutually additive inverse numbers are called complements. Thus subtraction of any number is implemented by adding its complement. Changing the sign of any number is encoded by generating its complement, which can be done by a very simple and efficient algorithm. This method was commonly used in mechanical calculators and is still used in modern computers. The generalized concept of the radix complement is also valuable in number theory, such as in Midy's theorem.

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.

Wythoff's game is a two-player mathematical subtraction game, played with two piles of counters. Players take turns removing counters from one or both piles; when removing counters from both piles, the numbers of counters removed from each pile must be equal. The game ends when one player removes the last counter or counters, thus winning.

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.

Kayles is a simple impartial game in combinatorial game theory, invented by Henry Dudeney in 1908. Given a row of imagined bowling pins, players take turns to knock out either one pin, or two adjacent pins, until all the pins are gone. Using the notation of octal games, Kayles is denoted 0.77.

The octal games are a class of two-player games that involve removing tokens from heaps of tokens. They have been studied in combinatorial game theory as a generalization of Nim, Kayles, and similar games.

Cram is a mathematical game played on a sheet of graph paper. It is the impartial version of Domineering and the only difference in the rules is that players may place their dominoes in either orientation, but it results in a very different game. It has been called by many names, including "plugg" by Geoffrey Mott-Smith, and "dots-and-pairs". Cram was popularized by Martin Gardner in Scientific American.

In the mathematical theory of games, genus theory in impartial games is a theory by which some games played under the misère play convention can be analysed, to predict the outcome class of games.

In combinatorial game theory, and particularly in the theory of impartial games in misère play, an indistinguishability quotient is a commutative monoid that generalizes and localizes the Sprague–Grundy theorem for a specific game's rule set.

In mathematics, a square-difference-free set is a set of natural numbers, no two of which differ by a square number. Hillel Furstenberg and András Sárközy proved in the late 1970s the Furstenberg–Sárközy theorem of additive number theory showing that, in a certain sense, these sets cannot be very large. In the game of subtract a square, the positions where the next player loses form a square-difference-free set. Another square-difference-free set is obtained by doubling the Moser–de Bruijn sequence.

In number theory, the Moser–de Bruijn sequence is an integer sequence named after Leo Moser and Nicolaas Govert de Bruijn, consisting of the sums of distinct powers of 4. Equivalently, they are the numbers whose binary representations are nonzero only in even positions.

Fibonacci nim is a mathematical subtraction game, a variant of the game of nim. Players alternate removing coins from a pile, on each move taking at most twice as many coins as the previous move, and winning by taking the last coin. The Fibonacci numbers feature heavily in its analysis; in particular, the first player can win if and only if the starting number of coins is not a Fibonacci number. A complete strategy is known for best play in games with a single pile of counters, but not for variants of the game with multiple piles.

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

↑ Silverman, David L. (1971), "61. Subtract-a-square", Your Move: Logic, Math and Word Puzzles for Enthusiasts, Dover Publications, p. 143, ISBN 9780486267319
↑ Dunn, Angela (1980), "Subtract-a-square", Mathematical Bafflers, Dover Publications, p. 102, ISBN 9780486239613
1 2 3 4 Golomb, Solomon W. (1966), "A mathematical investigation of games of "take-away"", Journal of Combinatorial Theory , 1 (4): 443–458, doi:10.1016/S0021-9800(66)80016-9, MR 0209015 .
1 2 Eppstein, David (2018), "Faster evaluation of subtraction games", in Ito, Hiro; Leonardi, Stefano; Pagli, Linda; Prencipe, Giuseppe (eds.), Proc. 9th International Conference on Fun with Algorithms (FUN 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 100, Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 20:1–20:12, doi:10.4230/lipics.fun.2018.20, ISBN 9783959770675, S2CID 4952124
↑ Bush, David (October 12, 1992), "the uniqueness of 11,356", sci.math
↑ Pintz, János; Steiger, W. L.; Szemerédi, Endre (1988), "On sets of natural numbers whose difference set contains no squares", Journal of the London Mathematical Society, Second Series, 37 (2): 219–231, doi:10.1112/jlms/s2-37.2.219, MR 0928519 .

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.

[1] Silverman, David L. (1971), "61. Subtract-a-square", Your Move: Logic, Math and Word Puzzles for Enthusiasts, Dover Publications, p. 143, ISBN 9780486267319

[2] Dunn, Angela (1980), "Subtract-a-square", Mathematical Bafflers, Dover Publications, p. 102, ISBN 9780486239613

[golomb-3] 1 2 3 4 Golomb, Solomon W. (1966), "A mathematical investigation of games of "take-away"", Journal of Combinatorial Theory , 1 (4): 443–458, doi:10.1016/S0021-9800(66)80016-9, MR 0209015 .

[fesg-4] 1 2 Eppstein, David (2018), "Faster evaluation of subtraction games", in Ito, Hiro; Leonardi, Stefano; Pagli, Linda; Prencipe, Giuseppe (eds.), Proc. 9th International Conference on Fun with Algorithms (FUN 2018), Leibniz International Proceedings in Informatics (LIPIcs), vol. 100, Dagstuhl, Germany: Schloss Dagstuhl – Leibniz-Zentrum für Informatik, pp. 20:1–20:12, doi:10.4230/lipics.fun.2018.20, ISBN 9783959770675, S2CID 4952124

[5] Bush, David (October 12, 1992), "the uniqueness of 11,356", sci.math

[6] Pintz, János; Steiger, W. L.; Szemerédi, Endre (1988), "On sets of natural numbers whose difference set contains no squares", Journal of the London Mathematical Society, Second Series, 37 (2): 219–231, doi:10.1112/jlms/s2-37.2.219, MR 0928519 .

[1]

[2]

[3]

[4]

[5]

[6]