Problem:
Let be positive integers, each at least , whose sum is . Prove that
When is equality achieved?
Solution
Solution:
Solution I. Adding to both sides makes the inequality equivalent to
Substituting , , etc., this is the same as
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 are zeros. This happens when all but one of are zero, correspondingly, when all but one of are .
Solution II. The given inequality can be written as
Now, for any two numbers , we have
Indeed, this is equivalent to
and the last is true because and . Note that (1) replaces the numbers by without changing the sum of the two numbers, but increases the sum of their squares. In the original problem, we do this for : we replace by :
We then do the same for : replace them by , and so on. In the end, we will have replaced five of the original numbers by 's, and the last by .
Equality is achieved if and only if there are equalities each time we apply (1), i.e., five of the given numbers are 's, and the remaining number is therefore .
Solution III. We first show the following inequality:
Consider two complete graphs, with and vertices, respectively. (A complete graph has all possible edges drawn.) Thus we have and edges in the two graphs. If we glue the graphs together on an edge, we produce a new graph with vertices. Count edges: the original configuration had edges, while the new configuration has at most edges. Since we lost an edge when we glued the two graphs together, we conclude that
This is equivalent to (2) after multiplying by . 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 ( or ). From here, apply consecutively (2) to the desired inequality. Again, maximum is attained if and only if five of the given numbers are 's.