On considère n points P_i dans le plan dont toutes les distances prises 2 à 2 sont différentes entre elles. On dit par convention que P_j est vassal de P_i si P_j a P_i pour point le plus proche. P_i a alors le statut de suzerain. Tous les points sont des vassaux mais tout ou partie d'entre eux peuvent être en même temps des suzerains.
On désigne par P(n) une position des n points pour laquelle le nombre total de suzerains S(n) atteint son minimum s(n). Par exemple pour n = 3, les 3 points sont les sommets d'un triangle quelconque (ni isocèle ni équilatéral). On a s(3) = 2.
Pour n variant de 4 à 13 déterminer s(n) et représenter des positions P(n) correspondant à chacune de ces valeurs.
Trouver la formule donnant s(n) pour n quelconque et en déduire s(2006)

Source : d'après présélection iranienne pour les olympiades de mathématiques

 Solution