Maths Olympiad Prep

Library / /90 of 94

Combinatorics Difficulty 7.2 National Olympiad, round 2 Prove it 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?

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.

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.