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 "1965 IMO Problems/Problem 6"

(bolded username awe-sum)
m
 
(10 intermediate revisions by 2 users not shown)
Line 1: Line 1:
 
== Problem ==
 
== Problem ==
 +
 
In a plane a set of <math>n</math> points (<math>n\geq 3</math>) is given. Each pair of points is connected by a segment. Let <math>d</math> be the length of the longest of these segments. We define a diameter of the set to be any connecting segment of length <math>d</math>. Prove that the number of diameters of the given set is at most <math>n</math>.
 
In a plane a set of <math>n</math> points (<math>n\geq 3</math>) is given. Each pair of points is connected by a segment. Let <math>d</math> be the length of the longest of these segments. We define a diameter of the set to be any connecting segment of length <math>d</math>. Prove that the number of diameters of the given set is at most <math>n</math>.
 +
  
 
== Solution ==
 
== Solution ==
Line 7: Line 9:
  
  
−
{{solution}}
+
== Remarks (added by pf02, October 2024) ==
 +
 
 +
1.  As a public service, I will upload the "Image of problem Solution" mentioned
 +
above to this web page.  That way, a reader can see the "Solution" immediately,
 +
without having to go to another web site, and we are not subjected to the
 +
possibility of the imgur.com website being taken down, or Imgur's parent company
 +
deciding to delete this particular image.  Credits for the image are due to user
 +
'''awe-sum''', as pointed out above.
 +
 
 +
2. This "Solution" is presented very badly, and edited very badly.  Indeed, some
 +
terms are undefined, left to the reader to make sense of (e.g. "incident",
 +
"degree").  But let us be forgiving, and let us do our best to make sense of
 +
the "Solution".
 +
 
 +
3. The "Solution" is incomplete, to the point of not being a solution at all.
 +
There are some serious gaps, which raise questions which are not addressed,
 +
and a reader can not be expected to fill in the details.  These are:
 +
 
 +
a. The author says "... at least one point is incident to at least three diagonals".
 +
But, it could also happen that two points are "incident" to two "diagonals"
 +
(i.e. diameters) each.  The author does not address this possibility at all.
 +
 
 +
b. The author says "consider all points at distance exactly d from point Q (the
 +
green circle).  We see that all of them are outside the locus, the exception
 +
being P."  This is far from obvious.  It assumes that all the other k-4 points
 +
(those points of the k given points which are not highlighted in the picture)
 +
are inside the "locus (the blue shaded region)".  In fact, it seems to this
 +
reader that this is not necessarily true.
 +
 
 +
c. Another issue with this "Solution" is that it assumes <math>n \ge 4</math>, while the
 +
statement of the problem has <math>n \ge 3</math>.  This shortcoming is easy to fix,
 +
unlike the previous two I mentioned.
 +
 
 +
4. I will give a solution below, in the section "Solution 2".
 +
 
 +
 
 +
== Solution (by user '''awe-sum''') ==
 +
 
 +
[[File:problem_1965_6_sol_by_awe-sum.png|900px]]
 +
 
 +
 
 +
== Solution 2 ==
 +
 
 +
<math>\mathbf{Definition:}</math>  For the purpose of this proof, let us define an
 +
<math>equilateral\ arc\ triangle</math> as the shape we obtain when we take a triangle
 +
<math>\triangle ABC</math> in which we replace the side <math>AB</math> by the <math>\pi/6</math> arc of the
 +
circle centered at <math>C</math> with radius <math>CA = CB</math>, going from <math>A</math> to <math>B</math>, and
 +
similarly for the other two sides <math>BC</math> and <math>AC</math>.
 +
 
 +
See the picture below.
 +
 
 +
[[File:prob_1965_6_fig1.png|300px]]
 +
 
 +
Note that if the sides of the original equilateral triangle were of length
 +
<math>d</math>, then the distance from a vertex to any point on the opposite arc is <math>d</math>.
 +
Also, the distance between any two points on the arcs, such that none of them
 +
are vertices is <math>< d</math>.  And finally, the distance from a vertex to any point
 +
on the arcs adjacent to it (which is not another vertex) is <math>< d</math>.
 +
 
 +
<math>\mathbf{Lemma:}</math>  A configuration of <math>n</math> points has exactly <math>n</math> diameters
 +
if an only if <math>3</math> of the points are the vertices of an equilateral arc
 +
triangle, and the other <math>n - 3</math> are on the boundary of the triangle.
 +
 
 +
[[File:prob_1965_6_fig2.png|300px]]
 +
 
 +
In the configuration shown above, we have <math>9</math> points with <math>9</math> diameters.
 +
 
 +
<math>\mathbf{Proof\ of\ the\ Lemma:}</math>  It is clear that if we have a configuration
 +
as described in the lemma then there are <math>n</math> diameters.  We will prove the
 +
converse by induction.  We want to prove that if we have a configuration
 +
of <math>n</math> points with <math>n</math> diameters, then the points are in a configuration
 +
as described above.
 +
 
 +
If <math>n = 3</math> it is clear that the <math>3</math> points have to be the vertices of an
 +
equilateral triangle since the sides are equal (to <math>d</math>).  Assume we know
 +
the statement to be true for <math>n</math>, and prove it for <math>n + 1</math>.  Assume that
 +
we have <math>n + 1</math> points with <math>n + 1</math> diameters <math>d</math>.  Consider <math>n</math> of the
 +
points, and let <math>Q</math> be the remaining point.  It follows from the induction
 +
hypothesis that <math>3</math> of the <math>n</math> are the vertices of an equilateral arc
 +
triangle, and the other <math>n - 3</math> are on the boundary.
 +
 
 +
Now let us examine where <math>Q</math> may be.  It can not be outside of the equilateral
 +
arc triangle because then the distance to at least one of the vertices would
 +
be <math>d' > d</math>, and the diameter of the set would be <math>d'</math> rather than <math>d</math>.  It
 +
can not be inside the triangle because then all the distances from <math>Q</math> to the
 +
<math>n</math> points considered are <math>< d</math>, and we would not have <math>n + 1</math> diameters, as
 +
assumed.  So <math>Q</math> must be on the boundary of the equilateral arc triangle,
 +
which proves the induction step, and the lemma.
 +
 
 +
Now the solution to the problem is easy to finish.  Assume we have <math>n</math> points
 +
given, and the configuration has <math>m</math> diameters.  I claim that we can not have
 +
<math>m > n</math>.  We prove this by contradiction.  If we did, let us consider a set
 +
<math>S</math> consisting of only <math>n</math> of the diameters.  Because of the lemma, this
 +
implies that the <math>n</math> points form a configuration as described in the lemma,
 +
i.e. <math>3</math> of them are the vertices of an equilateral arc triangle, and the
 +
other <math>n - 3</math> are on the boundary.  Now consider a diameter <math>D</math> which is
 +
not in <math>S</math>.  It is the distance of a segment between two of the points
 +
<math>P_1, P_2</math> in the configuration.  If one of <math>P_1, P_2</math> is a vertex, then
 +
this diameter <math>D</math> is in <math>S</math>, which is a contradiction.  If none of
 +
<math>P_1, P_2</math> are vertices, then the length of <math>P_1P_2 < d</math>, so <math>D = P_1P_2</math>
 +
is not a diameter, which is again a contradiction.
 +
 
 +
It follows that <math>m \le n</math> which proves the problem.
 +
 
 +
[Solution by pf02, October 2024]
 +
 
 +
 
 +
== See Also ==
 +
{{IMO box|year=1965|num-b=5|after=Last Question}}

Latest revision as of 18:06, 10 November 2024

Problem

In a plane a set of $n$ points ($n\geq 3$) is given. Each pair of points is connected by a segment. Let $d$ be the length of the longest of these segments. We define a diameter of the set to be any connecting segment of length $d$. Prove that the number of diameters of the given set is at most $n$.


Solution

Image of problem Solution. Credits to user awe-sum.


Remarks (added by pf02, October 2024)

1. As a public service, I will upload the "Image of problem Solution" mentioned above to this web page. That way, a reader can see the "Solution" immediately, without having to go to another web site, and we are not subjected to the possibility of the imgur.com website being taken down, or Imgur's parent company deciding to delete this particular image. Credits for the image are due to user awe-sum, as pointed out above.

2. This "Solution" is presented very badly, and edited very badly. Indeed, some terms are undefined, left to the reader to make sense of (e.g. "incident", "degree"). But let us be forgiving, and let us do our best to make sense of the "Solution".

3. The "Solution" is incomplete, to the point of not being a solution at all. There are some serious gaps, which raise questions which are not addressed, and a reader can not be expected to fill in the details. These are:

a. The author says "... at least one point is incident to at least three diagonals". But, it could also happen that two points are "incident" to two "diagonals" (i.e. diameters) each. The author does not address this possibility at all.

b. The author says "consider all points at distance exactly d from point Q (the green circle). We see that all of them are outside the locus, the exception being P." This is far from obvious. It assumes that all the other k-4 points (those points of the k given points which are not highlighted in the picture) are inside the "locus (the blue shaded region)". In fact, it seems to this reader that this is not necessarily true.

c. Another issue with this "Solution" is that it assumes $n \ge 4$, while the statement of the problem has $n \ge 3$. This shortcoming is easy to fix, unlike the previous two I mentioned.

4. I will give a solution below, in the section "Solution 2".


Solution (by user awe-sum)

Problem 1965 6 sol by awe-sum.png


Solution 2

$\mathbf{Definition:}$ For the purpose of this proof, let us define an $equilateral\ arc\ triangle$ as the shape we obtain when we take a triangle $\triangle ABC$ in which we replace the side $AB$ by the $\pi/6$ arc of the circle centered at $C$ with radius $CA = CB$, going from $A$ to $B$, and similarly for the other two sides $BC$ and $AC$.

See the picture below.

Prob 1965 6 fig1.png

Note that if the sides of the original equilateral triangle were of length $d$, then the distance from a vertex to any point on the opposite arc is $d$. Also, the distance between any two points on the arcs, such that none of them are vertices is $< d$. And finally, the distance from a vertex to any point on the arcs adjacent to it (which is not another vertex) is $< d$.

$\mathbf{Lemma:}$ A configuration of $n$ points has exactly $n$ diameters if an only if $3$ of the points are the vertices of an equilateral arc triangle, and the other $n - 3$ are on the boundary of the triangle.

Prob 1965 6 fig2.png

In the configuration shown above, we have $9$ points with $9$ diameters.

$\mathbf{Proof\ of\ the\ Lemma:}$ It is clear that if we have a configuration as described in the lemma then there are $n$ diameters. We will prove the converse by induction. We want to prove that if we have a configuration of $n$ points with $n$ diameters, then the points are in a configuration as described above.

If $n = 3$ it is clear that the $3$ points have to be the vertices of an equilateral triangle since the sides are equal (to $d$). Assume we know the statement to be true for $n$, and prove it for $n + 1$. Assume that we have $n + 1$ points with $n + 1$ diameters $d$. Consider $n$ of the points, and let $Q$ be the remaining point. It follows from the induction hypothesis that $3$ of the $n$ are the vertices of an equilateral arc triangle, and the other $n - 3$ are on the boundary.

Now let us examine where $Q$ may be. It can not be outside of the equilateral arc triangle because then the distance to at least one of the vertices would be $d' > d$, and the diameter of the set would be $d'$ rather than $d$. It can not be inside the triangle because then all the distances from $Q$ to the $n$ points considered are $< d$, and we would not have $n + 1$ diameters, as assumed. So $Q$ must be on the boundary of the equilateral arc triangle, which proves the induction step, and the lemma.

Now the solution to the problem is easy to finish. Assume we have $n$ points given, and the configuration has $m$ diameters. I claim that we can not have $m > n$. We prove this by contradiction. If we did, let us consider a set $S$ consisting of only $n$ of the diameters. Because of the lemma, this implies that the $n$ points form a configuration as described in the lemma, i.e. $3$ of them are the vertices of an equilateral arc triangle, and the other $n - 3$ are on the boundary. Now consider a diameter $D$ which is not in $S$. It is the distance of a segment between two of the points $P_1, P_2$ in the configuration. If one of $P_1, P_2$ is a vertex, then this diameter $D$ is in $S$, which is a contradiction. If none of $P_1, P_2$ are vertices, then the length of $P_1P_2 < d$, so $D = P_1P_2$ is not a diameter, which is again a contradiction.

It follows that $m \le n$ which proves the problem.

[Solution by pf02, October 2024]


See Also

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