
Problem 8.3. Given $n$ points, $n \geq 5$, in the plane such that no three lie on a line. John and Peter play the following game: On his turn each of them draws a segment between any two points which are not connected. The winner is the one after whose move every point is an end of at least one segment. If John is to begin the game, find the values of $n$ for which he can always win no matter how Peter plays.


Solution: Call a point isolated if it is not an end of a segment. John wins exactly when there are 1 or 2 isolated points before his last move. Peter is forced to reach the above only if before his move there are exactly 3 isolated points and any of the remaining $n-3$ points are connected by a segment. Indeed, if there are at least 4 isolated points he could connect one of them with a non-isolated point. If the isolated points are 3 but not all of the remainig $n-3$ points are connected he could draw a missing segment. Since the number of segments with ends in $n-3$ points is $\frac{(n-3)(n-4)}{2}$, we determine that John wins only when $\frac{(n-3)(n-4)}{2}$ is an odd integer number. This is true when $n$ is of the form $4 k+1$ or $4 k+2$.
