Art of Problem Solving
AoPS Online
Math texts, online classes, and more
for students in grades 5-12.
Visit AoPS Online ‚
Books for Grades 5-12 Online Courses
Beast Academy
Engaging math books and online learning
for students ages 6-13.
Visit Beast Academy ‚
Books for Ages 6-13 Beast Academy Online
AoPS Academy
Small live classes for advanced math
and language arts learners in grades 2-12.
Visit AoPS Academy ‚
Find a Physical Campus Visit the Virtual Campus

Difference between revisions of "1973 IMO Problems/Problem 4"
 
(5 intermediate revisions by the same user not shown)
Line 44: Line 44:
  
 
Below I will first point out the shortcomings of the solution.
 
Below I will first point out the shortcomings of the solution.
−
Then I will attempt to give a solution.  In fact, I don't
+
Then I will give a complete solution.
−
have a solution, but I will argue (along the lines of the
 
−
solution above, but filling in many details, and correcting
 
−
others) that the path described above is most likely minimal.
 
−
I will highlight the points where my attempted solution fails
 
−
to be rigorous.
 
  
 
1. The author states: "The path that is the solution to this
 
1. The author states: "The path that is the solution to this
Line 60: Line 55:
 
construction: take <math>P</math> on the arc of <math>\mathcal{C}_2</math> inside
 
construction: take <math>P</math> on the arc of <math>\mathcal{C}_2</math> inside
 
the triangle, and take the point <math>R</math> where <math>PB</math> intersects
 
the triangle, and take the point <math>R</math> where <math>PB</math> intersects
−
<math>\mathcal{C}_1</math> (<math>PR</math> is the normal from <math>P</math> to <math>\mathcal{C}_1</math>).
+
<math>\mathcal{C}_1</math>. He shows that the length of the curve <math>APR</math>
−
He shows that the length of the curve <math>APR</math> is minimal when
+
is minimal when <math>P = E</math>, where <math>E</math> is the midpoint of the
−
<math>P = E</math>, where <math>E</math> is the midpoint of the arch (also, the
+
height from <math>C</math>.
−
intersection of the arc with the height from <math>C</math>, and also,
 
−
the midpoint of the parallel <math>D_aD_b</math> to <math>AB</math>, going through
 
−
the midpoints <math>D_a, D_b</math> of <math>BC, AC</math>).  (Denote by <math>F</math> the
 
−
point <math>R</math> when <math>P = E</math>.)
 
  
 
Then, the author argues that the union of circles of radius
 
Then, the author argues that the union of circles of radius
Line 96: Line 87:
 
this is not what we need in order to conclude that the union
 
this is not what we need in order to conclude that the union
 
of circles of radius <math>\frac{h}{2}</math> centered at all the points
 
of circles of radius <math>\frac{h}{2}</math> centered at all the points
−
along <math>AEF</math> covers the triangle.
+
along <math>AEF</math> covers the triangle.  And it is hard to believe
 +
that something that involves only <math>AB</math> would be sufficient
 +
to conclude what we need.
  
  
−
==Solution (attempted)==
+
==Solution==
  
−
Let us say that a curve has the property <math>\mathcal{P}</math> if the
+
Let us say that a curve has the property <math>\mathcal{P}</math> if one end
−
union of circles of radius <math>\frac{h}{2}</math> centered at all the
+
of it is at <math>A</math>, it is inside the triangle, and the union of circles
−
points along the curve covers the triangle.  The problem asks
+
of radius <math>\frac{h}{2}</math> centered at all the points along the curve
−
us to find the shortest curve with one end at <math>A</math> satisfying
+
covers the triangle.  Let <math>\mathcal{S}</math> be the set of curves having
−
<math>\mathcal{P}</math>.
+
property <math>\mathcal{P}</math>.  The problem asks us to find the shortest
 +
curve in <math>\mathcal{S}</math>.
  
−
In this attempted solution when we say that a point is in a
+
In this solution when we say that a point is in a region, we mean
−
region, we mean that the point is in the interior, or on the
+
that the point is in the interior, or on the boundary of the region.
−
boundary of the region.
+
Also, note that we will use the words curve and path interchangeably.
  
 +
Let <math>\mathcal{C}_1</math> and <math>\mathcal{C}_2</math> be the circles of radius
 +
<math>\frac{h}{2}</math> centered at <math>B, C</math>.  Let us say that a curve has the
 +
property <math>\mathcal{P}'</math> if one end of it is at <math>A</math>, it is inside
 +
the triangle, it has a point in the sector of <math>\mathcal{C}_2</math>
 +
inside the triangle, and it has a point in the sector of <math>\mathcal{C}_1</math>
 +
inside the triangle.  Let <math>\mathcal{S}'</math> be the set of curves having
 +
property <math>\mathcal{P}'</math>.
  
 +
We have <math>\mathcal{S} \subset \mathcal{S}'</math>, in other words, if a path
 +
has property <math>\mathcal{P}</math>, then it has property <math>\mathcal{P}'</math>.  Indeed,
 +
if the union of circles of radius <math>\frac{h}{2}</math> centered at all the
 +
points along the path covers the triangle, then this set must cover
 +
<math>B</math> and <math>C</math>, so there must be points on the path at distance
 +
<math>\le \frac{h}{2}</math> from <math>B</math> and <math>C.</math>  These points will be inside the
 +
sectors delimited by the triangle and <math>\mathcal{C}_1, \mathcal{C}_2</math>.
  
 +
The plan of this solution is the following:  We will find the shortest
 +
path in <math>\mathcal{S}'</math>.  (There are two of them, symmetric to each
 +
other.)  If we show that this path is in <math>\mathcal{S}</math>, then it
 +
follows that it is the shortest path in <math>\mathcal{S}</math>.  We will
 +
verify that the path we found does indeed have property <math>\mathcal{P}</math>.
  
 +
Let us proceed by taking a path <math>p \in \mathcal{S}'</math>.  Let one end
 +
(the "beginning") be at <math>A</math>, and denote <math>T</math> the other end of the
 +
path.  Let <math>P</math> and <math>R</math> be points on the curve inside the sectors
 +
of <math>\mathcal{C}_2, \mathcal{C}_1</math>.  We can assume that <math>P \in p</math>
 +
comes "before" the intersection of <math>p</math> with  <math>\mathcal{C}_1</math>.
  
 +
(Note: if it is the other way, we can just change the notation, or
 +
adjust the proof which follows below.  This is where we build one
 +
of the two solutions, the second solution being a symmetrical
 +
transformation of the first.)
  
−
TO BE CONTINUED.
+
Let <math>R \in p \cap \mathcal{C}_1</math> be the "first" point of <math>p</math> where
 +
it meets <math>\mathcal{C}_1</math>.  Define the path <math>p_1</math> to be identical
 +
with <math>p</math> up to the point <math>R</math>, but then we cut off the rest of the
 +
path <math>p</math> (from <math>R</math> to the end <math>T</math>).  In other words, the new end
 +
point <math>T</math> of <math>p_1</math> is <math>T = R</math>.
  
 +
Now let <math>P \in p_1 \cap \mathcal{C}_2</math> be the "first" point of <math>p_1</math>
 +
where it meets <math>\mathcal{C}_2</math>.  The points in <math>p_1</math> are now the
 +
starting point <math>A</math>, followed by a set of points inside the triangle,
 +
outside of <math>\mathcal{C}_2, \mathcal{C}_1</math>, then <math>P</math> on <math>\mathcal{C}_2</math>,
 +
then a set of points which could be inside or outside of <math>\mathcal{C}_2</math>,
 +
and finally <math>R = T</math> on the circle <math>\mathcal{C}_1</math>.
  
−
{{alternate solutions}}
+
Let <math>p_2</math> be the curve in which we replace the portion of <math>p_1</math> from
 +
<math>A</math> to <math>P</math> by a segment on a straight line.  Clearly <math>p_2</math> is shorter
 +
than <math>p_1</math>.
 +
 
 +
Let <math>p_3</math> be the curve in which we replace the portion of <math>p_2</math> from
 +
<math>P</math> to <math>R</math> by a segment on a straight line.  Clearly <math>p_3</math> is shorter
 +
than <math>p_2</math>.  Note that <math>p_3</math> consists of the two segments <math>AP</math>, <math>PR</math>.
 +
 
 +
Let <math>p_4</math> be the curve identical to <math>p_3</math> from <math>A</math> to <math>P</math>, but which
 +
replaces the segment <math>PR</math> by a segment <math>PR'</math> along the normal from
 +
<math>P</math> to <math>\mathcal{C}_1</math>, where <math>R' \in \mathcal{C}_1</math> is the
 +
intersection of the normal with the circle.  (Note that the normal
 +
from <math>P</math> to <math>\mathcal{C}_1</math> is <math>PB</math>.)  Clearly <math>p_4</math> is shorter
 +
than <math>p_3</math>.
 +
 
 +
For the sake of ease of notation let us re-label <math>R'</math> to be <math>R</math>.
 +
Now we are looking at curves which consist of the segment <math>AP</math> (<math>P</math>
 +
being a point on <math>\mathcal{C}_2</math>) followed by the segment <math>PR</math>, where
 +
<math>R \in \mathcal{C}_1</math> is the foot of the normal from <math>P</math> to
 +
<math>\mathcal{C}_1</math>.  See the figure below.
 +
 
 +
[[File:prob_1973_4.png|800px]]
 +
 
 +
Now, we can proceed as in the previous "solution".  We will show
 +
that <math>APR</math> is shortest when <math>P = E</math>, where <math>E</math> is the midpoint of
 +
the arc of <math>\mathcal{C}_2</math> inside the triangle.  (It is also the
 +
intersection of the arc with the height from <math>C</math>, and it is also
 +
the midpoint of the height from <math>C</math>, and it is also the midpoint
 +
of the parallel <math>D_aD_b</math> to <math>AB</math>, going through the midpoints
 +
<math>D_a, D_b</math> of <math>BC, AC</math>).  Denote by <math>F</math> the point corresponding
 +
to <math>R</math> when <math>P = E</math>, that is <math>F \in \mathcal{C}_1</math> is the
 +
intersection of the arc with <math>EB</math>, or the foot of the normal
 +
from <math>E</math> to <math>\mathcal{C}_1</math>.
 +
 
 +
(Note: we could denote <math>\alpha = \angle PCB</math>, use coordinates and
 +
a little trigonometry to calculate the length of <math>APR = AP + PR</math>
 +
in terms of <math>\alpha</math> and <math>a =</math> the side of the triangle, and then
 +
use calculus to find <math>\alpha \in \left[ 0, \frac{\pi}{3} \right]</math>
 +
at which this function achieves its minimum.  The result would be
 +
<math>\alpha = \frac{\pi}{6}</math>.  But it is simpler to use a little
 +
geometry to show that <math>APR</math> is minimum when <math>P = E</math>.)
 +
 
 +
We want to prove that <math>AE + EF \le AP + PR</math>.  Clearly it is enough
 +
to prove <math>AE + EB \le AP + PB</math>.  Let <math>B'</math> by the point symetrical
 +
to <math>B</math> with respect to the line <math>\mathcal{L} = D_aD_b</math>.  Let
 +
<math>Q = AP \cap \mathcal{L}</math>.  We have
 +
<math>AE + EB = AE + EB' \le AQ + QB' = AQ + QB \le AQ + QP + PB = AP + PB</math>.
 +
 
 +
This ends the proof that <math>AEF</math> is the shortest path in <math>\mathcal{S}'</math>
 +
(up to a symmetry).  Now we will show that <math>AEF \in \mathcal{S}</math>, i.e.
 +
<math>AEF</math> has property <math>\mathcal{P}</math>.
 +
 
 +
In order for a curve <math>p</math> to have property <math>\mathcal{P}</math> it is sufficient
 +
to know that there is a portion of <math>p</math> inside the trapezoid <math>BCD_bD_c</math>
 +
which joins a point from the sector of <math>\mathcal{C}_1</math> inside the triangle
 +
to a point from the sector of <math>\mathcal{C}_2</math> inside the triangle, and
 +
similarly for the trapezoids <math>ABD_aD_b</math> and arcs <math>\mathcal{C}_1, \mathcal{C}</math>,
 +
and <math>ACD_aD_c</math> and arcs <math>\mathcal{C}_2, \mathcal{C}</math>.  Obviously <math>AEF</math>
 +
satisfies these conditions, and this ends the proof.
 +
 
 +
(Note:  It is interesting to note that in general, <math>APR</math> does not have
 +
property <math>\mathcal{P}</math> because a portion of it is outside the trapezoid
 +
<math>ABD_aD_b</math>.  We would have to extend it by another segment <math>RT</math> for <math>APRT</math>
 +
to have the property <math>\mathcal{P}</math>.  If we didn't want to extend <math>RT</math> all
 +
the way to <math>\mathcal{C}</math>, we would need some other sufficient condition
 +
for the curve to satisfy so that it has property <math>\mathcal{P}</math>.)
 +
 
 +
[Solution by pf02, June 2025]
  
  
 
== See Also == {{IMO box|year=1973|num-b=3|num-a=5}}
 
== See Also == {{IMO box|year=1973|num-b=3|num-a=5}}

Latest revision as of 13:35, 1 July 2025

Problem

A soldier needs to check on the presence of mines in a region having the shape of an equilateral triangle. The radius of action of his detector is equal to half the altitude of the triangle. The soldier leaves from one vertex of the triangle. What path shouid he follow in order to travel the least possible distance and still accomplish his mission?


Solution

Let our triangle be $\triangle ABC$, let the midpoint of $AB$ be $D$, and let the midpoint of $CD$ be $E$. Let the height of the triangle be $h$. Draw circles around points $B$ and $C$ with radius $\frac{h}{2}$, and label them $c_1$ and $c_2$. Let the intersection of $BE$ and $c_1$ be $F$.

The path that is the solution to this problem must go from $A$ to a point on $c_2$ to a point on $c_1$. Let us first find the shortest possible path. We will then prove that this path fits the requirements.

The shortest path is in fact the path from $A$ to $E$ to $F$. We will prove this as follows:

Suppose that a different point on $c_2$ is the optimal point to go to. Let this point be $P$. Then, the optimal point on $c_1$ would be the intersection of $BP$ and $c_1$ (let this point be $R$). Let the line through $E$ parallel to $AB$ be $l$, and the intersection of $AP$ and $l$ be $Q$. Then, we have

\[AE + BE < AQ + BQ \leq AQ + QP + BP = AP + BP.\textbf{ (1)}\]

The second inequality is true due to the triangle inequality, and we can prove the first to be true as follows:

Suppose we have a point on $l$, $X$. Reflect $B$ across $l$ to get $B'$. Then, $AX + BX = AX + B'X$, which is obviously minimized at the intersection of the two lines, $E$.

By $\textbf{(1)}$, we have

\[AE + EF = AE + BE - \frac{h}{2} < AP + BP - \frac{h}{2} = AP + PR,\]

and we have proved the claim.

This path easily covers the whole triangle. This is because if you draw a line perpendicular to $AB$ from any point in the triangle, this line will hit the path in a distance less than or equal to $\frac{h}{2}$. We can compute the length of the path to be

\[\left(\sqrt{\frac{7}{3}} - \frac{1}{2}\right)h\] \[= \left(\frac{\sqrt{7}}{2} - \frac{\sqrt{3}}{4}\right)\cdot\textrm{the side length of the triangle. }\square\]

~mathboy100


Remarks (added by pf02, June 2025)

The solution given above is so incomplete (and incorrect in a few details) that it can not be called a solution.

Below I will first point out the shortcomings of the solution. Then I will give a complete solution.

1. The author states: "The path that is the solution to this problem must go from $A$ to a point on $\mathcal{C}_2$ to a point on $\mathcal{C}_1$." This needs a proof. I believe this to be true (up to a symmetry), but it is the hardest part of the solution.

2. In the solution above, the author makes the following construction: take $P$ on the arc of $\mathcal{C}_2$ inside the triangle, and take the point $R$ where $PB$ intersects $\mathcal{C}_1$. He shows that the length of the curve $APR$ is minimal when $P = E$, where $E$ is the midpoint of the height from $C$.

Then, the author argues that the union of circles of radius $\frac{h}{2}$ centered at all the points along $AEF$ covers the triangle. (In fact, the argument is incorrect, but the fact is true.)

This is all good, but the two statements above do not prove that $AEF$ is the shortest curve such that the union of circles of radius $\frac{h}{2}$ centered at all the points along the curve covers the triangle. In fact, they don't even prove the much easier problem we obtain if we accept that "the path that is the solution to this problem must go from $A$ to a point on $\mathcal{C}_2$ to a point on $\mathcal{C}_1$."

3. The author says

"This path [$AEF$] easily covers the whole triangle. This is because if you draw a line perpendicular to $AB$ from any point in the triangle, this line will hit the path in a distance less than or equal to $\frac{h}{2}$."

In fact it is not true that "if you draw a line perpendicular to $AB$ from any point in the triangle, this line will hit the path in a distance less than or equal to $\frac{h}{2}$." Clearly, there are points $T$ such that a perpendicular from $T$ to $AB$ will not hit the path $AEF$ at all. Besides, this is not what we need in order to conclude that the union of circles of radius $\frac{h}{2}$ centered at all the points along $AEF$ covers the triangle. And it is hard to believe that something that involves only $AB$ would be sufficient to conclude what we need.


Solution

Let us say that a curve has the property $\mathcal{P}$ if one end of it is at $A$, it is inside the triangle, and the union of circles of radius $\frac{h}{2}$ centered at all the points along the curve covers the triangle. Let $\mathcal{S}$ be the set of curves having property $\mathcal{P}$. The problem asks us to find the shortest curve in $\mathcal{S}$.

In this solution when we say that a point is in a region, we mean that the point is in the interior, or on the boundary of the region. Also, note that we will use the words curve and path interchangeably.

Let $\mathcal{C}_1$ and $\mathcal{C}_2$ be the circles of radius $\frac{h}{2}$ centered at $B, C$. Let us say that a curve has the property $\mathcal{P}'$ if one end of it is at $A$, it is inside the triangle, it has a point in the sector of $\mathcal{C}_2$ inside the triangle, and it has a point in the sector of $\mathcal{C}_1$ inside the triangle. Let $\mathcal{S}'$ be the set of curves having property $\mathcal{P}'$.

We have $\mathcal{S} \subset \mathcal{S}'$, in other words, if a path has property $\mathcal{P}$, then it has property $\mathcal{P}'$. Indeed, if the union of circles of radius $\frac{h}{2}$ centered at all the points along the path covers the triangle, then this set must cover $B$ and $C$, so there must be points on the path at distance $\le \frac{h}{2}$ from $B$ and $C.$ These points will be inside the sectors delimited by the triangle and $\mathcal{C}_1, \mathcal{C}_2$.

The plan of this solution is the following: We will find the shortest path in $\mathcal{S}'$. (There are two of them, symmetric to each other.) If we show that this path is in $\mathcal{S}$, then it follows that it is the shortest path in $\mathcal{S}$. We will verify that the path we found does indeed have property $\mathcal{P}$.

Let us proceed by taking a path $p \in \mathcal{S}'$. Let one end (the "beginning") be at $A$, and denote $T$ the other end of the path. Let $P$ and $R$ be points on the curve inside the sectors of $\mathcal{C}_2, \mathcal{C}_1$. We can assume that $P \in p$ comes "before" the intersection of $p$ with $\mathcal{C}_1$.

(Note: if it is the other way, we can just change the notation, or adjust the proof which follows below. This is where we build one of the two solutions, the second solution being a symmetrical transformation of the first.)

Let $R \in p \cap \mathcal{C}_1$ be the "first" point of $p$ where it meets $\mathcal{C}_1$. Define the path $p_1$ to be identical with $p$ up to the point $R$, but then we cut off the rest of the path $p$ (from $R$ to the end $T$). In other words, the new end point $T$ of $p_1$ is $T = R$.

Now let $P \in p_1 \cap \mathcal{C}_2$ be the "first" point of $p_1$ where it meets $\mathcal{C}_2$. The points in $p_1$ are now the starting point $A$, followed by a set of points inside the triangle, outside of $\mathcal{C}_2, \mathcal{C}_1$, then $P$ on $\mathcal{C}_2$, then a set of points which could be inside or outside of $\mathcal{C}_2$, and finally $R = T$ on the circle $\mathcal{C}_1$.

Let $p_2$ be the curve in which we replace the portion of $p_1$ from $A$ to $P$ by a segment on a straight line. Clearly $p_2$ is shorter than $p_1$.

Let $p_3$ be the curve in which we replace the portion of $p_2$ from $P$ to $R$ by a segment on a straight line. Clearly $p_3$ is shorter than $p_2$. Note that $p_3$ consists of the two segments $AP$, $PR$.

Let $p_4$ be the curve identical to $p_3$ from $A$ to $P$, but which replaces the segment $PR$ by a segment $PR'$ along the normal from $P$ to $\mathcal{C}_1$, where $R' \in \mathcal{C}_1$ is the intersection of the normal with the circle. (Note that the normal from $P$ to $\mathcal{C}_1$ is $PB$.) Clearly $p_4$ is shorter than $p_3$.

For the sake of ease of notation let us re-label $R'$ to be $R$. Now we are looking at curves which consist of the segment $AP$ ($P$ being a point on $\mathcal{C}_2$) followed by the segment $PR$, where $R \in \mathcal{C}_1$ is the foot of the normal from $P$ to $\mathcal{C}_1$. See the figure below.

Prob 1973 4.png

Now, we can proceed as in the previous "solution". We will show that $APR$ is shortest when $P = E$, where $E$ is the midpoint of the arc of $\mathcal{C}_2$ inside the triangle. (It is also the intersection of the arc with the height from $C$, and it is also the midpoint of the height from $C$, and it is also the midpoint of the parallel $D_aD_b$ to $AB$, going through the midpoints $D_a, D_b$ of $BC, AC$). Denote by $F$ the point corresponding to $R$ when $P = E$, that is $F \in \mathcal{C}_1$ is the intersection of the arc with $EB$, or the foot of the normal from $E$ to $\mathcal{C}_1$.

(Note: we could denote $\alpha = \angle PCB$, use coordinates and a little trigonometry to calculate the length of $APR = AP + PR$ in terms of $\alpha$ and $a =$ the side of the triangle, and then use calculus to find $\alpha \in \left[ 0, \frac{\pi}{3} \right]$ at which this function achieves its minimum. The result would be $\alpha = \frac{\pi}{6}$. But it is simpler to use a little geometry to show that $APR$ is minimum when $P = E$.)

We want to prove that $AE + EF \le AP + PR$. Clearly it is enough to prove $AE + EB \le AP + PB$. Let $B'$ by the point symetrical to $B$ with respect to the line $\mathcal{L} = D_aD_b$. Let $Q = AP \cap \mathcal{L}$. We have $AE + EB = AE + EB' \le AQ + QB' = AQ + QB \le AQ + QP + PB = AP + PB$.

This ends the proof that $AEF$ is the shortest path in $\mathcal{S}'$ (up to a symmetry). Now we will show that $AEF \in \mathcal{S}$, i.e. $AEF$ has property $\mathcal{P}$.

In order for a curve $p$ to have property $\mathcal{P}$ it is sufficient to know that there is a portion of $p$ inside the trapezoid $BCD_bD_c$ which joins a point from the sector of $\mathcal{C}_1$ inside the triangle to a point from the sector of $\mathcal{C}_2$ inside the triangle, and similarly for the trapezoids $ABD_aD_b$ and arcs $\mathcal{C}_1, \mathcal{C}$, and $ACD_aD_c$ and arcs $\mathcal{C}_2, \mathcal{C}$. Obviously $AEF$ satisfies these conditions, and this ends the proof.

(Note: It is interesting to note that in general, $APR$ does not have property $\mathcal{P}$ because a portion of it is outside the trapezoid $ABD_aD_b$. We would have to extend it by another segment $RT$ for $APRT$ to have the property $\mathcal{P}$. If we didn't want to extend $RT$ all the way to $\mathcal{C}$, we would need some other sufficient condition for the curve to satisfy so that it has property $\mathcal{P}$.)

[Solution by pf02, June 2025]


See Also

1973 IMO (Problems) • Resources
Preceded by
Problem 3 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 5
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1973_IMO_Problems/Problem_4&oldid=252997"