There are 98 points on a circle. Two players play alternately as follows. Each player joins two points which are not already joined. The game ends when every point has been joined to at least one other. The winner is the last player to play. Does the first or second player have a winning strategy?
Solution
Answer: the first player has a winning strategy.
Assume there are n points. The first to play so that n-2 points each have at least one segment loses, because the other player simply joins the last two points and the game ends. But there are N = (n-3)(n-4)/2 possible plays amongst the first n-3 points to get a segment. For n = 1 or 2 mod 4, N is odd and for n = 0 or 3 it is even. So the first player wins for n = 1 or 2 mod 4 (and in particular for n = 98) and the second player for n = 0 or 3 mod 4.
© John Scholes
jscholes@kalva.demon.co.uk
24 Oct 2002