Inequality of arithmetic mean of two sets

Question

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<b+1$ 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!

Answer 1

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.

Answer 2

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<x_2 < ....<x_{a−1}< x_a$ $(1)$. Suppose $x_i+x_{a−i}<b+1 $.

Because of $(1)$ we know that: $x_i+x_{a−i} <b+1 \Rightarrow x_i+x_{a−i-1} <b+1\Rightarrow x_i+x_{a−i-2} <b+1 \Rightarrow ...\Rightarrow x_i+x_{2}<b+1\Rightarrow x_i+x_{1}<b+1\Rightarrow x_i<b+1\Rightarrow x_{i-1}+x_{1}<b+1\Rightarrow x_{i-2}+x_{1}<b+1\Rightarrow ...\Rightarrow x_{2}+x_{1}<b+1\Rightarrow x_{1}+x_{1}<b+1\Rightarrow x_{1}<b+1.$ 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.

Answer 3

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<x_2<....<x_{a−1}<x_a$ (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}<b+1 $ holds for SOME (maybe only one) $i$.

We know 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}<b+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.