More on the Magnus-Derek game

Li Jui Chen, Jinn Jy Lin, Min-Zheng Shieh, Shi-Chun Tsai*

*Corresponding author for this work

Research output: Contribution to journalArticle

3 Scopus citations

Abstract

We consider the so called MagnusDerek game, which is a two-person game played on a round table with n positions. The two players are called Magnus and Derek. Initially there is a token placed at position 0. In each round Magnus chooses a positive integer m≤n2 as the distance of the targeted position from his current position for the token to move, and Derek decides a direction, clockwise or counterclockwise, to move the token. The goal of Magnus is to maximize the total number of positions visited, while Derek's is to minimize this number. If both players play optimally, we prove that Magnus, the maximizer, can achieve his goal in O(n) rounds, which improves a previous result with O(nlogn) rounds. Then we consider a modified version of the MagnusDerek game, where one of the players reveals his moves in advance and the other player plays optimally. In this case we prove that it is NP-hard for Derek to achieve his goal if Magnus reveals his moves in advance. On the other hand, Magnus has an advantage to occupy all positions. We also consider the circumstance that both players play randomly, and we show that the expected time to visit all positions is O(nlogn).

Original languageEnglish
Pages (from-to)339-344
Number of pages6
JournalTheoretical Computer Science
Volume412
Issue number4-5
DOIs
StatePublished - 4 Feb 2011

Keywords

  • Additive combinatorics
  • Two-person game

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

  • Cite this