## 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 language | English (US) |
---|---|

Pages (from-to) | 124-132 |

Number of pages | 9 |

Journal | Theoretical Computer Science |

Volume | 393 |

Issue number | 1-3 |

DOIs | |

State | Published - 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)