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 6: Line 6:
  
 
==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 60: Line 63:
 
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>P'(a_1) + \cdots + P'(a_n)</math>, where <math>P'(x)</math> is the
 
derivative of <math>P(x)</math>.  The graph of <math>P(x)</math> as <math>x</math> goes from <math>-\infty</math>
 
derivative of <math>P(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 at every root, or is tangent to it,
+
to <math>\infty</math> crosses the <math>x</math>-axis at every root <math>a_k</math>, or is tangent
−
or it is tangent to it and crosses it, depending on the multiplicity
+
to it, or it is tangent to it and crosses it, depending on the
−
of the root.  At a simple root <math>P'(a_k)</math> is <math>> 0</math> or <math>< 0</math> depending
+
multiplicity of the root.  At a simple root <math>P'(a_k)</math> is <math>> 0</math> or
−
on the direction of the graph of <math>P(x)</math> at <math>a_k</math>. At a multiple root
+
<math>< 0</math> depending on the direction of the graph of <math>P(x)</math> at <math>a_k</math>.
−
<math>a_k = \cdots = a_{k+p}</math>, <math>P'(a_k) = 0</math>, and crosses the axes or not,
+
At a multiple root <math>a_k = \cdots = a_{k+p}</math>, <math>P'(a_k) = 0</math>, and the
−
depending on <math>p</math>.
+
graph of <math>P(x)</math> crosses the axes or not, depending on <math>p</math>.
  
 
I could not see how this way of looking at the problem would help give
 
I could not see how this way of looking at the problem would help give

Revision as of 18:49, 14 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 is non-negative (the first two factors are non-positive and the last two non-negative). The sum of the last two terms 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. To make the solution a little more complete, 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.

3. Also, 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 \le 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) \le 0$. To see this latter inequality, just notice that $a_1 - a_3 \le a_2 - a_3$, and similarly for the other pairs of factors. The difference of the products is $\le 0$ as desired.

4. By looking at the proof above, we can also see that for $n = 3$ we have equality if an only if $a_1 = a_2 = a_3$. For $n = 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$ (still assuming that $a_1 \ge a_2 \ge a_3 \ge a_4 \ge a_5$).

5. If we denote $P(x) = (x - a_1) \cdots (x - a_n)$, then the expression in the problem is $P'(a_1) + \cdots + P'(a_n)$, where $P'(x)$ is the derivative of $P(x)$. The graph of $P(x)$ as $x$ goes from $-\infty$ to $\infty$ crosses the $x$-axis at every root $a_k$, or is tangent to it, or it is tangent to it 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 axes or not, depending on $p$.

I could not see how this way of looking at the problem would help give a direct proof, without any assumptions on the ordering of $a_k$'s in the case $n = 5$ (such a proof is possible, but difficult). (The case $n = 3$ 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 $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), and is tangent to the $x$-axis at all the other roots.


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=236986"