6th Chinese 1991 Problem A3 10 points are arranged in the plane, so that given any 5, at least 4 lie on a circle. M is the maximum number of points on a circle. What is the minimum possible value of M? Solution
: 9. It is obvious that 9 is achievable - just take any 9 points on a circle and a tenth not on the circle. So we have to prove that at least 9 points must lie on a circle. The first step is to prove that at least 5 of the points lie on a circle. If every 4 points lie on a circle, then take C to be the circle through 4 points A, B, C, D. Now for any other point P, we have that A, B, C, P lie on a circle, which must be C, so all ten points lie on C. So we may assume that there is no circle through some 4 points. There are 4 circles through 3 of these 4 points. All the other 6 points P must lie on at least one of these circles (since a circle through four of the 4 points and P must contain P). So at least 2 of them must lie on one of these circles, which therefore contains 5 of the 10 points. Take these 5 points to be A, B, C, D, E and the circle through them to be C 1 . It is sufficient to prove that given any other two points F and G, at least one of them must lie on C 1 . So suppose F and G do not lie on it. Then F and G and two of A, B, C must lie on a circle C 2 . Similarly, F and G and two of A, C, E must lie on a circle C 3 and F and G and two of B, D, E must lie on a circle C 4 . But 6 points chosen from A, B, C, D, E now lie on the three circles C 2 , C 3 and C 4 , so at least one must lie on two of them. Since F and G lie on all three, that means the two circles must be identical. But that means that at least three points from A, B, C, D, E must lie on it and hence it must be identical with C 1 , so F and G lie on C 1 . Contradiction. 6th Chinese 1991 © John Scholes jscholes@kalva.demon.co.uk 1 May 2002