# Inequality of arithmetic mean of two sets

If $$a,b>0$$ and $$Q=\{x_1, x_2, x_3,..., x_a\}$$ a subset of the natural numbers $$1, 2, 3,..., b$$ such that, for $$x_i+x_j with $$1 ≤ i ≤ j ≤ a$$, then $$x_i+x_j$$ is also an element of Q. Prove that:

$$\frac{x_1+x_2+x_3+...+x_a}{a} ≥ \frac{b+1}{2}$$
so basically, you have to prove that the arithmetic mean of Q satisfying the condition is greater than equal to the arithmetic mean of the set the natural numbers $$1, 2, 3,..., b$$.

Any help would be appreciated. Thanks in advance!

• Hint: Note that if $x_i < \frac{b+1}{2}$ then $2x_i = x_j \in Q$ so we can replace $x_i$ and $x_j$ with $\frac{3 x_j}{2}$ – MBW Jun 22 '20 at 13:06
• @MBW Are you certain that you could do that replacement? E.g. What if we had $x_1 + x_2 = x_j$, and so we can't replace $x_j$ with another value? IE If we had the sequence $1, 1, 2, 3$, then for $i=2, j = 3$, you want to replace it with $1, 3, 3, 3$ where the condition doesn't hold. – Calvin Lin Jun 22 '20 at 13:52
• "$1 ≤ i ≤ j ≤ a$$x_i+x_j$ is also an element" does not make sense. – William Elliot Jun 22 '20 at 17:02
• @Calvin Lin Note that the sequence 1, 1, 2, 3 must be a subset of the first b positive integers (thats why two 2 members must be different). – user802105 Jun 22 '20 at 17:05
• @CalvinLin what I mean is that the sum $x_1 + x_2 + \ldots + x_i + \ldots + x_j + \ldots + x_a = x_1 + x_2 + \ldots + \frac{3x_j}{2} + \ldots + x_a$ where the right hand side does not contain $x_i$, that is, it has one less addition. – MBW Jun 22 '20 at 17:07

Hint: For each $$i$$, show that $$x_i + x_{a-i} \geq b+1$$.

Proof by contradiction. Suppose $$x_i + x_{a-i} < b+1$$, which satisfies the condition in the problem.
What does it make sense to consider next?
Do some work to reach a contradiction.

Corollary: $$2\sum x_i \geq a (b+1)$$, and the result follows.

I think i have solved my problem. @Calvin Lin thanks a lot, the hint was very helpful. Please correct me if I am wrong.

Solution:

Without loss of generality we assume $$x_1 $$(1)$$. Suppose $$x_i+x_{a−i}.

Because of $$(1)$$ we know that: $$x_i+x_{a−i} Thats why Q has to have $$a-i+i+1=a+1$$ elements. Contradiction! Thats why for each i, $$x_i+x_{a−i}≥b+1$$ must hold. After that the proof is excatly like Calvin Lin described.

I just found out that my proof was flawed. Hopefully the new proof is right. Here is my new proof:

Without loss of generality we assume $$x_1 (1). We can assume this because all $$x_i$$ are different (we know that because $$Q$$ is a subset of the DIFFERENT natural numbers from $$1$$ to $$b$$). Now we differentiate two cases.

Case $$1$$: $$x_i+x_{a−i}≥b+1$$ holds for ALL $$i$$.

Now we sum $$x_i+x_{a−i}≥b+1$$ for all possible $$i$$ (condition of this case). We get $$2\sum x_i \geq a (b+1)$$. After rearranging we get the desired expression: $$\frac{\sum x_i}{a}=\frac{x_1+x_2+x_3+...+x_a}{a} ≥ \frac{b+1}{2}$$. Now we consider the second case.

Case $$2$$: $$x_i+x_{a−i} holds for SOME (maybe only one) $$i$$.

We know that $$x_1 holds (because of $$(1)$$). That implies that, $$x_1, x_{1}+x_{1}, ..., x_{i-1}+x_{1}, x_i+x_{1}, ..., x_i+x_{a−i-1}, x_i+x_{a−i}$$ are the ONLY elements of $$Q$$ ($$Q$$ has only got $$a$$ elements). Thats why we know $$x_i=i*x_1, x_i+x_{a−i}=x_a$$ and $$x_1+x_a \geq b+1$$ $$(2)$$ (or else $$x_1+x_a$$ is also a element of $$Q$$ and $$Q$$ has $$a+1$$ elements). Because of the condition of this case $$x_1, x_2, x_3, ... , x_a$$ is a arithmetic sequence with common difference $$x_1$$. The average of the sum of an arithmetic sequence is the average of the first and last term.
Thats why we get: $$\frac{x_1+...+x_a}{a}=\frac{x_1+x_a}{2} ≥ \frac{b+1}{2}$$ (because of $$(2)$$). That is the desired expression and we are finished with our proof.

Thanks a lot for all the contribution to this problem. I hope everyone can understand this proof.