IGO 2017 P4 of Combinatorial Geometry

260 Views Asked by At

The following problem is from IGO 2017 (P4)

$P_1,P_2,\ldots,P_{100}$ are $100$ points on the plane, no three of them are collinear. For each three points, call their triangle clockwise if the increasing order of them is in clockwise order. Can the number of clockwise triangles be exactly $2017$?

-Proposed by Morteza Saghafian

OBSERVATIONS-

  1. It cannot be solved by constructing a plane with these arbitrary points, simply because there are too many.

  2. It is trivial to say that there can be a line join $2$ points such that all other $98$ points lie on the same side of this line. We $might$ use this fact.

  3. We can make an ordered set containing all points in clockwise order. [We can construct such a set - prove by rotating an imaginary line around a pivot which is any point $Pi$ and then changing the pivot to the next point this line intersects and continuing to move it clockwise until it touches all $100$ points]

  4. BEST POINT We can use a strong form of PHP which states that out of mn+1 elements in a sequence there exists a strictly increasing or decreasing subsequence of m+1 consecutive elements (assuming m<n)