Middle European Mathematical Olympiad 2009 Problem I-2

Suppose that we have $n \geqslant 3$ distinct colours. Let $f(n)$ be the greatest integer with the property that every side and every diagonal of a convex polygon with $f(n)$ vertices can be coloured with one of $n$ colours in the following way:

• at least two distinct colours are used, and

• any three vertices of the polygon determine either three segments of the same colour or of three different colours.

Show that $f(n) \leqslant (n - 1)^2$ with equality for infinitely many values of $n$.