|
| |
|
|
A338027
|
|
Lengths of games in optimal play of "subtract-a-square".
|
|
1
|
|
|
|
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, 7, 3, 5, 5, 9, 10, 5, 1, 7, 3, 6, 5, 3, 9, 5, 8, 7, 5, 9, 7, 1, 11, 3, 8, 9, 3, 7, 5, 10, 9, 5, 9, 7, 10, 11, 1, 8, 3, 12, 9, 3, 11, 5, 12, 11, 5, 7, 7, 9, 11, 5, 9, 1, 11, 3, 7, 10
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,3
|
|
|
COMMENTS
|
Consider a game of "take away" where at each turn a player is presented with an integer. The valid moves are to subtract a nonzero perfect square less than or equal to the starting number to generate the number that will be given to your opponent. The person who is given 0 loses the game. The winner's goal is to win in as few moves as possible, and the loser wants to force the winner to take as many moves as possible. a(n) is the length of the game with starting number n and perfect play by both players.
The optimal strategy in the game is a minimax strategy as follows: Given a starting number n, take away all squares less than n and determine whether playing any of those moves leaves your opponent with a "losing" number. If so, choose the move that leaves your opponent with a loss in the smallest number of moves assuming both of continue with this strategy. If you cannot leave your opponent with a "losing" number, then choose the move that maximizes the number of moves your opponent must take to win assuming both of you continue with this strategy. By applying this strategy recursively with a base case of "the player with 0 as their start loses in 0 moves," a game length for any possible starting position may be determined.
|
|
|
LINKS
|
|
|
|
FORMULA
|
Let S(n) be the set of nonzero perfect squares less than or equal to n. Let E be the set of even numbers.
a(0) = 0;
a(n) = Min_{a(n - s) with s in S(n) and a(n - s) in E} + 1 if there are any values of s in S(n) for which a(n - s) is in E. Otherwise:
a(n) = Max_{a(n - s) with s in S(n)} + 1.
|
|
|
EXAMPLE
|
If the starting number is 0, then the starting player loses immediately (in 0 turns), so a(0) = 0. If the starting number is a perfect square, the player can give their opponent a 0 in one move by subtracting the square immediately, thus a(n^2) = 1. If the starting number is 15, the player whose turn it is cannot win unless the other player plays suboptimally. An example optimal game from this point would be: 15 (loser takes away 4), 11 (winner takes away 9), 2 (loser takes away 1), 1 (winner takes away 1), 0 (current player loses). Thus a(15) = 4, a(11) = 3, a(2) = 2, a(1) = 1, and a(0) = 0.
|
|
|
PROG
|
(Python) # See Bauer link
|
|
|
CROSSREFS
|
A030193 gives all indices at which this sequence has an even value (corresponding to the losing positions).
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
