2
$\begingroup$

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!

$\endgroup$
7
  • $\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
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.