Maths Olympiad Prep

Library / /14 of 14

Geometry Difficulty 7.4 National olympiad, round 2 Prove it Bulgaria

A set of points in the plane is called good if the distance between any two points in it is at most 11. Let f(n,d)f(n, d) be the largest positive integer such that in any good set of 3n3n points, there is a circle of diameter dd, which contains at least f(n,d)f(n, d) points. Prove that there exists a positive real ϵ\epsilon, such that for all d(1ϵ,1)d \in (1 - \epsilon, 1), the value of f(n,d)f(n, d) does not depend on dd and find that value as a function of nn.
(Kristiyan Vasilev, Konstantin Garov)

Solution

Since m(n,d)m(n, d) is an increasing function of dd and it cannot be larger than 3n3n, clearly it hits a constant when dd approaches 11. Fix some dd, d<1d < 1, it may be very close to 11. Take an equilateral triangle with side length 11 and put inside it 3n3n points — nn points near each of its vertices so that they be at distance less than (1d)/2(1 - d)/2 from the corresponding vertex — see figure 1.

Figure 1

This set of points apparently is a good set. A disk with radius dd cannot cover a point that is near to one vertex and a point near another vertex. That is, the maximum number of points that could be covered with such a disk is nn. This means that m(n,d)nm(n, d) \le n no matter how close to 11 the value of dd is.

We will prove that m(n,d)=nm(n, d) = n when dd is close to 11. To prove this we need to study the good set of points. How close together are its points? Can we claim that all of them lie in disk with some not too large radius? Of course, they lie in a disk with radius 11 since if you take one of the points, the rest are at distance at most 11 from this point. But can we claim that all of them lie in a disk with a smaller radius? Clearly, they may not lie in a disk with radius 1/21/2 — the equilateral triangle with side length 11 is an example that disproves this. Crucial to this problem is the following observation.
Lemma. Any good set can be put inside a disk with radius 13\frac{1}{\sqrt{3}}. That is, any good set can be put inside a circle circumscribed about an equilateral triangle with a side length 11.

The official solution proves it by using Helly's theorem which is instructive. Another method is used here.
Proof. Let XX be a good set. We first show that XX lies in a circle circumscribed about an acute triangle with side lengths less or equal to 11. Take the convex hull of XX and put it inside a circle with some radius. We begin to tighten this circle until it touches 11 and then 22 points of the convex hull. We can tighten the circle further unless these two points lie on its diameter. In this case AA lies in a circle with a diameter at most 11. So, assume we decrease the circle kk until it touches 33 points of XX, say A,B,CA, B, C. If these points are vertices of an acute triangle we are done, so suppose ACB90\angle ACB \ge 90^\circ — see figure 2. We begin to further decrease the diameter of kk keeping the points AA and BB on the circle. This can be done until the first of the following two events happens:
1. The circle hits a point CXC' \in X (and CC' and CC lie on different sides of ABAB).
2. ABAB becomes a diameter of kk.

Figure 2

If the second event happens first, we are done since XX lies in a disk with diameter 11. In case of the first event, the triangle ABCABC' is acute. Next, since ABC\triangle ABC' is acute one of its angles, say ACB\angle AC'B, is greater or equal to 6060^\circ. It follows the radius of k=AB2sinC13k' = \frac{AB}{2 \sin \angle C} \le \frac{1}{\sqrt{3}}.
So, we proved that we can cover XX with a circle kk with radius 1/31/\sqrt{3}. \square

Take a point AkA \in k and construct the points B,C,DkB, C, D \in k such that AB=BC=CD=dAB = BC = CD = d — see figure 3. We construct three disks with diameters AB,BC,CDAB, BC, CD correspondingly. These disks cover all the points inside kk except the red piece in figure 3. Note now that by taking dd close to 11, the point DD will be as close to AA as we want. This means that we can make the red piece on figure 3 as small as we want. We take dd so close to 11 so that the measure of the arc ADAD (on figure 3) is less than 2π3n+1\frac{2\pi}{3n+1}. If the red piece does not contain a point of XX we are done. Otherwise we begin to rotate the point AA and the entire configuration around kk. It is not possible that every time the red piece hits a point of XX since otherwise the number of points in XX would be more than 3n3n. Therefore we can cover XX with 33 disks of diameter dd, hence one of these disks contains at least nn points. Thus, we proved that m(n,d)nm(n,d) \ge n and combined with m(n,d)nm(n,d) \le n this yields m(n,d)=nm(n,d) = n providing dd is close to 11. \square

Figure 3

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement and solution reproduced as published; topic and difficulty added by this site.