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

1971 IMO Problems/Problem 1

Revision as of 15:32, 20 December 2024 by Pf02 (talk | contribs)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)

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"