MathDB
Labelling edges of a complete graph - maximal # of labels?

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

December 29, 2006
functionIMO Shortlistgraph theorycombinatoricsExtremal combinatorics

Problem Statement

Let n≥3n\geq 3 be a fixed integer. Each side and each diagonal of a regular nn-gon is labelled with a number from the set {1;  2;  ...;  r}\left\{1;\;2;\;...;\;r\right\} in a way such that the following two conditions are fulfilled:
1. Each number from the set {1;  2;  ...;  r}\left\{1;\;2;\;...;\;r\right\} occurs at least once as a label.
2. In each triangle formed by three vertices of the nn-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 rr for which such a labelling is possible.
(b) Harder version (IMO Shortlist 2005): For this maximal value of rr, 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 rr, there are exactly n!(n−1)!2n−1\frac{n!\left(n-1\right)!}{2^{n-1}} possible labellings.
Proposed by Federico Ardila, Colombia
Back to ProblemsView on AoPS