Colour the edges of a polygon
Source: MEMO 2009, problem 2, single competition
October 1, 2009
geometrygeometric transformationcombinatorics proposedcombinatorics
Problem Statement
Suppose that we have distinct colours. Let be the greatest integer with the property that every side and every diagonal of a convex polygon with vertices can be coloured with one of colours in the following way:
(i) At least two colours are used,
(ii) any three vertices of the polygon determine either three segments of the same colour or of three different colours.
Show that f(n) \le (n\minus{}1)^2 with equality for infintely many values of .