Suppose that the vertices of a regular polygon of 20 sides are coloured with three colours - red, blue and green - such that there are exactly three red vertices. Prove that there are three vertices A,B,C of the polygon having the same colour such that triangle ABC is isosceles.
Problem
Source:
Tags: combinatorics, polygon
12.02.2014 11:27
Suppose we number the vertices of the regular 20-gon S={a1,b1,c1,d1,a2,b2,c2,d2,...,a5,b5,c5,d5}. Consider the vertices S1={a1,a2,a3,a4,a5}, S2={b1,b2,b3,b4,b5}, S3={c1,c2,c3,c4,c5} and S4={d1,d2,d3,d4,d5}. The four sets of vertices form four regular pentagons. Since three points are coloured red, at least one of the four sets has no red vertex by pigeon hole principle. Suppose the set S1={a1,a2,a3,a4,a5} has no red vertex and every vertex in this set is coloured using either blue or green. By pigeon hole principle, at least one of the two colours should appear at least thrice in the set. Suppose the colour blue appears at least thrice. It is easy to verify that every triangle in a pentagon is isosceles. Hence, we have a blue isosceles triangle.
20.11.2015 22:28
Since there are exactly three red vertices, among the remaining 17 vertices there are nine of them of the same colour, sayblue. We can divide the vertices of the regular 20-gon into four disjoint sets such that each set consists of vertices that form a regular pentagon. Since there are nine blue points, at least one of these sets will have three bluepoints. Since any three points on a pentagon form an isosceles triangle, the statement follows
13.09.2020 04:51
In fact, the problem is still true without the constraint of ≤3 red vertices. My only proof of this right now is a computer search, so I would be interested in seeing a combinatorial proof. The problem without the red vertices restriction essentially boils down to showing that any 3-coloring of Z/20Z admits a 3-AP. This is closely related to the cyclic van der Waerden numbers from Ramsey theory—indeed, it is equivalent to 20∉G(3,3) where G is defined in Grier (2012). It turns out (via computer search) that G(3,3)={1,…,10,12,14,16,18,24}. I would also be interested in seeing a combinatorial proof of this fact. On the topic of the original problem, I believe there is a counting proof à la 2016 ISL C3. As far as I can tell though, the details are a bit annoying.
12.10.2020 11:22
file:///C:/Users/arjun/OneDrive/0_Arjun/IMO/RMO%20past%20year%20papers/my%20solution,%20RMO%202013-6%20(paper%204).pdf Go to above link to check my solution to the problem. I used greedy algorithm to solve the problem (Though, I agree that the official solution was much more elegant).