Document RAIRO-Theor. Inf. Appl. 42, 375-393 (2008)
DOI: 10.1051/ita:2007039
A morphic approach to combinatorial games: the Tribonacci case
Eric Duchêne and Michel RigoInstitute of Mathematics, University of Liège, Grande Traverse 12 (B37), 4000 Liège, Belgium; Eric.Duchene@ulg.ac.be; M.Rigo@ulg.ac.be
(Received May 7, 2007. Accepted September 26, 2007. Published online 13 December 2007.)
Abstract
We propose a variation of Wythoff's game on three piles
of tokens, in the sense that the losing positions can be derived from
the Tribonacci word instead of the Fibonacci word for the two
piles game. Thanks to the corresponding exotic numeration system
built on the Tribonacci sequence, deciding whether a game position is
losing or not can be computed in polynomial time.
Mathematics Subject Classification. 91A46, 68R15, 68Q45
Key words: Two-player combinatorial game -- combinatorics on words -- numeration system -- Tribonacci sequence
© EDP Sciences 2007