Problem

Source: 2021 Saudi Arabia BMO TST 2.4

Tags: combinatorics, Coloring



A set of $n$ points in space is given, no three of which are collinear and no four of which are co-planar (on a single plane), and each pair of points is connected by a line segment. Initially, all the line segments are colorless. A positive integer $b$ is given and Alice and Bob play the following game. In each turn Alice colors one segment red and then Bob colors up to $b$ segments blue. This is repeated until there are no more colorless segments left. If Alice colors a red triangle, Alice wins. If there are no more colorless segments and Alice hasn’t succeeded in coloring a red triangle, Bob wins. Neither player is allowed to color over an already colored line segment. 1. Prove that if $b < \sqrt{2n - 2} -\frac32$ , then Alice has a winning strategy. 2. Prove that if $b \ge 2\sqrt{n}$, then Bob has a winning strategy.