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 78: Line 78:
 
in the problem is <math>E_n = P'(a_1) + \cdots + P'(a_n)</math>, where <math>P'(x)</math> is
 
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>
 
the derivative of <math>P(x)</math>.  (This is easy to see by calculating <math>P'(x)</math>
−
for <math>P(x)</math> written as a product rather than as a sum of powers of <math>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
 
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 at every root <math>a_k</math>, or it is tangent to it and stays in the
+
<math>x</math>-axis, or is tangent to the <math>x</math>-axis at every root <math>a_k</math>.  If the
−
same half plane, or it is tangent to the <math>x</math>-axis and crosses it,
+
graph is tangent to the <math>x</math>-axis, it crosses it, or it stays in the
−
depending on the multiplicity of the root.  At a simple root <math>P'(a_k)</math>
+
same half plane, depending on the multiplicity of the root.  At a simple
−
is <math>> 0</math> or <math>< 0</math> depending on the direction of the graph of <math>P(x)</math> at
+
root <math>a_k, P'(a_k) > 0</math> or <math>P'(a_k) < 0</math> depending on the direction of
−
<math>a_k</math>.  At a multiple root <math>a_k = \cdots = a_{k+p}</math>, <math>P'(a_k) = 0</math>,
+
the graph of <math>P(x)</math> at <math>a_k</math>.  At a multiple root
−
and the graph of <math>P(x)</math> crosses the <math>x</math>-axis or not, depending on <math>p</math>.
+
<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
 
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
+
which prove the problem for <math>n</math> even, or <math>n \ge 7</math> and odd, because we
−
be looking for polynomials whose graph crosses the <math>x</math>-axis once from
+
would be looking for polynomials whose graph crosses the <math>x</math>-axis once
−
above to below at a simple root <math>a_k</math> (to make <math>P'(a_k) < 0</math>), and is
+
from the upper half plane to the lower half plane at a simple root
−
tangent to the <math>x</math>-axis at all the other roots.  See the picture below
+
<math>a_k</math> (thus making <math>P'(a_k) < 0</math>), and is tangent to the <math>x</math>-axis at
−
for images showing the graphs of such polynomials.
+
all the other roots.  See the picture below for images showing the
 +
graphs of such polynomials.
  
 
[[File:prob_1971_1.png|600px]]
 
[[File:prob_1971_1.png|600px]]
  
−
(Wichking makes some remarks along similar lines on
+
(Wichking makes essentially the same remarks on
 
https://aops.com/community/p366761.)
 
https://aops.com/community/p366761.)
  

Latest revision as of 16: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"