Browse · MathNet
PrintTHE 68th NMO SELECTION TESTS FOR THE BALKAN AND INTERNATIONAL MATHEMATICAL OLYMPIADS
Romania counting and probability
Problem
Let be an odd integer greater than . Each vertex of a regular -gon is coloured one of three colours so that the total number of vertices of each colour is odd. Show that there exists an isosceles triangle whose vertices have pairwise distinct colours.
Solution
Suppose, if possible, no such triangles exist, and consider the parity of the total number of pairs , where is an isosceles triangle, and is an edge of whose endpoints have different colors.
On the one hand, under the above assumption, the vertices of a triangle in a pair form a bichromatic set, so the triangle occurs in exactly two pairs, and the total number of pairs is therefore even.
On the other hand, if we fix an edge whose endpoints have different colors, the number of isosceles triangles matching is either one or three. It is one if is the edge of an equilateral triangle. Otherwise, it is three: one triangle with apex at one endpoint of , another triangle with apex at the other endpoint of , and one more triangle with apex opposite , since is odd. Since the total number of bichromatic edges is odd, so is the total number of pairs, contradicting the parity established in the previous paragraph.
On the one hand, under the above assumption, the vertices of a triangle in a pair form a bichromatic set, so the triangle occurs in exactly two pairs, and the total number of pairs is therefore even.
On the other hand, if we fix an edge whose endpoints have different colors, the number of isosceles triangles matching is either one or three. It is one if is the edge of an equilateral triangle. Otherwise, it is three: one triangle with apex at one endpoint of , another triangle with apex at the other endpoint of , and one more triangle with apex opposite , since is odd. Since the total number of bichromatic edges is odd, so is the total number of pairs, contradicting the parity established in the previous paragraph.
Techniques
Counting two waysColoring schemes, extremal argumentsInvariants / monovariants