Subtract a square

Subtract-a-square (also referred to as take-a-square) is a two-player mathematical game of strategy. 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]

Illustration

A normal play game starting with 13 coins is a win for the first player provided he does 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:

1) the number 0 is 'cold', whilst 1 is 'hot'

2) if all numbers 1 .. N have been classified as either 'hot' or 'cold', then
  2a) the number N+1 is 'cold' if only 'hot' numbers can be reached by subtracting a positive square
  2b) 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)

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

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$ .^[5] The exact growth rate of the cold numbers remains unknown.

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 requires the positions in the game subtract-a-square to be mapped onto equivalent nim heap sizes; the first few values 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).

Optimal play consists of moving to a collection of numbers such that the nim-sum of their values is zero, when this is possible. Notice that all 'cold' positions get mapped onto a zero heap size.

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]

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, ...

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: 443–458, doi:10.1016/S0021-9800(66)80016-9, MR 0209015 .
↑ 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 928519 .

This article is issued from Wikipedia - version of the 12/4/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.