The Game of Cycles

Bachelor thesis (2022)

Authors

J.S. Zandee Electrical Engineering, Mathematics and Computer Science

Contributors

R.J. Fokkink Applied Probability - EEMCS (supervisor 1)
A. Bishnoi Discrete Mathematics and Optimization - EEMCS (supervisor 2)
Faculty
Electrical Engineering, Mathematics and Computer Science
Copyright: © 2022 Jonathan Zandee
More Info
expand_more

Published Date

08-07-2022

Language

English

Reuse Rights

Other than for strictly personal use, it is not permitted to download, forward or distribute the text or part of it, without the consent of the author(s) and/or copyright holder(s), unless the work is under an open content license such as Creative Commons.

Faculty

Electrical Engineering, Mathematics and Computer Science

Abstract

The Game of Cycles, invented by Francis Su (2020, p.51) is an impartial game played on a graph, where players take turns marking an edge according to a set of rules. Together with the game, there also came a conjecture that gives a condition for whether a specific position is winning or losing. Proving or disproving this conjecture is the main focus of this research, which we end up succeeding in by giving a counter-example, thus disproving the conjecture. We do this by first showcasing some relevant background knowledge from game theory in chapter 1. In chapter 2 we then introduce the Game of Cycles and its rules, as well as some of the previous results others have found. We continue in chapter 3 by creating a python script to brute-force the game for us and it is here that we find a counter-example to the main conjecture, of which we prove that it is indeed a counter-example. We close off with chapter 4 by looking at a simplification of the game, where it is played on trees instead of any graph. Here we prove that the main conjecture does hold for a special family of trees and state a conjecture for the solution of any tree.