Geodesic
Cumulative subtraction games
The electronic journal of combinatorics, Tome 26 (2019) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

We study a variation of Nim-type subtraction games, called Cumulative Subtraction (CS). Two players alternate in removing pebbles out of a joint pile, and their actions add or remove points to a common score. We prove that the zero-sum outcome in optimal play of a CS with a finite number of possible actions is eventually periodic, with period $2s$, where $s$ is the size of the largest available action. This settles a conjecture by Stewart in his Ph.D. thesis (2011). Specifically, we find a quadratic bound, in the size of $s$, on when the outcome function must have become periodic. In case of exactly two possible actions, we give an explicit description of optimal play.
DOI : 10.37236/7904
Classification : 91A46, 91A05
Mots-clés : combinatorial games, two players, zero-sum outcome, Nim-like game, subtraction game 
@article{10_37236_7904,
     author = {Gal Cohensius and Urban Larsson and Reshef Meir and David Wahlstedt},
     title = {Cumulative subtraction games},
     journal = {The electronic journal of combinatorics},
     year = {2019},
     volume = {26},
     number = {4},
     doi = {10.37236/7904},
     zbl = {1442.91015},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/7904/}
}
TY  - JOUR
AU  - Gal Cohensius
AU  - Urban Larsson
AU  - Reshef Meir
AU  - David Wahlstedt
TI  - Cumulative subtraction games
JO  - The electronic journal of combinatorics
PY  - 2019
VL  - 26
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/7904/
DO  - 10.37236/7904
ID  - 10_37236_7904
ER  - 
%0 Journal Article
%A Gal Cohensius
%A Urban Larsson
%A Reshef Meir
%A David Wahlstedt
%T Cumulative subtraction games
%J The electronic journal of combinatorics
%D 2019
%V 26
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/7904/
%R 10.37236/7904
%F 10_37236_7904
Gal Cohensius; Urban Larsson; Reshef Meir; David Wahlstedt. Cumulative subtraction games. The electronic journal of combinatorics, Tome 26 (2019) no. 4. doi: 10.37236/7904

Cité par Sources :