More on the Magnus-Derek game

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

*Corresponding author for this work

研究成果: Article同行評審

4 引文 斯高帕斯(Scopus)

摘要

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).

原文English
頁(從 - 到)339-344
頁數6
期刊Theoretical Computer Science
412
發行號4-5
DOIs
出版狀態Published - 4 二月 2011

指紋 深入研究「More on the Magnus-Derek game」主題。共同形成了獨特的指紋。

引用此