Let $P$ be a cyclic polygon with circumcenter $O$ that does not lie on any diagonal, and let $S$ be the set of points on 2D plane containing $P$ and $O$. The $\textit{Matcha Sweep Game}$ is a game between two players $A$ and $B$, with $A$ going first, such that each choosing a nonempty subset $T$ of points in $S$ that has not been previously chosen, and such that if $T$ has at least $3$ vertices then $T$ forms a convex polygon. The game ends with all points have been chosen, with the player picking the last point wins. For which polygons $P$ can $A$ guarantee a win? Proposed by Anzo Teh Zhao Yang
Problem
Source: Malaysian IMO TST 2023 P1
Tags: combinatorics
ACGNmath
30.04.2023 15:49
We claim that the answer is all polygons except for acute triangles. First, we demonstrate that $A$ cannot win with an acute triangle. In this case, $O$ lies within $P$. Therefore, $A$ cannot select all four points at once. Since he selects at least one point, $B$ is left with at most 3 points to select. This guarantees that $B$ will be able to select the remaining points (as a triangle is always convex). Now, we show that $A$ will always win with the other polygons. If $O$ lies outside $P$, then $A$ can just select all the points and win. If $O$ lies inside $P$, then triangulate the polygon. This can be done by labelling the vertices of $P$ to be $A_1, A_2, \dots, A_n$ in order, and then drawing $A_2 A_n$, $A_n A_3$, $A_3 A_{n-1}$, and so on. Since $O$ does not lie on any of these lines, this means that $O$ lies inside one of the triangles generated by the triangulation, say $\triangle A_i A_j A_k$. Pick all the points except for $A_i, A_j$, $A_k$ and $O$ (this can be done because the polygon now has more than 3 vertices). This set of points is convex because all the points lie on a circle. Therefore, $B$ is left with the triangle $A_i A_j A_k$ and $O$ inside it, which we have shown is impossible to win with. Therefore, $A$ will win in this case as well.
navi_09220114
13.10.2023 09:53
Official Solution: Answer: All polygons $P$ such that $P$ is not an acute-angled triangle. Solution: If $P$ is an acute-angled triangle, then $O$ lies inside $P$, so $A$ cannot choose $T=S$. Regardless of the $T$ chosen by $A$, there are at most 3 points left, so $B$ can just choose all the remaining points to win the game. Now suppose $P$ is not an acute-angled triangle. If $O$ is outside $P$ then the set $S$ is convex, and therefore $A$ can choose $T=S$. Otherwise, $|P|\ge 4$. Consider an arbitrary triangulation of $P$, and let $R$ be the triangle under this triangulation whose interior contains $O$. Then $A$ can choose $T = S\backslash (R\cup \{O\})$ (this $T$ is convex because it is a subset of $P$, which is convex). Now $B$ has to choose from $R\cup \{O\}$, which by the first paragraph means $B$ cannot win. $\blacksquare$