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"
 
(2 intermediate revisions by the same user not shown)
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
+
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 <math>x</math>-axis 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
 
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 essentially the same remarks on
 +
https://aops.com/community/p366761.)
  
  

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"