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!
-
$\begingroup$ 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}$ $\endgroup$ – MBW Jun 22 '20 at 13:06
-
1$\begingroup$ @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. $\endgroup$ – Calvin Lin Jun 22 '20 at 13:52
-
$\begingroup$ "$1 ≤ i ≤ j ≤ a$$x_i+x_j$ is also an element" does not make sense. $\endgroup$ – William Elliot Jun 22 '20 at 17:02
-
$\begingroup$ @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). $\endgroup$ – user802105 Jun 22 '20 at 17:05
-
$\begingroup$ @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. $\endgroup$ – 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<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.
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.