cp's OEIS Frontend

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.

%I A276163 #18 May 03 2025 07:44:31
%S A276163 1,1,2,4,5,9,6,16,9,25,10,36,13,49,14,64
%N 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.
%C A276163 a(2*n) = n^2 via [1, n+1, 2, n+2, ..., n, 2*n]
%D A276163 Peter Winkler, Mathematical Puzzles: A Connoisseur's Collection, A K Peters/CRC Press, 2003, pages 1-2.
%e A276163 a(1)  = 1  via [1]
%e A276163 a(2)  = 1  via [1,2]
%e A276163 a(3)  = 2  via [1,2,3]
%e A276163 a(4)  = 4  via [1,3,2,4]
%e A276163 a(5)  = 5  via [1,2,4,3,5]
%e A276163 a(6)  = 9  via [1,4,2,5,3,6]
%e A276163 a(7)  = 6  via [1,2,3,4,6,5,7]
%e A276163 a(8)  = 16 via [1,5,2,6,3,7,4,8]
%e A276163 a(9)  = 9  via [1,2,3,4,6,5,8,7,9]
%e A276163 a(10) = 25 via [1,6,2,7,3,8,4,9,5,10]
%e A276163 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.
%o A276163 (Haskell)
%o A276163 minimax [] = 0
%o A276163 minimax as = max (head as - minimax (tail as)) (last as - minimax (init as))
%o A276163 a276163 n = maximum $ map minimax $ permutations [1..n]
%Y A276163 Cf. A276164.
%K A276163 nonn,more
%O A276163 1,3
%A A276163 _Peter Kagey_, Aug 22 2016
%E A276163 a(11)-a(16) from _Bert Dobbelaere_, May 03 2025