A Game where Construction of an odd cycle loses
Source: 2019 Canadian Mathematical Olympiad Problem 5
March 30, 2019
Game Theorygame strategyCombinatorial gamesgraph theorygraph cyclescombinatorics
Problem Statement
A 2-player game is played on points, where no 3 points are collinear. Each move consists of selecting 2 of the points and drawing a new line segment connecting them. The first player to draw a line segment that creates an odd cycle loses. (An odd cycle must have all its vertices among the points from the start, so the vertices of the cycle cannot be the intersections of the lines drawn.) Find all such that the player to move first wins.