← All problems

Duchêne–Rigo conjecture on invariant games for complementary Beatty sequences

16 years old · traced to

Let S=(An,Bn)n≥1S=(A_n,B_n)_{n\geq 1} be a pair of complementary Beatty sequences, and let an invariant game mean a combinatorial game whose legal moves are invariant under translation by game positions. A position is a PP-position if the previous player has a winning strategy.

Duchêne–Rigo conjecture. There exists an invariant game having

S∪{(0,0)}S\cup\{(0,0)\}

as its set of PP-positions.

This conjecture addresses the inverse problem of constructing games from prescribed complementary sequences.

References

2 papers in this index state this conjecture (2010–2022). The statement above is taken from the most recent of them; the others are arXiv:1005.4162.

Status

  • Solved: Urban Larsson, Peter Hegarty, and Aviezri S. Fraenkel. Invariant and dual subtraction games resolving the Duchêne–Rigo conjecture (Theoretical Computer Science, 2011) https://arxiv.org/abs/1005.4162

Source: Jon Kay and Geremias Polanco, “Relaxed Wythoff has All Beatty Solutions”, arXiv:2208.00041 (2023).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.