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"
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 66: Line 61:
 
the midpoint of the parallel <math>D_aD_b</math> to <math>AB</math>, going through
 
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
 
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>.)
+
point corresponding to <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 99: Line 94:
  
  
−
==Solution (attempted)==
+
==Solution==
 +
 
 +
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, and the union of circles
 +
of radius <math>\frac{h}{2}</math> centered at all the points along the curve
 +
covers the triangle.  Let <math>\mathcal{S}</math> be the set of curves having
 +
property <math>\mathcal{P}</math>.  The problem asks us to find the shortest
 +
curve in <math>\mathcal{S}</math>.
 +
 
 +
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 <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>Q</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.)
 +
 
 +
Let <math>Q \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>Q</math>, but then we cut off the rest of the
 +
path <math>p</math> (from <math>Q</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 = Q</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>Q = T</math> on the circle <math>\mathcal{C}_1</math>.
 +
 
 +
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>Q</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>PQ</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>PQ</math> by a segment <math>PQ'</math> along the normal from
 +
<math>P</math> to <math>\mathcal{C}_2</math>, where <math>Q' \in \mathcal{C}_2</math> is the
 +
intersection of the normal with the circle.  Clearly <math>p_4</math> is shorter
 +
than <math>p_3</math>.
 +
 
 +
For the sake of ease of notation let us re-label <math>Q'</math> to be <math>Q</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>PQ</math>, where
 +
<math>Q \in \mathcal{C}_1</math> is the foot of the normal from <math>P</math> to
 +
<math>\mathcal{C}_1</math> (the normal is in fact the line <math>PB</math>.)  See the
 +
figure below.
 +
 
 +
 
  
−
Let us say that a curve has the property <math>\mathcal{P}</math> if the
 
−
union of circles of radius <math>\frac{h}{2}</math> centered at all the
 
−
points along the curve covers the triangle.  The problem asks
 
−
us to find the shortest curve with one end at <math>A</math> satisfying
 
−
<math>\mathcal{P}</math>.
 
  
−
In this attempted 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.
 
  
  
Line 119: Line 185:
  
  
−
TO BE CONTINUED.
 
  
  
−
{{solution}}
+
TO BE CONTINUED.
  
  
 
== See Also == {{IMO box|year=1973|num-b=3|num-a=5}}
 
== See Also == {{IMO box|year=1973|num-b=3|num-a=5}}

Revision as of 17:30, 30 June 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$ ($PR$ is the normal from $P$ to $\mathcal{C}_1$). He shows that the length of the curve $APR$ is minimal when $P = E$, where $E$ is the midpoint of the arch (also, the intersection of the arc with the height from $C$, and 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$.)

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.


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 $Q$ 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 $Q \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 $Q$, but then we cut off the rest of the path $p$ (from $Q$ to the end $T$). In other words, the new end point $T$ of $p_1$ is $T = Q$.

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 $Q = 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 $Q$ 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$, $PQ$.

Let $p_4$ be the curve identical to $p_3$ from $A$ to $P$, but which replaces the segment $PQ$ by a segment $PQ'$ along the normal from $P$ to $\mathcal{C}_2$, where $Q' \in \mathcal{C}_2$ is the intersection of the normal with the circle. Clearly $p_4$ is shorter than $p_3$.

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








TO BE CONTINUED.


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=252944"