Maths Olympiad Prep

Library / /12 of 16

Algebra Difficulty 6.7 National Olympiad Prove it United States

Problem:
Let a,b,c,d,e,fa, b, c, d, e, f be positive integers, each at least 22, whose sum is SS. Prove that
a(a1)+b(b1)+c(c1)+d(d1)+e(e1)+f(f1)(S10)(S11)+10. a(a-1)+b(b-1)+c(c-1)+d(d-1)+e(e-1)+f(f-1) \leq (S-10)(S-11)+10.
When is equality achieved?

Solution

Solution:
Solution I. Adding 3S+24-3S+24 to both sides makes the inequality equivalent to
(a2)2+(b2)2+(c2)2+(d2)2+(e2)2+(f2)2(S12)2. (a-2)^2 + (b-2)^2 + (c-2)^2 + (d-2)^2 + (e-2)^2 + (f-2)^2 \leq (S-12)^2.
Substituting A=a2A = a-2, B=b2B = b-2, etc., this is the same as
A2+B2+C2+D2+E2+F2(A+B+C+D+E+F)2. A^2 + B^2 + C^2 + D^2 + E^2 + F^2 \leq (A+B+C+D+E+F)^2.
On the left side we have the sum of squares of nonnegative numbers and on the right side we have the square of the sum. The latter is always larger except when all pairwise products AB,AC,DF,AB, AC, DF, \ldots are zeros. This happens when all but one of A,B,C,D,E,FA, B, C, D, E, F are zero, correspondingly, when all but one of a,b,c,d,e,fa, b, c, d, e, f are 22.

Solution II. The given inequality can be written as
a2+b2+c2+d2+e2+f2(S10)2+20. a^2 + b^2 + c^2 + d^2 + e^2 + f^2 \leq (S-10)^2 + 20.
Now, for any two numbers x,yzx, y \geq z, we have
x2+y2z2+(x+yz)2. x^2 + y^2 \leq z^2 + (x+y-z)^2.
Indeed, this is equivalent to
x2z2(x+yz)2y2(xz)(x+z)(xz)(x+2yz)02(xz)(yz), x^2 - z^2 \leq (x+y-z)^2 - y^2 \Leftrightarrow (x-z)(x+z) \leq (x-z)(x+2y-z) \Leftrightarrow 0 \leq 2(x-z)(y-z),
and the last is true because xzx \geq z and yzy \geq z. Note that (1) replaces the numbers (x,y)(x, y) by (z,x+yz)(z, x+y-z) without changing the sum of the two numbers, but increases the sum of their squares. In the original problem, we do this for a,b2a, b \geq 2: we replace (a,b)(a, b) by (2,a+b2)(2, a+b-2):
a2+b222+(a+b2)2. a^2 + b^2 \leq 2^2 + (a+b-2)^2.
We then do the same for (a+b2,c)(a+b-2, c): replace them by (2,a+b+c4)(2, a+b+c-4), and so on. In the end, we will have replaced five of the original numbers by 22's, and the last by a+b+c+d+e+f10=S10a+b+c+d+e+f-10 = S-10.
a2+b2+c2+d2+e2+f222+22+22+22+22+(S10)2=20+(S10)2. \Rightarrow a^2 + b^2 + c^2 + d^2 + e^2 + f^2 \leq 2^2 + 2^2 + 2^2 + 2^2 + 2^2 + (S-10)^2 = 20 + (S-10)^2.
Equality is achieved if and only if there are equalities each time we apply (1), i.e., five of the given numbers are 22's, and the remaining number is therefore S10S-10.

Solution III. We first show the following inequality:
x(x1)+y(y1)(x+y2)(x+y3)+2,x,y2 x(x-1) + y(y-1) \leq (x+y-2)(x+y-3) + 2, \quad x, y \geq 2
Consider two complete graphs, with xx and yy vertices, respectively. (A complete graph has all possible edges drawn.) Thus we have (x2)\binom{x}{2} and (y2)\binom{y}{2} edges in the two graphs. If we glue the graphs together on an edge, we produce a new graph with x+y2x+y-2 vertices. Count edges: the original configuration had (x2)+(y2)\binom{x}{2} + \binom{y}{2} edges, while the new configuration has at most (x+y22)\binom{x+y-2}{2} edges. Since we lost an edge when we glued the two graphs together, we conclude that
(x2)+(y2)(x+y22)+1 \binom{x}{2} + \binom{y}{2} \leq \binom{x+y-2}{2} + 1
This is equivalent to (2) after multiplying by 22. Equality is attained if and only if the new graph is also complete, i.e., one of the original graphs must have been just an edge (x=2x=2 or y=2y=2). From here, apply consecutively (2) to the desired inequality. Again, maximum is attained if and only if five of the given numbers are 22's.

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: MathNet, licensed CC-BY-4.0. Statement reproduced verbatim; metadata (topic, difficulty) added by this project.