login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A276166
a(n) is the first player's score in a "Coins in a Row" game over the n-th row of A066099 using a minimax strategy.
3
0, 1, 2, 1, 3, 2, 2, 2, 4, 3, 2, 3, 3, 2, 3, 2, 5, 4, 3, 4, 3, 3, 3, 3, 4, 2, 3, 3, 4, 3, 3, 3, 6, 5, 4, 5, 3, 4, 4, 4, 4, 3, 4, 3, 4, 4, 3, 4, 5, 2, 3, 4, 4, 3, 4, 3, 5, 4, 3, 3, 4, 3, 4, 3, 7, 6, 5, 6, 4, 5, 5, 5, 4, 4, 5, 4, 4, 5, 4, 5, 5, 3, 4, 4, 5, 4, 4
OFFSET
0,3
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 1-2.
FORMULA
a(n) = A029837(n + 1) - A276167(n).
a(n) = A276165(n) + A276167(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) = 1 via [L]
A066099_Row(3) = [1,1]; a(3) = 1 via [R,L]
A066099_Row(22) = [2,1,2]; a(22) = 3 via [L,R,L]
A066099_Row(88) = [2,1,4]; a(88) = 5 via [R,L,L]
A066099_Row(1418) = [2,1,4,2,2]; a(1418) = 5 via [L,R,R,R,L]
PROG
(Haskell)
minimaxDifference [] = 0
minimaxDifference as = max (head as - minimaxDifference (tail as)) (last as - minimaxDifference (init as))
minimaxScore as = (sum as + minimaxDifference as) `div` 2
a276166 = minimaxScore . a066099_row
CROSSREFS
KEYWORD
nonn
AUTHOR
Peter Kagey, Aug 25 2016
STATUS
approved