Given $n \ge 2$ points on a circle, Alice and Bob play the following game. Initially, a tile is placed on one of the points and no segment is drawn. The players alternate in turns, with Alice to start. In a turn, a player moves the tile from its current position $P$ to one of the $n-1$ other points $Q$ and draws the segment $PQ$. This move is not allowed if the segment $PQ$ is already drawn. If a player cannot make a move, the game is over and the opponent wins. Determine, for each $n$, which of the two players has a winning strategy.
Problem
Source: Francophone 2024, Junior P2
Tags: combinatorics, combinatorics proposed, game, winning strategy
08.04.2024 16:43
Claim: Alice wins for all $n$. Proof: We can show this by showing a winning stratgy that guarantees Alice a win. For $n = 2$, it's obvious that Alice wins. For $n > 2$, we could label the points as following: Name the on which the pawn starts $(1)$, then, we name the point clockwise adjacent to $(1)$ by $(2)$, and so on till $(n)$. Alice can start by going from $(1)$ to $(2)$, then for any point that Bob goes to, Alice goes to the point that is available between $(1)$ and $(2)$, which is obviously unique. Since Bob has to visit a new point and cant return to any other points he's visited, and Alice can always find a move after Bob, and $n$ is finite, Bob will always run out of moves before Alice, and thus, Alice wins the game.
08.04.2024 18:38
A nice and easy problem. Funny how this isn't a classical problem. My solution is basically the same as above but posting anyways for storage purposes. We claim that Alice can win for all $n\geq 2$ by following the given algorithm. First label the points $P_1 , P_2, \dots , P_n$ where $P_1$ is the point on which the tile is initially placed. Algorithm : Alice moves from the current position $P$ to $P_1$ or $P_2$ alternating between these positions such that she moves to $P_2$ on an odd numbered move of hers and $P_1$ on an even numbered move. Proof : The first move will be from $P_1$ to $P_2$ according to the above algorithm, which is perfectly valid. We prove via induction that on each move of Bob's he must move to a new (unvisited) point. It is clear that in Bob's first move he cannot move from $P_2$ to $P_1$ and thus, he must move to a new point as claimed. Now, say points $P_1,P_2,\dots, P_n$ are visited for some $n\geq 3$ and the tile is currently at $P_n$ (which is visited for the first time). By Alice's strategy, she moves this to either $P_2$ and $P_1$ (depending on the parity of $n$ as described before). Now, according to Alice's strategy all of the segments $A_1A_m$ and $A_2A_m$ are drawn for $m \leq n$ since Bob uses one of these edges to reach $P_m$ and Alice uses the other to return to one of $P_1$ and $P_2$. Thus, Bob cannot move to any of $P_1,\dots, P_n$ forcing him to move to a new point as claimed. Thus, Alice simply has to return to one of $A_1$ or $A_2$ after Bob has done his move, guaranteeing Alice a move if there is a valid move for Bob. But, since the number of points is finite, Bob will eventually run out of new points to visit and thus Alice is guaranteed to win under this algorithm.