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 "1971 IMO Problems/Problem 1"
 
(5 intermediate revisions by the same user not shown)
Line 26: Line 26:
 
Then the sum of the first two terms in <math>E_5</math> is
 
Then the sum of the first two terms in <math>E_5</math> is
 
<math>(a_1 - a_2)[(a_1 - a_3)(a_1 - a_4)(a_1 - a_5) - (a_2 - a_3)(a_2 - a_4)(a_2 - a_5)] \ge 0</math>.
 
<math>(a_1 - a_2)[(a_1 - a_3)(a_1 - a_4)(a_1 - a_5) - (a_2 - a_3)(a_2 - a_4)(a_2 - a_5)] \ge 0</math>.
−
The third term is non-negative (the first two factors are non-positive and the last two non-negative).
+
 
−
The sum of the last two terms is:
+
The third term in <math>E_5</math> is non-negative (the first two factors are non-positive and the last two non-negative).
 +
 
 +
The sum of the last two terms in <math>E_5</math> is:
 
<math>(a_4 - a_5)[(a_1 - a_5)(a_2 - a_5)(a_3 - a_5) - (a_1 - a_4)(a_2 - a_4)(a_3 - a_4)] \ge 0</math>.
 
<math>(a_4 - a_5)[(a_1 - a_5)(a_2 - a_5)(a_3 - a_5) - (a_1 - a_4)(a_2 - a_4)(a_3 - a_4)] \ge 0</math>.
 +
 
Hence <math>E_5 \ge 0</math>.
 
Hence <math>E_5 \ge 0</math>.
  
Line 38: Line 41:
 
1. As a public service, I fixed a few typos in the solution above.
 
1. As a public service, I fixed a few typos in the solution above.
  
−
2. To make the solution a little more complete, let us note that
+
2. Make the solution a little more complete:
−
the assumptions <math>a_1 \ge a_2 \ge a_3</math> in case <math>n = 3</math> and
+
 
−
<math>a_1 \ge a_2 \ge a_3 \ge a_4 \ge a_5</math> in case <math>n = 5</math> are perfectly
+
2.1. Let us note that the assumptions <math>a_1 \ge a_2 \ge a_3</math> in case
−
legitimate.  A different ordering of these numbers could be reduced
+
<math>n = 3</math> and <math>a_1 \ge a_2 \ge a_3 \ge a_4 \ge a_5</math> in case <math>n = 5</math>
−
to this case by a simple change of notation: we would substitute
+
are perfectly legitimate.  A different ordering of these numbers
−
<math>a_i</math> by <math>b_j</math> with the indexes for the <math>b</math>'s chosen in such a way
+
could be reduced to this case by a simple change of notation: we
−
that the inequalities above are true for the <math>b</math>'s.
+
would substitute <math>a_i</math> by <math>b_j</math> with the indexes for the <math>b</math>'s chosen
 +
in such a way that the inequalities above are true for the <math>b</math>'s.
  
−
3. Also, the inequality
+
2.2. The inequality
 
<math>(a_1 - a_2)[(a_1 - a_3)(a_1 - a_4)(a_1 - a_5) - (a_2 - a_3)(a_2 - a_4)(a_2 - a_5)] \ge 0</math>
 
<math>(a_1 - a_2)[(a_1 - a_3)(a_1 - a_4)(a_1 - a_5) - (a_2 - a_3)(a_2 - a_4)(a_2 - a_5)] \ge 0</math>
−
is true because <math>a_1 - a_2 \le 0</math>, and
+
is true because <math>a_1 - a_2 \ge 0</math>, and
−
<math>(a_1 - a_3)(a_1 - a_4)(a_1 - a_5) - (a_2 - a_3)(a_2 - a_4)(a_2 - a_5) \le 0</math>.
+
<math>(a_1 - a_3)(a_1 - a_4)(a_1 - a_5) - (a_2 - a_3)(a_2 - a_4)(a_2 - a_5) \ge 0</math>.
−
To see this latter inequality, just notice that <math>a_1 - a_3 \le a_2 - a_3</math>,
+
To see this latter inequality, just notice that <math>a_1 - a_3 \ge a_2 - a_3</math>,
 
and similarly for the other pairs of factors.  The difference of the products
 
and similarly for the other pairs of factors.  The difference of the products
−
is <math>\le 0</math> as desired.
+
is <math>\ge 0</math> as desired.
 +
 
 +
The argument for the sum of the last two terms in <math>E_5</math> is similar.
 +
 
 +
3. The case <math>n = 3</math> is very easy to prove in a different way.  Note
 +
that
 +
 
 +
<math>(a_1 - a_2)(a_1 - a_3) + (a_2 - a_1)(a_2 - a_3) + (a_3 - a_1)(a_3 - a_2) =
 +
\frac{1}{2}[(a_1 - a_2)^2 + (a_2 - a_3)^2 + (a_3 - a_1)^2]</math>
 +
 
 +
I could not find an identity which would give such a simple proof
 +
in the case <math>n = 5</math>.
  
 
4. By looking at the proof above, we can also see that for <math>n = 3</math>
 
4. By looking at the proof above, we can also see that for <math>n = 3</math>
−
we have equality if an only if <math>a_1 = a_2 = a_3</math>.  For <math>n = 5</math>, we
+
we have equality if and only if <math>a_1 = a_2 = a_3</math>.  For <math>n = 5</math>,
 +
assuming that <math>a_1 \ge a_2 \ge a_3 \ge a_4 \ge a_5</math>, we
 
have equality if and only if <math>a_1 = a_2</math> and <math>a_3 = a_4 = a_5</math>,
 
have equality if and only if <math>a_1 = a_2</math> and <math>a_3 = a_4 = a_5</math>,
−
or <math>a_1 = a_2 = a_3</math> and <math>a_4 = a_5</math> (still assuming that
+
or <math>a_1 = a_2 = a_3</math> and <math>a_4 = a_5</math>.
−
<math>a_1 \ge a_2 \ge a_3 \ge a_4 \ge a_5</math>).
 
  
 
5. If we denote <math>P(x) = (x - a_1) \cdots (x - a_n)</math>, then the expression
 
5. If we denote <math>P(x) = (x - a_1) \cdots (x - a_n)</math>, then the expression
−
in the problem is <math>P'(a_1) + \cdots + P'(a_n)</math>, where <math>P'(x)</math> is the
+
in the problem is <math>E_n = P'(a_1) + \cdots + P'(a_n)</math>, where <math>P'(x)</math> is
−
derivative of <math>P(x)</math>.  The graph of <math>P(x)</math> as <math>x</math> goes from <math>-\infty</math>
+
the derivative of <math>P(x)</math>.  (This is easy to see by calculating <math>P'(x)</math>
−
to <math>\infty</math> crosses the <math>x</math>-axis at every root <math>a_k</math>, or is tangent
+
when <math>P(x)</math> is written as a product rather than as a sum of powers of
−
to it, or it is tangent to it and crosses it, depending on the
+
<math>x</math>.)
−
multiplicity of the root.  At a simple root <math>P'(a_k)</math> is <math>> 0</math> or
+
 
−
<math>< 0</math> depending on the direction of the graph of <math>P(x)</math> at <math>a_k</math>.
+
The graph of <math>P(x)</math> as <math>x</math> goes from <math>-\infty</math> to <math>\infty</math> crosses the
−
At a multiple root <math>a_k = \cdots = a_{k+p}</math>, <math>P'(a_k) = 0</math>, and the
+
<math>x</math>-axis, or is tangent to the <math>x</math>-axis at every root <math>a_k</math>.  If the
−
graph of <math>P(x)</math> crosses the axes or not, depending on <math>p</math>.
+
graph is tangent to the <math>x</math>-axis, it crosses it, or it stays in the
 +
same half plane, depending on the multiplicity of the root.  At a simple
 +
root <math>a_k, P'(a_k) > 0</math> or <math>P'(a_k) < 0</math> depending on the direction of
 +
the graph of <math>P(x)</math> at <math>a_k</math>. At a multiple root
 +
<math>a_k = \cdots = a_{k+p}, P'(a_k) = 0</math>, and the graph of <math>P(x)</math> crosses
 +
the <math>x</math>-axis or not, depending on <math>p</math> being odd or even.
 +
 
 +
This way of looking at the problem makes it very easy to find examples
 +
which prove the problem for <math>n</math> even, or <math>n \ge 7</math> and odd, because we
 +
would be looking for polynomials whose graph crosses the <math>x</math>-axis once
 +
from the upper half plane to the lower half plane at a simple root
 +
<math>a_k</math> (thus making <math>P'(a_k) < 0</math>), and is tangent to the <math>x</math>-axis at
 +
all the other roots.  See the picture below for images showing the
 +
graphs of such polynomials.
 +
 
 +
[[File:prob_1971_1.png|600px]]
  
−
I could not see how this way of looking at the problem would help give
+
(Wichking makes essentially the same remarks on
−
a direct proof, without any assumptions on the ordering of <math>a_k</math>'s in
+
https://aops.com/community/p366761.)
−
the case <math>n = 5</math> (such a proof is possible, but difficult).  (The case
 
−
<math>n = 3</math> is very simple to prove directly, without any assumptions, or
 
−
insight into polynomials and their roots.)  However, this way of
 
−
looking at the problem makes it very easy to find examples which prove
 
−
the problem for <math>n</math> even or <math>n \ge 7</math> odd, because we would be looking
 
−
for polynomials whose graph crosses the <math>x</math>-axis once from above to
 
−
below (at a simple root), and is tangent to the <math>x</math>-axis at all the
 
−
other roots.
 
  
  

Latest revision as of 15:32, 20 December 2024

Problem

Prove that the following assertion is true for $n=3$ and $n=5$, and that it is false for every other natural number $n>2:$

If $a_1, a_2,\cdots, a_n$ are arbitrary real numbers, then $(a_1-a_2)(a_1-a_3)\cdots (a_1-a_n)+(a_2-a_1)(a_2-a_3)\cdots (a_2-a_n)+\cdots+(a_n-a_1)(a_n-a_2)\cdots (a_n-a_{n-1})\ge 0.$


Solution

Denote $E_n$ the expression in the problem, and denote $S_n$ the statement that $E_n \ge 0$.

Take $a_1 < 0$, and the remaining $a_i = 0$. Then $E_n = a_1^{n-1} < 0$ for $n$ even. So the proposition is false for even $n$.

Suppose $n \ge 7$ and odd. Take any $c > a > b$, and let $a_1 = a$, $a_2 = a_3 = a_4= b$, and $a_5 = a_6 = ... = a_n = c$. Then $E_n = (a - b)^3 (a - c)^{n-4} < 0$. So the proposition is false for odd $n \ge 7$.

Assume $a_1 \ge a_2 \ge a_3$. Then in $E_3$ the sum of the first two terms is non-negative, because $a_1 - a_3 \ge a_2 - a_3$. The last term is also non-negative. Hence $E_3 \ge 0$, and the proposition is true for $n = 3$.

It remains to prove $S_5$. Suppose $a_1 \ge a_2 \ge a_3 \ge a_4 \ge a_5$. Then the sum of the first two terms in $E_5$ is $(a_1 - a_2)[(a_1 - a_3)(a_1 - a_4)(a_1 - a_5) - (a_2 - a_3)(a_2 - a_4)(a_2 - a_5)] \ge 0$.

The third term in $E_5$ is non-negative (the first two factors are non-positive and the last two non-negative).

The sum of the last two terms in $E_5$ is: $(a_4 - a_5)[(a_1 - a_5)(a_2 - a_5)(a_3 - a_5) - (a_1 - a_4)(a_2 - a_4)(a_3 - a_4)] \ge 0$.

Hence $E_5 \ge 0$.

This solution was posted and copyrighted by e.lopes. The original thread can be found here: [1]


Remarks (added by pf02, December 2024)

1. As a public service, I fixed a few typos in the solution above.

2. Make the solution a little more complete:

2.1. Let us note that the assumptions $a_1 \ge a_2 \ge a_3$ in case $n = 3$ and $a_1 \ge a_2 \ge a_3 \ge a_4 \ge a_5$ in case $n = 5$ are perfectly legitimate. A different ordering of these numbers could be reduced to this case by a simple change of notation: we would substitute $a_i$ by $b_j$ with the indexes for the $b$'s chosen in such a way that the inequalities above are true for the $b$'s.

2.2. The inequality $(a_1 - a_2)[(a_1 - a_3)(a_1 - a_4)(a_1 - a_5) - (a_2 - a_3)(a_2 - a_4)(a_2 - a_5)] \ge 0$ is true because $a_1 - a_2 \ge 0$, and $(a_1 - a_3)(a_1 - a_4)(a_1 - a_5) - (a_2 - a_3)(a_2 - a_4)(a_2 - a_5) \ge 0$. To see this latter inequality, just notice that $a_1 - a_3 \ge a_2 - a_3$, and similarly for the other pairs of factors. The difference of the products is $\ge 0$ as desired.

The argument for the sum of the last two terms in $E_5$ is similar.

3. The case $n = 3$ is very easy to prove in a different way. Note that

$(a_1 - a_2)(a_1 - a_3) + (a_2 - a_1)(a_2 - a_3) + (a_3 - a_1)(a_3 - a_2) = \frac{1}{2}[(a_1 - a_2)^2 + (a_2 - a_3)^2 + (a_3 - a_1)^2]$

I could not find an identity which would give such a simple proof in the case $n = 5$.

4. By looking at the proof above, we can also see that for $n = 3$ we have equality if and only if $a_1 = a_2 = a_3$. For $n = 5$, assuming that $a_1 \ge a_2 \ge a_3 \ge a_4 \ge a_5$, we have equality if and only if $a_1 = a_2$ and $a_3 = a_4 = a_5$, or $a_1 = a_2 = a_3$ and $a_4 = a_5$.

5. If we denote $P(x) = (x - a_1) \cdots (x - a_n)$, then the expression in the problem is $E_n = P'(a_1) + \cdots + P'(a_n)$, where $P'(x)$ is the derivative of $P(x)$. (This is easy to see by calculating $P'(x)$ when $P(x)$ is written as a product rather than as a sum of powers of $x$.)

The graph of $P(x)$ as $x$ goes from $-\infty$ to $\infty$ crosses the $x$-axis, or is tangent to the $x$-axis at every root $a_k$. If the graph is tangent to the $x$-axis, it crosses it, or it stays in the same half plane, depending on the multiplicity of the root. At a simple root $a_k, P'(a_k) > 0$ or $P'(a_k) < 0$ depending on the direction of the graph of $P(x)$ at $a_k$. At a multiple root $a_k = \cdots = a_{k+p}, P'(a_k) = 0$, and the graph of $P(x)$ crosses the $x$-axis or not, depending on $p$ being odd or even.

This way of looking at the problem makes it very easy to find examples which prove the problem for $n$ even, or $n \ge 7$ and odd, because we would be looking for polynomials whose graph crosses the $x$-axis once from the upper half plane to the lower half plane at a simple root $a_k$ (thus making $P'(a_k) < 0$), and is tangent to the $x$-axis at all the other roots. See the picture below for images showing the graphs of such polynomials.

Prob 1971 1.png

(Wichking makes essentially the same remarks on https://aops.com/community/p366761.)


See Also

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