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 n3 be a fixed integer. Each side and each diagonal of a regular n-gon is labelled with a number from the set {1;2;...;r} in a way such that the following two conditions are fulfilled: 1. Each number from the set {1;2;...;r} 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 n!(n1)!2n1 possible labellings.

Proposed by Federico Ardila, Colombia