Treffer: The Magnus-Derek game

Title:
The Magnus-Derek game
Authors:
NEDEV, Z, MUTHUKRISHNAN, S
Source:
Theoretical computer science. 393(1-3):124-132
Publisher Information:
Amsterdam: Elsevier, 2008.
Publication Year:
2008
Physical Description:
print, 8 ref
Original Material:
INIST-CNRS
Subject Terms:
Computer science, Informatique, Sciences exactes et technologie, Exact sciences and technology, Sciences et techniques communes, Sciences and techniques of general use, Mathematiques, Mathematics, Algèbre, Algebra, Théorie des nombres, Number theory, Sciences appliquees, Applied sciences, Informatique; automatique theorique; systemes, Computer science; control theory; systems, Informatique théorique, Theoretical computing, Algorithmique. Calculabilité. Arithmétique ordinateur, Algorithmics. Computability. Computer arithmetics, Divers, Miscellaneous, Algorithmique, Algorithmics, Algorítmica, Anneau, Ring, Anillo, Factorisation, Factorization, Factorización, Informatique théorique, Computer theory, Informática teórica, Jeu 2 personnes, Two person game, Juego 2 personas, Mathématiques, Mathematics, Matemáticas, Réseau anneau, Ring network, Red anillo, Stratégie, Strategy, Estrategia, Théorie nombre, Number theory, Teoría números, 11xx, 68R01, 68R99, 68Rxx, Jeu combinatoire, Terme, Algorithmic strategies, Combinatorial number theory, Discrete mathematics, Mobile agent, Network with inconsistent global sense of direction, Two-person games
Document Type:
Fachzeitschrift Article
File Description:
text
Language:
English
Author Affiliations:
University of Victoria, Victoria, BC, Canada
Rutgers University, United States
ISSN:
0304-3975
Access URL:
http://pascal-francis.inist.fr/vibad/index.php?action=search&terms=20217983
Rights:
Copyright 2008 INIST-CNRS
CC BY 4.0
Sauf mention contraire ci-dessus, le contenu de cette notice bibliographique peut être utilisé dans le cadre d’une licence CC BY 4.0 Inist-CNRS / Unless otherwise stated above, the content of this bibliographic record may be used under a CC BY 4.0 licence by Inist-CNRS / A menos que se haya señalado antes, el contenido de este registro bibliográfico puede ser utilizado al amparo de una licencia CC BY 4.0 Inist-CNRS
Notes:
Computer science; theoretical automation; systems

Mathematics
Accession Number:
edscal.20217983
Database:
PASCAL Archive

Weitere Informationen

We introduce a new combinatorial game between two players: Magnus and Derek. Initially, a token is placed at position 0 on a round table with n positions. In each round of the game Magnus chooses the number of positions for the token to move, and Derek decides in which direction, + (clockwise) or - (counterclockwise), the token will be moved. Magnus aims to maximize the total number of positions visited during the course of the game, while Derek aims to minimize this quantity. We define f* (n) to be the eventual size of the set of visited positions when both players play optimally. We prove a closed form expression for f* (n) in terms of the prime factorization of n, and provide algorithmic strategies for Magnus and Derek to meet this bound. We note the relevance of the game for a mobile agent exploring a ring network with faulty sense of direction, and we pose variants of the game for future study.