Maths Olympiad Prep

Library / /78 of 520

Combinatorics Difficulty 5.5 AIME, harder Find the answer

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?

A number or a short expression. Spacing and $ signs are ignored.

Solution

Answer: the first player has a winning strategy.

Assume there are nn points. The first to play so that n2n-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=(n3)(n4)/2\mathrm{N}=(\mathrm{n}-3)(\mathrm{n}-4) / 2 possible plays amongst the first n3\mathrm{n}-3 points to get a segment. For n=1\mathrm{n}=1 or 2mod4, N2 \bmod 4, \mathrm{~N} is odd and for n=0\mathrm{n}=0 or 3 it is even. So the first player wins for n=1\mathrm{n}=1 or 2mod42 \bmod 4 (and in particular for n=98\mathrm{n}=98 ) and the second player for n=0\mathrm{n}=0 or 3mod43 \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: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.