China Mathematical Olympiad

We claim that the least positive integer $n$ is $17$.

Firstly we prove that $n=17$ has the required property. By contradiction, assume that we have a painting pattern with three colors for the regular $17$-gon such that any group of $4$ vertices of the same color cannot constitute an isogonal trapezoid.

As $\lfloor \frac{17}{3}\rfloor +1=6$, there exists a group of $6$ vertices of the same color, say yellow. Connecting these vertices one another with lines, we get $\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$ segments. Since the lengths of the segments have at most $\lfloor \frac{17}{2}\rfloor =8$ variations, one of the following two cases must exist:

(a) There is a group of three segments with the same length. Since $3\nmid 7$, not every pair of the segments in the group has a common vertex. So there are two segments in the group which have no common vertex. The four vertices of the two segments constitute an isogonal trapezoid, and this is a contradiction.

(b) There are $7$ pairs of segments with the same length. Then each pair must have a common vertex for its segments. Otherwise, the $4$ vertices of the segments in a pair with no common vertex will constitute an isogonal trapezoid. On the other hand, by the pigeonhole principle, we know that there are two pairs which share the same vertex as their segments' common vertex. Then another four vertices of the segments in these two pairs constitute an isogonal trapezoid. This leads to a contradiction again. So $n=17$ has the required property.

Next we will construct painting patterns for $n\le 16$, which do not have the required property. Define $A_1,A_2,\dots ,A_n$ as the vertices of a regular $n$-gon (ordered in clockwise), and $M_1,M_2,M_3$ as the sets of vertices with the same color — red, yellow and blue respectively.

When $n=16$, let $$M_1=\{A_5,A_8,A_{13},A_{14},A_{16}\},$$ $$M_2=\{A_3,A_6,A_7,A_{11},A_{15}\},$$ $$M_3=\{A_1,A_2,A_4,A_9,A_{10},A_{12}\}.$$ In $M_1$, it is easy to check that the distances from $A_{14}$ to the other $4$ vertices are different from each other, and the latter $4$ vertices constitute a rectangle, not an isogonal trapezoid. Similarly, no $4$ vertices in $M_2$ constitute an isogonal trapezoid either. As to $M_3$, the $6$ vertices in it are just vertices of three diameters. So any group of four vertices that constitutes either a rectangle or a $4$-gon with its sides of different lengths.

When $n=15$, let $$M_1=\{A_1,A_2,A_3,A_5,A_8\},$$ $$M_2=\{A_6,A_9,A_{13},A_{14},A_{15}\},$$ $$M_3=\{A_4,A_7,A_{10},A_{11},A_{12}\}.$$ It is easy to check that no four vertices in each $M_i$ ($i=1,2,3$) constitute an isogonal trapezoid.

When $n=14$, let $$M_1=\{A_1,A_3,A_8,A_{10},A_{14}\},$$ $$M_2=\{A_4,A_5,A_7,A_{11},A_{12}\},$$ $$M_3=\{A_2,A_6,A_9,A_{13}\}.$$ This can be verified easily.

When $n=13$, let $$M_1=\{A_5,A_6,A_7,A_{10}\},$$ $$M_2=\{A_1,A_8,A_{11},A_{12}\},$$ $$M_3=\{A_2,A_3,A_4,A_9,A_{13}\}.$$ This can be easily verified too. As in this case, we drop $A_{13}$ from $M_3$, then we arrive at the case for $n=12$; further drop $A_{12}$, we have the case $n=11$; and further drop $A_{11}$, we get the case $n=10$.

When $n\le 9$, we can construct a painting pattern such that $|M_i|<4$ ($i=1,2,3$), to ensure that no four vertices of the same color constitute an isogonal trapezoid.

By now, we have checked all the cases for $n\le 16$. This completes the proof that $17$ is the least value for $n$ to have the required property.