The Magnus-Derek game

Z. Nedev, S. Muthukrishnan

    Research output: Contribution to journalArticlepeer-review

    Abstract

    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.

    Original languageEnglish (US)
    Pages (from-to)124-132
    Number of pages9
    JournalTheoretical Computer Science
    Volume393
    Issue number1-3
    DOIs
    StatePublished - Mar 20 2008

    Keywords

    • Algorithmic strategies
    • Combinatorial number theory
    • Discrete mathematics
    • Mobile agent
    • Network with inconsistent global sense of direction
    • Two-person games

    ASJC Scopus subject areas

    • Theoretical Computer Science
    • Computer Science(all)

    Fingerprint Dive into the research topics of 'The Magnus-Derek game'. Together they form a unique fingerprint.

    Cite this