A set of points is marked on the plane, with the property that any three marked points can be covered with a disk of radius 1. Prove that the set of all marked points can be covered with a disk of radius 1.
This question is from the 2009 Canada National Olympiad.
I would be grateful for any suggestions on:
- how to prove by an alternative method, e.g. probabalistic
- how to streamline the proof
- how to make the proof more rigorous
Formulation
Prove the worst case where there is at least one limiting triangle that could not be covered if it were scaled up in size by any factor exceeding 1. That is, apply a uniform scaling to the set of points until there is at least one limiting triangle.
The notion of limiting triangle is important because there is then a unique circle that covers the triangle; the circle will not cover the entire triangle if it is translated by any nonzero amount in any direction from the covering position.
We distinguish two cases:
- There is a limiting triangle(s) that is right or obtuse
- All limiting triangle(s) are acute
Case 1: Limiting Triangle is Right or Obtuse
By comparison with a right triangle whose longest side is on the diameter of the covering circle, we see that any triangle with a diametral side will have its other vertex outside the circle if and only if the angle at this vertex is $<90^\circ$, and will have its other vertex on or inside the circle otherwise. So a right or obtuse triangle can be covered by a unit circle if and only if its longest side is $\le 2$ units in length. The longest side is the sole limiting feature of a non-acute triangle.
In the diagram below, $AB$ is the longest side and $\angle ACB = 90^\circ, \angle AC'B > 90^\circ, \angle ADB < 90^\circ$.
Then if any other point (say $D$) is outside the circle with diameter AB, we have a triangle $\Delta ABD$ that cannot be covered by a unit circle (because $AB$ is limiting), which contradicts the original stipulation that any three points forms a triangle that is coverable. Hence, there are no points outside the unit circle with $AB$ diametral.
This proves case 1.
What suggestions for making the above argument more rigorous?
Case 2: Limiting Triangle is Acute
When the limiting triangle is acute, its circumcenter will coincide with the center of the covering circle.
We first need to prove:
Lemma 1: If a triangle is acute and all its vertices lie on a circle, then no larger circle can cover the triangle.
With reference to the diagram below, for an acute triangle the circumcenter is inside the triangle. If the covering circle is translated in a direction that is not aligned with, say, $AB$, then it will need to move in a general direction away from vertex $C$, as indicated by the arrows. It is impossible to satisfy all three sets of requirements (relative to all sides), so the covering circle is unique and the triangle limiting. This argument relies on the circumcenter being inside the triangle, and hence does not work for obtuse triangles (nor should it).
This proves the lemma.
What suggestions for making the above argument more rigorous, or streamlining it?
Now suppose that we have a limiting triangle $\Delta ABC$ and a point $D'$ outside the covering circle for $\Delta ABC$, as per the next diagram. Construct point $D$ as the intersection of $AD'$ with the circle. Then show that a triangle with vertex $D$ is limiting, so that the analogous triangle with vertex $D'$ cannot be covered.
Prove by contradiction. Suppose WLOG that $D\in\text{arc}\stackrel{\Large\frown}{BC}$. Suppose also that perpendiculars to $AB$ and to $AC$ cross at point $G$ inside the circle, and that $D\in\text{arc}\stackrel{\Large\frown}{FE}$ as shown, so that it not possible to find an acute (or right) triangle having $D$ as one vertex and having one of the sides of $\Delta ABC$ as a side.
But in quadrilateral $ABGC$, for one pair of opposite angles $\angle ABG = \angle ACG = 90^\circ$, so $ABGC$ is a cyclic quadrilateral. So point $G$ is on the same circle as points $A,B,C$ thereby showing that points $E,F,G$ coincide.
Hence, it is not possible to have $D\in\text{arc}\stackrel{\Large\frown}{FE}$, so $D$ must form an acute or right triangle with one side of $\Delta ABC$, e.g. if $D\in\text{arc}\stackrel{\Large\frown}{BG}$ we have acute triangle $\Delta ADC$. Then $\Delta ADC$ is limiting, so $\Delta AD'C$ cannot be covered as required. Otherwise, $D\in\text{arc}\stackrel{\Large\frown}{GC}$ and the argument is similar, or points $D$ and $G$ coincide and $\Delta ACD$ is a right triangle, so we then proceed as in Case 1.
This proves Case 2.
