More on the Magnus-Derek game

Abstract

We consider the so called Magnus-Derek 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 O. In each round Magnus chooses a positive integer m <= n/2 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(n log n) rounds. Then we consider a modified version of the Magnus-Derek 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(n log n). (c) 2010 Elsevier B.V. All rights reserved.