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 "1979 USAMO Problems/Problem 3"

(→‎Second Hint)
(→‎Solution)
Line 19: Line 19:
  
 
==Solution==
 
==Solution==
−
Let x equal the number of elements in the sequence equivalent to 0 mod 3, y equal those 1 mod 3, and z equal those 2 mod 3. Then, considering that 0+0+0, 1+1+1, 2+2+2, and 0+1+2 are divisible by 3, we obtain the equivalent inequality in the First Hint. This simplifies to <math>x^3 + y^3 + z^3 + 6xyz \ge x^2(y+z) + y^2(x+z) + z^2(x+y).</math> Now, we attempt to prove that <math>x^3 + y^3 + z^3 + 3xyz \ge x^2(y+z) + y^2(x+z) + z^2(x+y).</math> for all positive real numbers x, y, z; our inequality will follow from this. But this is just Schur's Inequality with r = 1! This completes the proof.
+
Let x equal the number of elements in the sequence equivalent to 0 mod 3, y equal those 1 mod 3, and z equal those 2 mod 3. Then, considering that 0+0+0, 1+1+1, 2+2+2, and 0+1+2 are divisible by 3, we obtain the equivalent inequality in the First Hint. This simplifies to <math>x^3 + y^3 + z^3 + 6xyz \ge x^2(y+z) + y^2(x+z) + z^2(x+y).</math> Now, we attempt to prove that <math>x^3 + y^3 + z^3 + 3xyz \ge x^2(y+z) + y^2(x+z) + z^2(x+y).</math> for all nonnegative real numbers x, y, z; our inequality will follow from this. But this is just Schur's Inequality with r = 1! This completes the proof.
  
 
''Note: Schur's Inequality states that <math>x^r(x-y)(x-z) + y^r(y-z)(y-x) + z^r(z-x)(z-y) \ge 0</math>. This can be proven by setting WLOG <math>x \ge y \ge z</math> and bunching together terms that are nonnegative. Challenge: when does equality hold? When does equality hold in the problem?''
 
''Note: Schur's Inequality states that <math>x^r(x-y)(x-z) + y^r(y-z)(y-x) + z^r(z-x)(z-y) \ge 0</math>. This can be proven by setting WLOG <math>x \ge y \ge z</math> and bunching together terms that are nonnegative. Challenge: when does equality hold? When does equality hold in the problem?''

Revision as of 14:23, 19 April 2014

Problem

$a_1, a_2, \ldots, a_n$ is an arbitrary sequence of positive integers. A member of the sequence is picked at random. Its value is $a$. Another member is picked at random, independently of the first. Its value is $b$. Then a third value, $c$. Show that the probability that $a + b +c$ is divisible by $3$ is at least $\frac14$.

First Hint

The given problem is equivalent to proving that $4(x^3 + y^3 + z^3 + 6xyz) \ge (x + y + z)^3$.


Second Hint

Try proving this inequality for all nonnegative real numbers x, y, z; not just positive integers.

Final Hint

Prove that $x^3 + y^3 + z^3 + 3xyz \ge x^2(y+z) + y^2(x+z) + z^2(x+y).$.



Solution

Let x equal the number of elements in the sequence equivalent to 0 mod 3, y equal those 1 mod 3, and z equal those 2 mod 3. Then, considering that 0+0+0, 1+1+1, 2+2+2, and 0+1+2 are divisible by 3, we obtain the equivalent inequality in the First Hint. This simplifies to $x^3 + y^3 + z^3 + 6xyz \ge x^2(y+z) + y^2(x+z) + z^2(x+y).$ Now, we attempt to prove that $x^3 + y^3 + z^3 + 3xyz \ge x^2(y+z) + y^2(x+z) + z^2(x+y).$ for all nonnegative real numbers x, y, z; our inequality will follow from this. But this is just Schur's Inequality with r = 1! This completes the proof.

Note: Schur's Inequality states that $x^r(x-y)(x-z) + y^r(y-z)(y-x) + z^r(z-x)(z-y) \ge 0$. This can be proven by setting WLOG $x \ge y \ge z$ and bunching together terms that are nonnegative. Challenge: when does equality hold? When does equality hold in the problem?

See Also

1979 USAMO (Problems • Resources)
Preceded by
Problem 2 		Followed by
Problem 4
1 • 2 • 3 • 4 • 5
All USAMO Problems and Solutions

The problems on this page are copyrighted by the Mathematical Association of America's American Mathematics Competitions. AMC logo.png

Retrieved from "https://artofproblemsolving.com/wiki/index.php?title=1979_USAMO_Problems/Problem_3&oldid=61568"