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, 10, 36, 13, 49, 14, 64
Offset: 1
Examples
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.
References
- Peter Winkler, Mathematical Puzzles: A Connoisseur's Collection, A K Peters/CRC Press, 2003, pages 1-2.
Crossrefs
Cf. A276164.
Programs
-
Haskell
minimax [] = 0 minimax as = max (head as - minimax (tail as)) (last as - minimax (init as)) a276163 n = maximum $ map minimax $ permutations [1..n]
Extensions
a(11)-a(16) from Bert Dobbelaere, May 03 2025
Comments