Till sidans topp

Sidansvarig: Webbredaktion
Sidan uppdaterades: 2012-09-11 15:12

Tipsa en vän
Utskriftsversion

Invariant and dual subtra… - Göteborgs universitet Till startsida
Webbkarta
Till innehåll Läs mer om hur kakor används på gu.se

Invariant and dual subtraction games resolving the Duchene-Rigo conjecture

Artikel i vetenskaplig tidskrift
Författare Urban Larsson
Peter Hegarty
A. S. Fraenkel
Publicerad i Theoretical Computer Science
Volym 412
Nummer/häfte 8-10
Sidor 729-735
ISSN 0304-3975
Publiceringsår 2011
Publicerad vid Institutionen för matematiska vetenskaper, matematik
Sidor 729-735
Språk en
Länkar dx.doi.org/10.1016/j.tcs.2010.11.01...
Ämnesord Beatty sequence, Complementary sequences, Impartial game, Invariant, game, Superadditivity
Ämneskategorier Annan matematik

Sammanfattning

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.

Sidansvarig: Webbredaktion|Sidan uppdaterades: 2012-09-11
Dela:

På Göteborgs universitet använder vi kakor (cookies) för att webbplatsen ska fungera på ett bra sätt för dig. Genom att surfa vidare godkänner du att vi använder kakor.  Vad är kakor?