3
$\begingroup$

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:

  1. There is a limiting triangle(s) that is right or obtuse
  2. 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$.

enter image description here

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).

enter image description here

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.

enter image description here

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.

$\endgroup$
1
$\begingroup$

HINT: Consider the unit disks with centers at these points. Any three of them intersect. Now use Helly's theorem.

$\endgroup$
  • $\begingroup$ Thanks - I suspected there was an easier approach. Mine would not even have "scaled" to $\mathbb{R}^3$. $\endgroup$ – Marconius Aug 16 '15 at 2:03
  • $\begingroup$ No worries.,, Indeed, it scales OK. .With this result you can show that any set of diameter $d$ can be covered with a disk of radius $\frac{\sqrt{3}}{2} \cdot d $ since it works for triangles of diameter $d$. $\endgroup$ – Orest Bucicovschi Aug 16 '15 at 2:27
1
$\begingroup$

A set $S$ of marked points can be covered by a unit disk, centered at $p$ if and only if $p$ is in the intersection of all theunit disks centered at the points of $S$. So your question is equivalent to: Given some unit disks in the plane, if every three have a point in common, then all of them have a point in common. Since unit disks are convex, this is a special case of Helly's theorem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.