CPL - Chalmers Publication Library
| Utbildning | Forskning | Styrkeområden | Om Chalmers | In English In English Ej inloggad.

Invariant and dual subtraction games resolving the Duchene-Rigo conjecture

Urban Larsson (Institutionen för matematiska vetenskaper, matematik) ; Peter Hegarty (Institutionen för matematiska vetenskaper, matematik) ; A. S. Fraenkel
Theoretical Computer Science (0304-3975). Vol. 412 (2011), 8-10, p. 729-735.
[Artikel, refereegranskad vetenskaplig]

We prove a recent conjecture of Duchene and Rigo, stating that every complementary pair of homogeneous Beatty sequences represents the solution to an invariant impartial game. Here invariance means that each available move in a game can be played anywhere inside the game board. In fact, we establish such a result for a wider class of pairs of complementary sequences, and in the process generalize the notion of a subtraction game. Given a pair of complementary sequences (a(n)) and (b(n)) of positive integers, we define a game G by setting {{a(n), b(n)}} as invariant moves. We then introduce the invariant game G*, whose moves are all non-zero P-positions of G. Provided the set of non-zero P-positions of G* equals {{a(n), b(n)}}, this is the desired invariant game. We give sufficient conditions on the initial pair of sequences for this 'duality' to hold.

Nyckelord: Beatty sequence, Complementary sequences, Impartial game, Invariant, game, Superadditivity



Denna post skapades 2011-03-14. Senast ändrad 2012-02-10.
CPL Pubid: 137933

 

Läs direkt!


Länk till annan sajt (kan kräva inloggning)


Institutioner (Chalmers)

Institutionen för matematiska vetenskaper, matematik (2005-2016)

Ämnesområden

Annan matematik

Chalmers infrastruktur

Relaterade publikationer

Denna publikation ingår i:


Impartial Games and Recursive Functions