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 "1999 IMO Problems/Problem 2"

(problem and somewhat unattractive smoothing solution)
 
(→‎Resources)
 
(4 intermediate revisions by 3 users not shown)
Line 12: Line 12:
 
== Solution ==
 
== Solution ==
  
−
The answer is <math>C=1/8</math>, and equality holds exactly when two of the <math>x_i</math> are equal to each other and all the other <math>x_i</math> are zero.  We prove this by induction on the number of nonzero <math>x_i</math>.
+
The answer is <math>C=1/8</math>, and equality holds exactly when two of the <math>x_i</math> are equal to each other and all the other <math>x_i</math> are zero.  We prove this by [[induction]] on the number of nonzero <math>x_i</math>.
  
−
First, suppose that at most two of the <math>x_i</math>, say <math>x_a</math> and <math>x_b</math>, are nonzero.  Then the left-hand side of the desired inequality becomes <math>x_a x_b (x_a^2 + x_b^2)</math> and the right-hand side becomes <math>(x_a + x_b)^4/8</math>.  By AM-GM,
+
First, suppose that at most two of the <math>x_i</math>, say <math>x_a</math> and <math>x_b</math>, are nonzero.  Then the left-hand side of the desired inequality becomes <math>x_a x_b (x_a^2 + x_b^2)</math> and the right-hand side becomes <math>(x_a + x_b)^4/8</math>.  By [[AM-GM]],
 
<cmath> \begin{align*}
 
<cmath> \begin{align*}
 
x_a x_b(x_a^2 + x_b^2) = 1/2 \left[ \sqrt{(2x_ax_b)(x_a^2 + x_b^2)} \right]^2
 
x_a x_b(x_a^2 + x_b^2) = 1/2 \left[ \sqrt{(2x_ax_b)(x_a^2 + x_b^2)} \right]^2
Line 22: Line 22:
 
with equality exactly when <math>x_a = x_b</math>, as desired.
 
with equality exactly when <math>x_a = x_b</math>, as desired.
  
−
Now, suppose that our statement holds when at most <math>k</math> of the <math>x_i</math> are equal to zero.  Suppose now that <math>k+1</math> of the <math>x_i</math> are equal to zero, for <math>k\ge 2</math>.  Without loss of generality, let these be <math>x_1 \ge \dotsb \ge x_k \ge x_{k+1}</math>.
+
Now, suppose that our statement holds when at most <math>k</math> of the <math>x_i</math> are equal to zero.  Suppose now that <math>k+1</math> of the <math>x_i</math> are equal to zero, for <math>k\ge 2</math>.  [[Without loss of generality]], let these be <math>x_1 \ge \dotsb \ge x_k \ge x_{k+1}</math>.
 
We define
 
We define
 
<cmath> y_j = \begin{cases} x_j, & j \notin \{k, k+1\} \\
 
<cmath> y_j = \begin{cases} x_j, & j \notin \{k, k+1\} \\
Line 42: Line 42:
 
<cmath> S(x_k + x_{k+1})^3 = S(x_k + x_{k+1})^3 + 3S(x_k^2 x_{k+1} + x_k x_{k+1}^2), </cmath>
 
<cmath> S(x_k + x_{k+1})^3 = S(x_k + x_{k+1})^3 + 3S(x_k^2 x_{k+1} + x_k x_{k+1}^2), </cmath>
 
but none of the other terms change.  Since <math>3S > S \ge a_1 \ge a_k, a_{k+1}</math>, it follows that we have strictly increased the right-hand side of the equation, i.e.,
 
but none of the other terms change.  Since <math>3S > S \ge a_1 \ge a_k, a_{k+1}</math>, it follows that we have strictly increased the right-hand side of the equation, i.e.,
−
<cmath> \sum_{1 \le i<j \le n} x_i x_j (x_i^2 + x_j^2) < sum_{1 \le i<j \le n} y_i y_j (y_i^2 + y_j^2) . </cmath>
+
<cmath> \sum_{1 \le i<j \le n} x_i x_j (x_i^2 + x_j^2) < \sum_{1 \le i<j \le n} y_i y_j (y_i^2 + y_j^2) . </cmath>
 
By inductive hypothesis,
 
By inductive hypothesis,
−
<cmath> \sum_{1\le i<j \le n} y_i y_j (y_i^2 +y_j^2) \le \left( \sum_{i=1}^n y_i right)^4 / 8 , </cmath>
+
<cmath> \sum_{1\le i<j \le n} y_i y_j (y_i^2 +y_j^2) \le \left( \sum_{i=1}^n y_i \right)^4 / 8 , </cmath>
 
and by our choice of <math>y_i</math>,
 
and by our choice of <math>y_i</math>,
 
<cmath> \left( \sum_{i=1}^n y_i \right)^4/8 = \left( \sum_{i=1}^n x_i \right)^4/8 .</cmath>
 
<cmath> \left( \sum_{i=1}^n y_i \right)^4/8 = \left( \sum_{i=1}^n x_i \right)^4/8 .</cmath>
 
Hence the problem's inequality holds by induction, and is strict when there are more than two nonzero <math>x_i</math>, as desired.  <math>\blacksquare</math>
 
Hence the problem's inequality holds by induction, and is strict when there are more than two nonzero <math>x_i</math>, as desired.  <math>\blacksquare</math>
  
 +
== Solution 2 (elegant) ==
 +
 +
I claim that <math>C=\frac{1}{8}</math>. Let <math>P_2=\sum_{i=1}^nx_i^2</math> and <math>S_2=\sum_{1\leq i<j\leq n}x_ix_j</math>. Note that <cmath>\sum_{1\leq i<j\leq n}x_ix_j\left(x_i^2+x_j^2\right)\leq\sum_{1\leq i<j\leq n}x_ix_jP_2=P_2S_2=\frac{\left(2\sqrt{P_2\cdot2S_2}\right)^2}{8}\leq\frac{\left(P_2+2S_2\right)^2}{8}=\frac{1}{8}\left(\sum_{i=1}^nx_i\right)^4.</cmath> Equality holds in the first ineq when all but two of the <math>x_i</math> are zero, and this reduces to the <math>n=2</math> case which we can easily show to be equivalent to <math>\left(x_1-x_2\right)^4\geq0</math>, so <math>x_1=x_2</math>. That is, equality holds when two <math>x_i</math> are the same and the rest are zero.
 +
 +
Q.E.D.
  
 
{{alternate solutions}}
 
{{alternate solutions}}
Line 57: Line 62:
 
* [http://www.mathlinks.ro/Forum/viewtopic.php?p=131846#p131846 Discussion on AoPS/MathLinks]
 
* [http://www.mathlinks.ro/Forum/viewtopic.php?p=131846#p131846 Discussion on AoPS/MathLinks]
  
−
 
+
{{IMO box|year=1999|num-b=1|num-a=3}}
 
[[Category:Olympiad Algebra Problems]]
 
[[Category:Olympiad Algebra Problems]]
 +
[[Category:Olympiad Inequality Problems]]

Latest revision as of 00:04, 17 November 2023

Problem

(Marcin Kuczma, Poland) Let $n \geq 2$ be a fixed integer.

  • (a) Find the least constant $C$ such that for all nonnegative real numbers $x_1, \dots, x_n$,

\[\sum_{1\leq i<j \leq n} x_ix_j (x_i^2 + x_j^2) \leq C \left( \sum_{i=1}^n x_i \right)^4.\]

  • (b) Determine when equality occurs for this value of $C$.

Solution

The answer is $C=1/8$, and equality holds exactly when two of the $x_i$ are equal to each other and all the other $x_i$ are zero. We prove this by induction on the number of nonzero $x_i$.

First, suppose that at most two of the $x_i$, say $x_a$ and $x_b$, are nonzero. Then the left-hand side of the desired inequality becomes $x_a x_b (x_a^2 + x_b^2)$ and the right-hand side becomes $(x_a + x_b)^4/8$. By AM-GM, \begin{align*} x_a x_b(x_a^2 + x_b^2) = 1/2 \left[ \sqrt{(2x_ax_b)(x_a^2 + x_b^2)} \right]^2 &\le \frac{1}{2} \left( \frac{x_a^2 + 2x_a x_b + x_b^2}{2} \right)^2 \\ &= (x_a + x_b)^2/8, \end{align*} with equality exactly when $x_a = x_b$, as desired.

Now, suppose that our statement holds when at most $k$ of the $x_i$ are equal to zero. Suppose now that $k+1$ of the $x_i$ are equal to zero, for $k\ge 2$. Without loss of generality, let these be $x_1 \ge \dotsb \ge x_k \ge x_{k+1}$. We define \[y_j = \begin{cases} x_j, & j \notin \{k, k+1\} \\ x_k + x_{k+1}, & j=k \\ 0, & j=k+1 \end{cases} ,\] and for convenience, we will denote $S= \sum_{i=1}^{k-1} x_i$. We wish to show that by replacing the $x_i$ with the $y_i$, we increase the left-hand side of the desired inequality without changing the right-hand side; and then to use the inductive hypothesis.

We note that \begin{align*} \sum_{1\le i< j \le n} x_i x_j(x_i^2 + x_j^2) ={}& \sum_{1 \le i<j \le k-1} x_i x_j(x_i^2 + x_j^2) + \sum_{1 \le i \le k-1} \left[ x_ix_k(x_i^2 + x_k^2) + x_ix_{k+1}(x_i^2 + x_{k+1}^2) \right] \\ & + x_k x_{k+1}(x_k^2 + x_{k+1}^2) \\ ={}& \sum_{1 \le i<j \le k-1} x_i x_j(x_i^2 + x_j^2) + \sum_{i=1}^{k-1} x_i^3 (x_k + x_{k+1}) + S(x_k^3 + x_{k+1}^3) \\ &+ x_k^3 x_{k+1} + x_k x_{k+1}^3 \end{align*} If we replace $x$ with $y$, then $S(x_k^3 + x_{k+1}^3) + x_k^3 x_{k+1} + x_k x_{k+1}^3$ becomes \[S(x_k + x_{k+1})^3 = S(x_k + x_{k+1})^3 + 3S(x_k^2 x_{k+1} + x_k x_{k+1}^2),\] but none of the other terms change. Since $3S > S \ge a_1 \ge a_k, a_{k+1}$, it follows that we have strictly increased the right-hand side of the equation, i.e., \[\sum_{1 \le i<j \le n} x_i x_j (x_i^2 + x_j^2) < \sum_{1 \le i<j \le n} y_i y_j (y_i^2 + y_j^2) .\] By inductive hypothesis, \[\sum_{1\le i<j \le n} y_i y_j (y_i^2 +y_j^2) \le \left( \sum_{i=1}^n y_i \right)^4 / 8 ,\] and by our choice of $y_i$, \[\left( \sum_{i=1}^n y_i \right)^4/8 = \left( \sum_{i=1}^n x_i \right)^4/8 .\] Hence the problem's inequality holds by induction, and is strict when there are more than two nonzero $x_i$, as desired. $\blacksquare$

Solution 2 (elegant)

I claim that $C=\frac{1}{8}$. Let $P_2=\sum_{i=1}^nx_i^2$ and $S_2=\sum_{1\leq i<j\leq n}x_ix_j$. Note that \[\sum_{1\leq i<j\leq n}x_ix_j\left(x_i^2+x_j^2\right)\leq\sum_{1\leq i<j\leq n}x_ix_jP_2=P_2S_2=\frac{\left(2\sqrt{P_2\cdot2S_2}\right)^2}{8}\leq\frac{\left(P_2+2S_2\right)^2}{8}=\frac{1}{8}\left(\sum_{i=1}^nx_i\right)^4.\] Equality holds in the first ineq when all but two of the $x_i$ are zero, and this reduces to the $n=2$ case which we can easily show to be equivalent to $\left(x_1-x_2\right)^4\geq0$, so $x_1=x_2$. That is, equality holds when two $x_i$ are the same and the rest are zero.

Q.E.D.

Alternate solutions are always welcome. If you have a different, elegant solution to this problem, please add it to this page.

Resources

1999 IMO (Problems) • Resources
Preceded by
Problem 1 		1 • 2 • 3 • 4 • 5 • 6 Followed by
Problem 3
All IMO Problems and Solutions
Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1999_IMO_Problems/Problem_2&oldid=204271"