35th IMO 1994 shortlist

Problem C7

n > 2. Show that there is a set of 2n-1 points in the plane, no three collinear such that no 2n form a convex 2n-gon.

Solution

Let S2 be {(0,0), (1,1)}. Given Sn, take Tn = ((x+2n-1,y+Mn)|(x,y) ∈ Sn), where Mn is chosen sufficiently large that the gradient of any segment joining a point of Sn to a point of Tn is greater than that of any segment joining two points of Sn. Then put Sn+1 = Sn ∪ Tn.

Clearly Sn has 2n-1 points. The next step is to show that no three are collinear. Suppose not. Then take k to be the smallest n such that Sk has 3 collinear points. They cannot all be in Sk-1. Nor can they all be in Tk-1, because then the corresponding points in Sk-1 would also be collinear. So we may assume that P is in Sk-1 and Q in Tk-1. But now if R is in Sk-1, then the gradient of PQ exceeds that of PR. Contradiction. Similarly, if R is in Tk-1, then the gradient of QR equals that of the two corresponding points in Sk-1 and is therefore less than that of PQ. Contradiction.

Finally, we have to show that Sn does not contain a convex 2n-gon. Suppose it does. Let k be the smallest n such that Sk contains a convex 2k-gon. Let P be the vertex of the 2k-gon with the smallest x-coordinate and Q be the vertex with the largest. We must have P ∈ Sk-1, Q &isin Tk-1, otherwise all vertices would be in Sk-1 or all vertices would be in Tk-1, contradicting the minimality of k. Now there must be at least k-1 other vertices below the line PQ, or at least k-1 above it. Suppose there are at least k-1 below it. Take them to be P=P0, P1, ... , Pk=Q, in order of increasing x-coordinate. These points must form a convex polygon, so grad Pi-1Pi < grad PiPi+1. But the greatest gradient must occur as we move from Sk-1 to Tk-1, so all but Q must belong to Sk-1. Thus we have k vertices in Sk-1 with increasing x-coordinate and all lying below the line joining the first and the last. We can now repeat the argument. Eventually, we get 3 vertices in S2. Contradiction.

The case were we have k-1 vertices above the line PQ is similar. By convexity, all but P must lie in Tk-1. We now take their translates in Sk-1 and repeat the argument, getting the same contradiction as before.