

A276167


a(n) is the second player's score in a "Coins in a Row" game over the nth row of A066099 using a minimax strategy.


3



0, 0, 0, 1, 0, 1, 1, 1, 0, 1, 2, 1, 1, 2, 1, 2, 0, 1, 2, 1, 2, 2, 2, 2, 1, 3, 2, 2, 1, 2, 2, 2, 0, 1, 2, 1, 3, 2, 2, 2, 2, 3, 2, 3, 2, 2, 3, 2, 1, 4, 3, 2, 2, 3, 2, 3, 1, 2, 3, 3, 2, 3, 2, 3, 0, 1, 2, 1, 3, 2, 2, 2, 3, 3, 2, 3, 3, 2, 3, 2, 2, 4, 3, 3, 2, 3, 3
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

0,11


COMMENTS

"Coins in a Row" is a game in which players alternate picking up coins of varying denominations from the end of the row in an attempt to collect as many points as possible.


REFERENCES

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


LINKS

Peter Kagey, Table of n, a(n) for n = 0..10000


FORMULA

a(n) = A029837(n + 1)  A276166(n).
a(n) = A276166(n)  A276165(n).


EXAMPLE

Let [R,L,L,L] represent a game in which the first player takes the right coin, the second player takes the left coin, the first player takes the left coin, and the second player takes the left (only remaining) coin.
A066099_Row(0) = [0]; a(0) = 0 via [L]
A066099_Row(1) = [1]; a(1) = 0 via [L]
A066099_Row(3) = [1,1]; a(3) = 1 via [R,L]
A066099_Row(22) = [2,1,2]; a(22) = 2 via [L,R,L]
A066099_Row(88) = [2,1,4]; a(88) = 2 via [R,L,L]
A066099_Row(1418) = [2,1,4,2,2]; a(1418) = 6 via [L,R,R,R,L]


PROG

(Haskell)
minimaxDifference [] = 0
minimaxDifference as = max (head as  minimaxDifference (tail as)) (last as  minimaxDifference (init as))
minimaxScore2 as = (sum as  minimaxDifference as) `div` 2
a276167 = minimaxScore2 . a066099_row


CROSSREFS

Cf. A276163, A276164, A276165, A276166.
Sequence in context: A214501 A057856 A117939 * A105522 A131774 A078316
Adjacent sequences: A276164 A276165 A276166 * A276168 A276169 A276170


KEYWORD

nonn


AUTHOR

Peter Kagey, Aug 25 2016


STATUS

approved



