On a circle there are $2n+1$ points, dividing it into equal arcs ($n\ge 2$). Two players take turns to erase one point. If after one player's turn, it turned out that all the triangles formed by the remaining points on the circle were obtuse, then the player wins and the game ends. Who has a winning strategy: the starting player or his opponent?
Problem
Source: All-Russian Olympiad 2012 Grade 11 Day 2
Tags: induction, combinatorics proposed, combinatorics
01.06.2012 03:46
Let $O$ be the centre of the circle 1) Three points on the circle form an acute triangle if and only if the triangle contains $O$ Proof: follows from that fact that if $ABC$ contains $O$ then $2\angle ABC=\angle AOC$, and the fact that opposite angles of cyclic quadrilaterals sum to $\pi$ 2) The game ends when a string of $n$ or more consecutive points on the circle has been removed Join all remaining points to form an $m$-gon, then triangulate it. If $O$ is in the $m$-gon then it is inside some (acute) triangle. Otherwise $O$ is outside the $m$-gon and all points lie in one half of the plane. This means there is some string of $n$ or more consecutive points that has been removed. 3) The second player always wins. When $n=2$ there are $5$ points, and the second player wins in their first turn by taking a point that is a neighbour of the point that the first player selected. If $n=k>2$ then number the points clockwise $1,2,...,2k+1$. WLOG player one removes point $1$, then player two removes point $k+1$. Notice now that any string of $k-1$ consecutive points must pass over or end at the point $1$ or $k+1$, so we can play the strategy for $2(k-1)+1$ points and insure a win. So, by induction, the second player always wins.
01.08.2019 08:33
The above solution is wrong! The string $k+2\cdots 2k+1$ has $k$ points and passes through neither $1$ nor $k+1$, so when we delete $1, k+1$ we do not get a reduced game.
01.08.2019 17:52
Here is a solution in the spirit of the above, but with different execution. Very nice problem Consider the $2n+1$ collections of $n$ contiguous points $A_1, \ldots, A_{2n+1}$ (indices mod $2n+1$). The game proceeds as follows: In a move, one picks an integer $k$ and decrements $S_k, S_{k+1}, \ldots, S_{k+n}$, where $S_k$ is defined as $|A_k|$. A player wins when some $S_i$ becomes zero. Another restriction we impose is that no integer $k$ can be picked twice. This allows for the following transformation: Given $2n+1$ piles of stones, each consisting of $n$ stones, a move consists of picking $n$ consecutive piles that have not been chosen before and removing a stone from each of the piles. The win condition is to fully deplete a condition; equivalently, the first player to make a pile have $1$ stone loses, since the other player now just picks the last block of $n$ piles that contains the pile with $1$ stone left and wins. Thus we play the game where the player to make a pile have exactly $1$ stone loses. Now, we claim that the second player always wins. For a block $P_1\dots P_n$ of stones, we say that the piles $P_0$ and $P_{n+1}$ are the two pivots of the block. Also, note that each pile is the pivot of two blocks. Thus, we may represent the situation as a graph $G$ in which blocks are vertices and piles are edges. Since $(n,2n+1) = 1$, $G$ is a $C_{2n+1}$, and players alternate turns picking vertices. Note that at any point, the vertices chosen form a bunch of disjoint paths. We claim that second player can always ensure that after their turn, each path has even length. We induct on the number of turns; after 0 this is clear. Now once first player moves, one path has odd length, and so second player just picks a vertex so as to extend the odd path (it's fine if this merges with another path, since we just add an even number of edges on to the now-even path). To see why this wins, note that after $2m$ vertices have been chosen, they can be partitioned into $m$ edges. Thus if we call the pivots $Q_1, \ldots, Q_m$, we see that we have removed $m$ stones from each pile but $m-1$ from $Q_1, \ldots, Q_m$. This results, when $m = n-2$, into us having $n-2$ piles with $3$ stones each, and $n+3$ piles of $2$ stones each. It is clear that first player's next move must remove a stone from one of the piles with $2$ stones, so first player must lose. $\blacksquare$