1,5

A positive value indicates that all permutations of 1..n result in a game where the first player has a winning strategy.

A negative value indicates that there exists a permutation of 1..n where the second player has a winning strategy.

a(2*k) is strictly nonnegative.

Conjecture: a(2*n - 1) = -A067998(n).

Conjecture: a(n) = n + 1 - A276163(n + 1) for all n >= 1.

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

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

a(1) = 1; via [1]

a(2) = 1; via [1,2]

a(3) = 0; via [1,3,2]

a(4) = 0; via [1,2,4,3]

a(5) = -3; via [1,4,2,5,3]

a(6) = 1; via [1,2,3,4,6,5]

a(7) = -8; via [1,5,2,6,3,7,4]

a(8) = 0; via [1,2,3,4,6,5,8,7]

a(9) = -15; via [1,6,2,7,3,8,4,9,5]

(Haskell)

minimax [] = 0

minimax as = max (head as - minimax (tail as)) (last as - minimax (init as))

a276168 n = minimum $ map minimax $ permutations [1..n]

Cf. A276163.

Sequence in context: A096797 A084246 A141252 * A165498 A195731 A154294

Adjacent sequences: A276165 A276166 A276167 * A276169 A276170 A276171

sign,more

Peter Kagey, Aug 29 2016

approved