Problem

Source: IMO Shortlist 2005 Combinatorics problem C4; 5th German TST 2006, 23 April 2006, problem 1

Tags: function, IMO Shortlist, graph theory, combinatorics, Extremal combinatorics



Let $n\geq 3$ be a fixed integer. Each side and each diagonal of a regular $n$-gon is labelled with a number from the set $\left\{1;\;2;\;...;\;r\right\}$ in a way such that the following two conditions are fulfilled: 1. Each number from the set $\left\{1;\;2;\;...;\;r\right\}$ occurs at least once as a label. 2. In each triangle formed by three vertices of the $n$-gon, two of the sides are labelled with the same number, and this number is greater than the label of the third side. (a) Find the maximal $r$ for which such a labelling is possible. (b) Harder version (IMO Shortlist 2005): For this maximal value of $r$, how many such labellings are there?

HIDE: Easier version (5th German TST 2006) - contains answer to the harder version Easier version (5th German TST 2006): Show that, for this maximal value of $r$, there are exactly $\frac{n!\left(n-1\right)!}{2^{n-1}}$ possible labellings.

Proposed by Federico Ardila, Colombia