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"

m (→‎Solution)
 
(8 intermediate revisions by the same user not shown)
Line 3: Line 3:
  
 
If <math>a_1, a_2,\cdots, a_n</math> are arbitrary real numbers, then <math>(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.</math>
 
If <math>a_1, a_2,\cdots, a_n</math> are arbitrary real numbers, then <math>(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.</math>
 +
  
 
==Solution==
 
==Solution==
−
Take <math>a_1 < 0</math>, and the remaining <math>a_i = 0</math>. Then <math>E_n = a_1(n-1) < 0</math> for <math>n</math> even,
+
Denote <math>E_n</math> the expression in the problem, and denote <math>S_n</math> the statement
−
so the proposition is false for even <math>n</math>.
+
that <math>E_n \ge 0</math>.
 +
 
 +
Take <math>a_1 < 0</math>, and the remaining <math>a_i = 0</math>. Then <math>E_n = a_1^{n-1} < 0</math> for <math>n</math> even.
 +
So the proposition is false for even <math>n</math>.
  
 
Suppose <math>n \ge 7</math> and odd. Take any <math>c > a > b</math>, and let <math>a_1 = a</math>, <math>a_2 = a_3 = a_4= b</math>,
 
Suppose <math>n \ge 7</math> and odd. Take any <math>c > a > b</math>, and let <math>a_1 = a</math>, <math>a_2 = a_3 = a_4= b</math>,
Line 14: Line 18:
  
 
Assume <math>a_1 \ge a_2 \ge a_3</math>.
 
Assume <math>a_1 \ge a_2 \ge a_3</math>.
−
Then in <math>E_3</math> the sum of the first two terms is non-negative, because <math>a_1 - a_3 \ge a_2 - a3</math>.
+
Then in <math>E_3</math> the sum of the first two terms is non-negative, because <math>a_1 - a_3 \ge a_2 - a_3</math>.
 
The last term is also non-negative.
 
The last term is also non-negative.
 
Hence <math>E_3 \ge 0</math>, and the proposition is true for <math>n = 3</math>.
 
Hence <math>E_3 \ge 0</math>, and the proposition is true for <math>n = 3</math>.
Line 21: Line 25:
 
Suppose <math>a_1 \ge a_2 \ge a_3 \ge a_4 \ge a_5</math>.
 
Suppose <math>a_1 \ge a_2 \ge a_3 \ge a_4 \ge a_5</math>.
 
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).
−
<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>.
+
 
 +
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>.
 +
 
 
Hence <math>E_5 \ge 0</math>.
 
Hence <math>E_5 \ge 0</math>.
  
 
This solution was posted and copyrighted by e.lopes. The original thread can be found here: [https://aops.com/community/p366761]
 
This solution was posted and copyrighted by e.lopes. The original thread can be found here: [https://aops.com/community/p366761]
 +
 +
 +
==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 <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 legitimate.  A different ordering of these numbers
 +
could be reduced to this case by a simple change of notation: we
 +
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.
 +
 +
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>
 +
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) \ge 0</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
 +
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>
 +
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>,
 +
or <math>a_1 = a_2 = a_3</math> and <math>a_4 = a_5</math>.
 +
 +
5. If we denote <math>P(x) = (x - a_1) \cdots (x - a_n)</math>, then the expression
 +
in the problem is <math>E_n = P'(a_1) + \cdots + P'(a_n)</math>, where <math>P'(x)</math> is
 +
the derivative of <math>P(x)</math>.  (This is easy to see by calculating <math>P'(x)</math>
 +
when <math>P(x)</math> is written as a product rather than as a sum of powers of
 +
<math>x</math>.)
 +
 +
The graph of <math>P(x)</math> as <math>x</math> goes from <math>-\infty</math> to <math>\infty</math> crosses the
 +
<math>x</math>-axis, or is tangent to the <math>x</math>-axis at every root <math>a_k</math>.  If the
 +
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]]
 +
 +
(Wichking makes essentially the same remarks on
 +
https://aops.com/community/p366761.)
 +
  
 
==See Also==
 
==See Also==
  
 
{{IMO box|year=1971|before=First Question|num-a=2}}
 
{{IMO box|year=1971|before=First Question|num-a=2}}

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"