Subtract-a-square is a two-player mathematical game of strategy starting with a positive integer and both players taking turns subtracting a non-zero square number not larger than the current value. The game is usually played as a normal play

Misère game

Misere or misère is a bid in various card games, and the player who bids misere undertakes to win no tricks or as few as possible, usually at no trump, in the round to be played...

game, which means that the last person who can make a subtraction wins.

Illustration

A normal play game starting with the number 13 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

Recursion

Recursion is the process of repeating items in a self-similar way. For instance, when the surfaces of two mirrors are exactly parallel with each other the nested images that occur are a form of infinite recursion. The term has a variety of meanings specific to a variety of disciplines ranging from...

:

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

Cold numbers tend to end in 0, 2, 4, 5, 7, or 9. Cold values that end with other digits are quite uncommon. 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.

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 theory

Sprague–Grundy theorem

In combinatorial game theory, the Sprague–Grundy theorem states that every impartial game under the normal play convention is equivalent to a nimber. The Grundy value or nim-value of an impartial game is then defined as the unique nimber that the game is equivalent to...

. This requires the positions in the game subtract-a-square to be mapped onto equivalent nim heap sizes

Nim

Nim is a mathematical game of strategy in which two players take turns removing objects from distinct heaps. 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....

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

Notice that all 'cold' positions get mapped onto a zero heap size.

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