2016/12/09 by Aggarwal, Shubham, Geller, Jared, Sadhuka, Shuvom +1
#Combinatorics (math.CO) #FOS: Mathematics
paper · doi:10.48550/arxiv.1612.03068
Wythoff's Game is a variation of Nim in which players may take an equal number of stones from each pile or make valid Nim moves. W. A. Wythoff proved that the set of P-Positions (losing position), C, for Wythoff's Game is given by C := \ (\lfloor kϕ\rfloor, \lfloor kϕ2 \rfloor), (\lfloor kϕ2 \rfloor, \lfloor kϕ\rfloor) : k ∈ \mathbb Z≥ 0 \. An open Wythoff problem remains where players make the valid Nim moves or remove kb stones from each pile, where b is a fixed integer. We denote this as the (b,b) game. For example, regular Wythoff's Game is just the (1,1) game. In 2009, Duchêne and Gravier proved an algorithm to generate the set of P-Positions for the (2,2) game by exploiting the periodic nature of the differences of stones between the two piles modulo 4. We observe similar cyclic behaviour for any b, where b is a power of 2, modulo b2, and construct an algorithm to generate the set of P-Positions for this game. Let a be a power of 2. We prove our algorithm works by first showing that it holds for the first a2 terms in the (a,a) game. Next, we construct an ordered multiset for the (2a,2a) game from the a2 terms, and an inductive proof follows. Moreover, we conjecture that all cyclic games require a to be a power of 2, suggesting that there is no similar structure in the generalised (b,b) game where b isn't a power of 2. Future directions for generalising this result would likely utilise numeration systems, particularly the PV numbers.