, 2019

$78$

Label the vertices of the regular $120$-gon as $A_1, A_2, \dots, A_{120}$ clockwise. Form six subsets of the set of all the vertices $A_i$, $i = 1, 2, \dots, 120$ by putting the vertex $A_i$ into the $r$-th group for $r = 1, 2, \dots, 6$ if the remainder obtained is $r-1$ when $i$ is divided by $6$. Note that for $r = 1, 2, \dots, 6$ the vertex $A_r$ belongs to the $r$-th group, which we call simply the group $r$.

Call a triplet $(X, Y, Z)$ of vertices of the regular $120$-gon a bad triangle if $X, Y, Z$ are located clockwise in this order and if $\angle YXZ = \angle YZX$, and $\angle XYZ = 18^\circ$. Note that the vertices of the regular $120$-gon lie on the same circle and they divide the circumference of the circle into $120$ segments of equal length. Let us call $O$ the center of this circle. If $(A_i, A_j, A_k)$ is a bad triangle, we have $\angle A_j A_i A_k = 81^\circ$, from which it follows that $\angle A_j O A_k = 2 \cdot 81^\circ$, which, in turn, implies that $k-j \equiv 54 \pmod{120}$. We also get $j-i \equiv 54 \pmod{120}$ by the same argument. Thus, we conclude that $A_i, A_j, A_k$ belong to the same group.

Fix a positive integer $r$ satisfying $1 \le r \le 6$, and define for $1 \le i \le 20$ $B_i = A_{54i+r}$. Here, we let $A_{n+120} = A_n$. From the fact that the greatest common divisor of $120$ and $54$ is $6$ and in view of the Chinese Remainder Theorem, we see that in each of $B_1, B_2, \dots, B_{20}$ an element of the group $r$ appears exactly once. For a triplet $(B_i, B_{i+1}, B_{i+2})$ belonging to the group $r$, $(B_i, B_{i+1}, B_{i+2})$ is a bad triangle if and only if $i+2 \equiv j+1 \equiv k \pmod{20}$.

Now suppose there are $14$ or more vertices marked with $*$ among the vertices of the group $r$. Let $i$ be an integer satisfying $1 \le i \le 20$, and consider a triplet $(B_i, B_{i+1}, B_{i+2})$ of vertices. (Here, we let $B_{n+20} = B_n$.) If $B_k$ is not marked by $*$, then there are exactly $3$ indices $i$ for which one of the vertices among $B_i, B_{i+1}, B_{i+2}$ coincides with $B_k$. Consequently, the number of $i$ for which at least one of $B_i, B_{i+1}, B_{i+2}$ is not marked with $*$ is at most $3 \cdot (20-14) = 18$. Consequently, there exists an $i$ for which all of $B_i, B_{i+1}, B_{i+2}$ are marked with $*$. Since this situation cannot occur by the condition of the problem, we conclude that the number of vertices marked with $*$ belonging to the group $r$ is at most $13$. Thus, there are at most $13 \cdot 6 = 78$ vertices of regular $120$-gon marked with $*$.

On the other hand, suppose that for every pair $r, i$ chosen from $78$ combinations formed when $r$ is one of $1, 2, 3, 4, 5, 6$ and $i$ is one of $1, 2, 4, 5, 7, 8, 10, 11, 13, 14, 16, 17, 19$, the vertex $A_{54i+r}$ is marked with $*$. Then, there exists no bad triangle formed by vertices marked with $*$ belonging to the same group. Since the triplet $X, Y, Z$ of vertices must always belong to the same group if the triple $(X, Y, Z)$ is a bad triangle, we conclude that the conditions of the problem are satisfied for all of the $78$ pairs $r, i$ considered above. Therefore, the answer we seek is $78$.