XXIX Rioplatense Mathematical Olympiad

Question

Let n 4 and k be positive integers. We consider n lines on the plane such that no two of them are parallel and no three of them intersect in a single point. On each of the n(n-1)2 intersection points of these lines there are k coins. Ana and Beto play the following game: each player, in their turn, chooses a point that does not lie on the same line as the point chosen in the previous turn by the other player, and discards one coin from that point. Ana makes the first move and she can choose any point. The player who cannot make a move loses the game. Determine, for each value of n and k, which player has a winning strategy.

Accepted Answer

We will prove that Ana has a winning strategy if and only if the total number of coins is odd. It is easy to see that this happens if and only if k is odd and n 2 or 3 4. For the rest of the solution we think of the lines as numbered from 1 to n and denote by p_ij the intersection of lines i and j. We will say that a pairing of a family of coins is good if coins in the same pair are not in the same line. We claim that there is a good pairing that leaves at most one coin out. If k=1 we proceed by induction. For n=4 we can pair coins according to the following pairs of points p_12, p_34, p_13, p_24, p_14, p_23, and for n=5 we can do it according to p_12, p_35, p_23, p_41, p_34, p_52, p_45, p_13, p_51, p_24. For the inductive step we assume that we already have n lines and we add two new lin…