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

**Solution**

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

Clearly S_{n} has 2^{n-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 S_{k} has 3 collinear points. They cannot all be in S_{k-1}. Nor can they all be in T_{k-1}, because then the corresponding points in S_{k-1} would also be collinear. So we may assume that P is in S_{k-1} and Q in T_{k-1}. But now if R is in S_{k-1}, then the gradient of PQ exceeds that of PR. Contradiction. Similarly, if R is in T_{k-1}, then the gradient of QR equals that of the two corresponding points in S_{k-1} and is therefore less than that of PQ. Contradiction.

Finally, we have to show that S_{n} does not contain a convex 2n-gon. Suppose it does. Let k be the smallest n such that S_{k} 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 ∈ S_{k-1}, Q &isin T_{k-1}, otherwise all vertices would be in S_{k-1} or all vertices would be in T_{k-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=P_{0}, P_{1}, ... , P_{k}=Q, in order of increasing x-coordinate. These points must form a convex polygon, so grad P_{i-1}P_{i} < grad P_{i}P_{i+1}. But the greatest gradient must occur as we move from S_{k-1} to T_{k-1}, so all but Q must belong to S_{k-1}. Thus we have k vertices in S_{k-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 S_{2}. Contradiction.

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

© John Scholes

jscholes@kalva.demon.co.uk

18 Sep 2002