IMO 1994 SL C7

Origin: BRA | Category: Combinatorics

Problem

Prove that for any integer n \geq2, there exists a set of 2n−1 points in the plane such that no 3 lie on a line and no 2n are the vertices of a convex 2n-gon.

Solution

Define Sn recursively as follows: Let S2 = {(0, 0), (1, 1)} and Sn+1 = Sn \cupTn, where Tn = {(x + 2n−1, y + Mn) | (x, y) \inSn}, with Mn chosen large enough so that the entire set Tn lies above every line passing through two points of Sn. By definition, Sn has exactly 2n−1 points and contains no three collinear points. We claim that no 2n points of this set are the vertices of a convex 2n-gon. Consider an arbitrary convex polygon P with vertices in Sn. Join by a diagonal d the two vertices of P having the smallest and greatest x- coordinates. This diagonal divides P into two convex polygons P1, P2, the former lying above d. We shall show by induction that both P1, P2 have at most n vertices. Assume to the contrary that P1 has at least n+1 vertices A1(x1, y1), . . . , An+1(xn+1, yn+1) in Sn, with x1 < \cdot \cdot \cdot < xn+1. It follows that y2−y1 x2−x1 > \cdot \cdot \cdot > yn+1−yn xn+1−xn . By the induction hypothesis, not more than n −1 of these vertices belong to Sn−1 or Tn−1, so let Ak−1, Ak \inSn−1, Ak+1 \inTn−1. But by the construction of Tn−1, yk+1−yk xk+1−xk > yk−yk−1 xk−xk−1 , which

gives a contradiction. Similarly, P2 has no more than n vertices, and there- fore P itself has at most 2n −2 vertices.