
Problem 8.3. Let 1998 points be chosen on the plane so that out of any 17 it is possible to choose 11 that lie inside a circle of diameter 1 . Find the smallest number of circles of diameter 2 sufficient to cover all 1998 points.

(We say that a circle covers a certain number of points if all points lie inside the circle or on its outline.)


Solution: Consider a regular hexagon with a side of length 3 . Choose 1998 points as follows: the 6 vertices of the hexagon and 1992 points inside a circle of diameter 1 centred at the centre of the hexagon. It is clear that the above 1998 points satisfy the condition of the problem. Moreover any circle of radius 1 covers at most one of the vertices of the hexagon. Therefore the required number is no less than 7 (in our case: 6 circles for each vertex and a single circle for the remaining points).

Now we shall prove that the required number is no greater than 7 . Arbitrarily choose 8 points and add other 9 , for a total of 17 . It is clear that there is a circle of diameter 1 covering at least 11 of these 17 points. At most 6 points lie outside the circle and therefore at least 2 of the initially chosen 8 points lie inside the circle. The distance between these two points is no greater than 1 . We have proved that among any 8 points there always exist 2 such that the distance between them is no greater than 1 .

Now choose a circle of radius 1 centred in one of the points. If the remaining points lie inside the circle, the required number is 1 and thus no greater than 7. If this is not the case, take another point outside the first circle. If all points lie in the two circles, then the required number is 2 and thus no greater than 7 . Continuing in this way we either obtain no more than 7 circles covering all points or have 7 circles and a point that lies outside all circles. Consider this point and the centres of the chosen circles. There exist 2 points among these 8 such that the distance between them is no greater than 1. But this is impossible because of the way we chose our points.

Together the two parts of the proof demonstrate that the required number is 7 .
