IMO shortlist 1994/C7 solution

35th IMO 1994 shortlist

Problem C7

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₂ 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₀, P₁, ... , P_k=Q, in order of increasing x-coordinate. These points must form a convex polygon, so grad P_i-1P_i < grad P_iP_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₂. 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.

35th IMO shortlist 1994