A reduced computational complexity strategy for the Magnus-Derek game
Zhivko Nedev · International Mathematical Forum · 2014
Copyright c © 2014 Zhivko Nedev. This is an open access article distributed under the Creative Commons Attribution License, which permits unrestricted use, distribution, and reproduction in any medium, provided the original work is properly cited. We analyze the Magnus-Derek game, a two-player game played on a round table having n positions. The players jointly control the movement of a token. One player aims to minimize the number of positions visited, and the other aims to maximize this quantity. We give an f∗(n) + log2(m − 1) f∗(m)-round strategy, where p is the smallest odd prime factor of n, m = np, and f is a function yielding the number of positions visited when both players play optimally. This strategy requires significantly less computation time than the previously published strategies. 1