IMO 1986 SL 11

Origin: BUL

Problem

Let f(n) be the least number of distinct points in the plane such that for each k = 1, 2, . . ., n there exists a straight line containing exactly k of these points. Find an explicit expression for f(n). Simplified version. Show that f(n) = / n+1 0 / n+2 ([x] denoting the great- est integer not exceeding x).

Solution

Let X be a finite set in the plane and lk a line containing exactly k points of X (k = 1, . . . , n). Then ln contains n points, ln−1 contains at least n−2 points not lying on ln, ln−2 contains at least n −4 points not lying on ln or ln−1, etc. It follows that |X| \geqg(n) = n + (n −2) + (n −4) + \cdot \cdot \cdot +
n −2 / n 0 . Hence f(n) \geqg(n) = / n+1 0 / n+2 , where the last equality is easily proved by induction. We claim that f(n) = g(n). To prove this, we shall inductively construct a set Xn of cardinality g(n) with the required property. For n \leq2 a one-point and two-point set satisfy the requirements. Assume that Xn is a set of g(n) points and that lk is a line containing exactly k points of Xn, k = 1, . . . , n. Consider any line l not parallel to any of the lk’s and not containing any point of Xn or any intersection point of the lk. Let l intersect lk in a point Pk, k = 1, . . . , n, and let Pn+1, Pn+2 be two points on l other than P1, . . . , Pn. We define Xn+2 = Xn \cup{P1, . . . , Pn+2}. The set Xn+2 consists of g(n) + (n + 2) = g(n + 2) points. Since the lines l, ln, . . . , l2, l1 meet Xn in n + 2, n + 1, . . . , 3, 2 points respectively (and there clearly exists a line containing only one point of Xn+2), this set also meets the demands.