Let $n \ge 4$ and $k$ be positive integers. We consider $n$ lines in the plane between which there are not two parallel nor three concurrent. In each of the $\frac{n(n-1)}{2}$ points of intersection of these lines, $k$ coins are placed. Ana and Beto play the following game in turns: each player, in turn, chooses one of those points that does not share one of the $n$ lines with the point chosen immediately before by the other player, and removes a coin from that point. Ana starts and can choose any point. The player who cannot make his move loses. Determine based on $n$ and $k$ who has a winning strategy.
Problem
Source: Rioplatense 2022 L3 p5
Tags: combinatorics, game strategy, winning strategy, game
nestor-ortigoza
05.01.2023 06:20
I think I overcomplicated a bit here, if anyone has a shorter solution please post it.
If two points lie on the same line, we will say they $\textit{block}$ each other.
We will begin by proving we can split the points into pairs, such that in each pair, the two points do not block each other (If there is an odd number of points, then there is exactly one point not in a pair).
Label the $n$ lines $L_1,\ldots, L_n$. Then, we can label the point that lies in the intersection of $L_i$ and $L_j$ as $(L_i, L_j)$. Let us start pairing the points, until we reach a point we cannot choose a pair for. Let us call this point $(L_a, L_b)$. Then, we know that every point not lying in $L_a$ or $L_b$ is already in a pair. If $(L_a, L_b)$ is the only point without a pair left, then the number of points is odd, and we have achieved our goal. otherwise, there is at least another unpaired point lying in $L_a$ or $L_b$. WLOG, suppose this point is $(L_1,L_a)$. Take a look at $L_1$. We are sure that all points lying in $L_1$ are in a pair, except for $(L_1,L_a)$ and $(L_1,L_b)$. These are $n-3$ points in total. If at least one of them is not paired with a point lying in $L_a$ then we can choose that point, pair it with $(L_a, L_b)$, and take its original pair and pair it with $(L_1, L_a)$. If this is not possible, then all of those $n-3$ points in $L_1$ are paired with the $n-3$ points remaining in $L_a$. Let this be the case. If a point in $L_b$ (not $(L_1,L_b)$) has a pair, then we can take the point in $L_b$ and pair it with $(L_1, L_a)$, and take its pair and pair it with $(L_a, L_b)$, given that we are assuming that all points lying in $L_1$ are paired with the points in $L_a$ (except for $(L_1, L_a)$ and $(L_1, L_b)$). So, suppose no points in $L_b$ have a pair. Then we can take, WLOG, $(L_2, L_b)$ and pair it with $(L_1, L_a)$. Thus we have shown that we can always increase the number of pairs (until we have no points left).
If the number of points is even, then Beto can split the points into pairs. Then, when Ana chooses a point, Beto chooses its pair. In this manner, Beto is guaranteed to always have a possible move, and since we have a finite amount of points, he wins.
Let $\frac{n(n-1)}{2}$ be odd. We have two cases.
Case 1: $k$ is odd.
Ana chooses a point, Beto chooses another (let us call this last point $P$. Then, Ana splits the points into pairs: the unpaired point is the point she chose first, an the pair of $P$ does not lie in the same line as the unpaired point. Then, Ana chooses the unpaired point again (unless $k=1$, in which case she can choose the pair of the point chosen by Beto and repeat that strategy to win). In the following moves, if Beto chooses the pair of $P$, Ana chooses the unpaired point, if Beto chooses the unpaired point, Ana chooses the pair of $P$, and if Beto chooses any other point, Ana chooses its pair. In this way, Ana always has a move secured, so she wins.
Case 2: $k$ is even.
In his first turn, Beto splits the points into pairs, leaving the first point chosen by Ana unpaired. He proceeds to choose some point available, let us call it $P$ (its pair must not lie in the same line as Ana's first point, which can be granted by the Pigeonhole principle). If Ana repeats her choice, then Beto chooses the pair of $P$. If Ana chooses another point, Beto chooses its pair. If Ana chooses the pair of $P$, Beto chooses the unpaired point. If Beto repeats this strategy, he always has a possible move
Thus we can state that Beto wins if the total of coins is even, while Ana wins if it is odd.