Nonhomogeneous Beatty Sequences Leading to Invariant Games
Julien Cassaigne, Éric Duchêne, Michel Rigo · SIAM Journal on Discrete Mathematics · 2016
We characterize pairs of complementary nonhomogeneous Beatty sequences $(A_n)_{n>0}$ and $(B_n)_{n>0}$, with the restriction $A_1=1$ and $B_1\geq 3$, for which there exists an invariant take-away game having $\{(A_n,B_n),(B_n,A_n)\mid n> 0\}\cup\{(0,0)\}$ as a set of $P$-positions. Using the notion of a Sturmian word arising in combinatorics on words, this characterization can be translated into a decision procedure relying only on a few algebraic tests about algebraicity or rational independence. This work partially answers to a question of Larsson, Hegarty, and Fraenkel, raised in [Theoret. Comput. Sci., 412 (2011), pp. 729--735].