IMO 2000 SL C3

Origin: COL | Category: Combinatorics

Problem

Let n \geq4 be a fixed positive integer. Given a set S = {P1, P2, . . . , Pn} of points in the plane such that no three are collinear and no four concyclic, let at, 1 \leqt \leqn, be the number of circles PiPjPk that contain Pt in their interior, and let m(S) = a1 + a2 + \cdot \cdot \cdot + an. Prove that there exists a positive integer f(n), depending only on n, such that the points of S are the vertices of a convex polygon if and only if m(S) = f(n).

Solution

Clearly m(S) is the number of pairs of point and triangle (Pt, PiPjPk) such that Pt lies inside the circle PiPjPk. Consider any four-element set Sijkl = {Pi, Pj, Pk, Pl}. If the convex hull of Sijkl is the triangle PiPjPk, then we have ai = aj = ak = 0, al = 1. Suppose that the convex hull is

the quadrilateral PiPjPkPl. Since this quadrilateral is not cyclic, we may suppose that \anglePi + \anglePk < 180◦< \anglePj + \anglePl. In this case ai = ak = 0 and aj = al = 1. Therefore m(Sijkl) is 2 if Pi, Pj, Pk, Pl are vertices of a convex quadrilateral, and 1 otherwise. There are
n  four-element subsets Sijkl. If a(S) is the number of such subsets whose points determine a convex quadrilateral, we have m(S) = 2a(S) +

n  −a(S) 

n 

• a(S) \leq2
  n  . Equality holds if and only if every four distinct points of S determine a convex quadrilateral, i.e. if and only if the points of S determine a convex polygon. Hence f(n) = 2
  n  has the desired property.