An O(n)-round strategy for the Magnus-Derek game

DOI10.3390/A3030244MaRDI QIDQ1662552zbMATH OpenOpenAlexFDO

Authors Zhivko Nedev

Publication date 20 August 2018

Published in Algorithms (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://doi.org/10.3390/a3030244

zbMATH Keywords

additive combinatoricsalgorithmic game theorycombinatorial games

Mathematics Subject Classification ID

Combinatorics in computer science (68R05) Analysis of algorithms (68W40) 2-person games (91A05) Combinatorial games (91A46)

Review text

Summary: We analyze further the \textit{Magnus-Derek} game, a two-player game played on a round table with \(n\) positions. The players jointly control the movement of a token. One player, Magnus, aims to maximize the number of positions visited while minimizing the number of rounds. The other player, Derek, attempts to minimize the number of visited positions. We present a new strategy for Magnus that succeeds in visiting the maximal number of positions in \(3(n-1)\) rounds, which is the optimal number of rounds up to a constant factor.

Recommendations

• More on the Magnus-Derek game
• The Magnus-Derek game
• The Magnus-Derek game in groups
• The c game revisited
• Domination game on paths and cycles

Cites work

• An algorithm for finding a nearly minimal balanced set in \(\mathbb{F}_p\)
• BALANCED SETS AND THE VECTOR GAME
• On the Addition of Residue Classes
• The c game revisited
• The Magnus-Derek game
• The On-Line Encyclopedia of Integer Sequences
• Universal sets and the vector game

Cited in

(7)

• The Magnus-Derek game
• Palindromes in finite groups and the explorer-director game
• The Magnus-Derek game in groups
• The explorer-director game on graphs
• More on the Magnus-Derek game
• Lower bound for balanced sets
• The c game revisited

This page was built for publication: An \(O(n)\)-round strategy for the Magnus-Derek game

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1662552)