A set of 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 is given and Alice and Bob play the following game. In each turn Alice colors one segment red and then Bob colors up to 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 , then Alice has a winning strategy.
2. Prove that if , then Bob has a winning strategy.
Solution
1. We will call a threat an uncolored segment whose coloring of red would produce a triangle. We will show that Alice can use the following strategy to win: Alice will keep coloring segments whose one end-point is unless she can complete a triangle. We will call the other endpoints opposite ends. Let us assume that Bob can stop this strategy. Bob's optimal strategy to counter Alice's is first eliminating all threats in his move and then using his remaining moves to color segments coming out of . Note that after the -th red line is drawn, Bob must color threats blue, which are the lines connecting the new opposite end with all the previous opposite ends. Thus in the -th pair of moves of Alice and Bob, the number of colored edges coming out of has increased by . Assume there exists a such that after moves all segments out of have been colored before Alice could draw a triangle. Then we have
therefore the discriminant of the quadratic equation is non-negative, i.e. and therefore . Since this inequality is violated, it follows that Alice's winning strategy works.
2. We will show that Bob can use the following strategy to win: Whenever Alice colors a line , Bob will color edges out of blue and edges out of . This ensures at most red edges out of any point, which is not larger than for . Assuming Alice completes a triangle and WLOG moves , and in sequence, it follows that before placing there were at least threats out of . However this means, since placing created these threats, that, not counting , there were at least red lines out of and thus the total number of red lines coming out of is larger than , a contradiction.