Maths Olympiad Prep

Track / Stage 7 / 121 of 300 #2001 of 2444

Problem 2001

National Olympiad second round; IMO P1/P4
Combinatorics Difficulty 7.2 Prove it China Hong Kong Mathematical Olympiad · Hong Kong

Let n2n \ge 2 be an integer. There are nn distinct circles on the plane such that any two circles have two distinct intersections and no three circles have a common intersection. Initially there is a coin on each of the intersection points of the circles. Starting from XX, players XX and YY alternately take away a coin, with the restriction that one cannot take away a coin lying on the same circle as the last coin just taken away by the opponent in the previous step. The one who cannot do so will lose. In particular, one loses when there is no coin left. For what values of nn does YY has a winning strategy?

This one wants a proof. Work it on paper, then read the official solution and mark yourself. Be honest about it: the record is only any use to you if it is.

Next problem →

Official solution

YY has a winning strategy if and only if n4n \ge 4.
For n=2,3n = 2, 3, after XX takes away any coin, YY cannot take away any other coin. Therefore, YY does not have a winning strategy.
For n4n \ge 4, we claim that YY has a winning strategy. Since the total number 2(n2)2\binom{n}{2} of coins is even, it suffices to partition all the coins into pairs such that the two coins in the same pair do not lie on the same circle. Once this is done, the strategy of YY is to take away the coin in the same pair as the coin just taken away by XX. Clearly, YY can win as there is always a move, and the number of coins is finite.
We label the circles from 11 to nn, and let Aij=AjiA_{ij} = A_{ji} and Bij=BjiB_{ij} = B_{ji} be the intersection points of circle ii and circle jj. For any jj, we pair up Aj(j+1)A_{j(j+1)} with B(j+2)(j+3)B_{(j+2)(j+3)}, where all indices are taken modulo nn. Since n4n \ge 4, these two points do not lie on the same circle. Next, we pair up any other point AijA_{ij} with B(i+1)(j+1)B_{(i+1)(j+1)}. Note that ij+1(modn)i \ne j+1 \pmod n and ji+1(modn)j \ne i+1 \pmod n by assumption. Therefore, these two points do not lie on the same circle. This gives a desired pairing, and so we are done.

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