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"
Line 76: Line 76:
  
 
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
+
for <math>P(x)</math> written as a product rather than as a sum of powers of <math>x</math>.)
−
to it, or it is tangent to it and crosses it, depending on the
+
The graph of <math>P(x)</math> as <math>x</math> goes from <math>-\infty</math> to <math>\infty</math> crosses the
−
multiplicity of the root.  At a simple root <math>P'(a_k)</math> is <math>> 0</math> or
+
<math>x</math>-axis at every root <math>a_k</math>, or it is tangent to it and stays in the
−
<math>< 0</math> depending on the direction of the graph of <math>P(x)</math> at <math>a_k</math>.
+
same half plane, or it is tangent to the <math>x</math>-axis and crosses it,
−
At a multiple root <math>a_k = \cdots = a_{k+p}</math>, <math>P'(a_k) = 0</math>, and the
+
depending on the multiplicity of the root.  At a simple root <math>P'(a_k)</math>
−
graph of <math>P(x)</math> crosses the <math>x</math>-axis or not, depending on <math>p</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>. At a multiple root <math>a_k = \cdots = a_{k+p}</math>, <math>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>.
  
 
This way of looking at the problem makes it very easy to find examples
 
This way of looking at the problem makes it very easy to find examples

Revision as of 17:25, 15 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)$ for $P(x)$ 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 at every root $a_k$, or it is tangent to it and stays in the same half plane, or it is tangent to the $x$-axis and crosses it, depending on the multiplicity of the root. At a simple root $P'(a_k)$ is $> 0$ or $< 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$.

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$ odd, because we would be looking for polynomials whose graph crosses the $x$-axis once from above to below at a simple root $a_k$ (to make $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 some remarks along similar lines 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=237046"