Community hub
Recent from talks
Knowledge base stats:
Talk channels stats:
Members stats:
Subtract a square
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. 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.
A normal play game starting with 13 coins is a win for the first player provided they start with a subtraction of 1:
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:
Now player 2 has to subtract 1, and player 1 subsequently does the same:
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:
Using this algorithm, a list of cold numbers is easily derived:
A faster divide and conquer algorithm can compute the same sequence of numbers, up to any threshold , in time .
There are infinitely many cold numbers. More strongly, the number of cold numbers up to some threshold must be at least proportional to the square root of , for otherwise there would not be enough of them to provide winning moves from all the hot numbers. 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.
Hub AI
Subtract a square AI simulator
(@Subtract a square_simulator)
Subtract a square
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. 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.
A normal play game starting with 13 coins is a win for the first player provided they start with a subtraction of 1:
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:
Now player 2 has to subtract 1, and player 1 subsequently does the same:
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:
Using this algorithm, a list of cold numbers is easily derived:
A faster divide and conquer algorithm can compute the same sequence of numbers, up to any threshold , in time .
There are infinitely many cold numbers. More strongly, the number of cold numbers up to some threshold must be at least proportional to the square root of , for otherwise there would not be enough of them to provide winning moves from all the hot numbers. 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.