Competition problem — Combinatorics

Library / /14 of 16

Combinatorics Difficulty 7.5 National olympiad, round 2 Prove it Argentina

Let $n \ge 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 $\frac{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.

Solution

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 \equiv 2$ or $3$ \pmod{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 lines $l_A$ and $l_B$ . We use the inductive hypothesis to pair coins in intersections between old lines and $\{p_{A1}, p_{B2}\}, \{p_{A2}, p_{B3}\}, \dots, \{p_{An}, p_{B1}\}$ to pair coins at intersections of old and new lines. It remains to be decided what to do with the coin at $p_{AB}$ and with zero or one coins, the discarded one among the old lines. In the first case we discard $p_{AB}$ and in the second we pair the two of them.

For the general case we paint the coins with $k$ colors in such a way that any two coins on the same point of intersection have different color. In particular, there are the same number of coins of each color. We consider two cases.

If this number is even, we use the case $k=1$ to find a pairing among the coins of each color and we are done.

If this number is odd, we use the case $k=1$ to find a pairing of all coins but one of each color. The discarded coins are chosen to be at $p_{12}$ and $p_{34}$ so that we can find a pairing among them that leaves at most one out as desired. Now that the claim is proved let's fix a good pairing that leaves at most one coin out. If the number of coins is even then there is no coin left out and if it is odd then there is one.

In the first case Beto has a winning strategy: every time that Ana chooses a coin he chooses the other coin in the same pair of our fixed good pairing.

In the second case Ana has a winning strategy: she first chooses the coin left out and then she proceeds as Beto in the previous case.

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 and solution reproduced as published; topic and difficulty added by this site.