Competition problem — Combinatorics

Library / /24 of 61

Combinatorics Difficulty 5.4 AIME, harder Prove it Ibero-American Mathematical Olympiad

Problem:

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

Solution:

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 \bmod 4$ , $N$ is odd and for $n = 0$ or $3$ it is even. So the first player wins for $n = 1$ or $2 \bmod 4$ (and in particular for $n = 98$ ) and the second player for $n = 0$ or $3 \bmod 4$ .

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.