Find the smallest integer $n$ satisfying the following condition: regardless of how one colour the vertices of a regular $n$-gon with either red, yellow or blue, one can always find an isosceles trapezoid whose vertices are of the same colour.
Problem
Source:
Tags: geometry, trapezoid, pigeonhole principle, combinatorics
30.11.2010 09:29
We prove that $n=17$ satisfies the given conditions. By pigeonhole principle, there are 6 vertices of the same colour, say yellow, and 15 edges joining them, call them "yellow edges". There are 8 different lengths of edges. If there are three yellow edges of the same length, we obviously get an isosceles trapezoid. Suppose each length appears at most twice on the yellow edges. So there are seven pairs of yellow edges having the same length. If one of the pairs does not have a common vertex, then we get an isosceles trapezoid. Otherwise, each of the pair of edges have a common vertex. So there is a vertex, say $A$, which becomes a common vertex for two pairs of edges, say $(AA_i,AA_j)$ and $(AA_k,AA_l)$. Thus we get an isosceles trapezoid $A_iA_jA_kA_l$. For $n<17$, we can construct a colouring that does not satisfy the conditions. But it's very tedious.
24.07.2019 23:33
In the original problem statement the isosceles trapezoid must not have two sets of parallel sides.
29.05.2020 10:45
How come the answer is not n=16. Can anyone show me how to construct the coloring?
12.07.2020 22:18
Since post #2 already mentioned how $n=17$ satisfies the conditions, we will now prove that all $n<17$ do not. We will continue to work with the yellow color as defined in post #2. Denote $A_1, A_2, \dots, A_n$ as the vertices of a regular $n-gon$ (in clockwise order) and $M_1, M_2, M_3$ as the sets of vertices with the same color (red, yellow, 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$, we can check that the distances from $A_14$ to the other $4$ vertices are all distinct, and the latter $4$ vertices constitute a rectangle, not an isogonal trapezoid. Similarly, no $4$ vertices in $M_2$ form an isogonal trapezoid either. For $M_3$, the $6$ vertices in it are vertices of #3# diameters, so it is impossible to form a trapezoid. Any group of four vertices will either form a rectangle or a quadrilateral 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$ for $i\in{1,2,3}$ form 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}\}$ Similarly, we can easily verify that they cannot form an isogonal trapezoid. 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 is fairly obvious to check. From $n=13$, we can derive the steps for $n=12, 11, 10$: For $n=12$, we simply remove $A_{13}$ from $M_3$. For $n=11$, we further remove $A_{12}$. For $n=10$, we remove $A_{11}$. When $n\leq 9$, we construct a pattern such that $|M_i|<4$ for $i\in(1,2,3)$ to ensure no four vertices of the same color will constitute an isogonal trapezoid. Q.E.D. *sigh* this was very tedious