A276163 a(n) is the maximum first-player score difference of a "Coins in a Row" game over all permutations of coins 1..n with both players using a minimax strategy.

1, 1, 2, 4, 5, 9, 6, 16, 9, 25

Offset

1,3

Comments

a(2*n) = n^2 via [1, n+1, 2, n+2, ..., n, 2*n]

References

Peter Winkler, Mathematical Puzzles: A Connoisseur's Collection, A K Peters/CRC Press, 2003, pages 1-2.

Links

Table of n, a(n) for n=1..10.

Example

a(1)  = 1  via [1]
a(2)  = 1  via [1,2]
a(3)  = 2  via [1,2,3]
a(4)  = 4  via [1,3,2,4]
a(5)  = 5  via [1,2,4,3,5]
a(6)  = 9  via [1,4,2,5,3,6]
a(7)  = 6  via [1,2,3,4,6,5,7]
a(8)  = 16 via [1,5,2,6,3,7,4,8]
a(9)  = 9  via [1,2,3,4,6,5,8,7,9]
a(10) = 25 via [1,6,2,7,3,8,4,9,5,10]
For n=4, the first player would take 4, the second player would take 2, the first player would take 3, and the second player would take 1. The resulting score difference would be 4 - 2 + 3 - 1 = 4.

Prog

(Haskell)
minimax [] = 0
minimax as = max (head as - minimax (tail as)) (last as - minimax (init as))
a276163 n = maximum $ map minimax $ permutations [1..n]

Crossrefs

Cf. A276164.

Sequence in context: A368797 A011175 A109534 * A011341 A116477 A116920

Adjacent sequences: A276160 A276161 A276162 * A276164 A276165 A276166

Keyword

nonn,more

Author

Peter Kagey, Aug 22 2016

Status

approved