I saw this question, and I proved the first half of the "iff", but I still need help to prove the second half.

Of the set $1,2,...,n$ you take the sum of part of the numbers, so that the sum will be the average of the remaining numbers in the set. You can take $2$ numbers or more. Prove that it's possible if and only if $n+1$ is a square.

Let's take the first $k$ numbers, so that their sum is; $1+2+...+k=\frac{k^2+k}{2}$, this sum should be the average of $\{k+1,k+2,...,n\}$, which is known to be the average of $\{k+1,n\}$. so; $$\frac{k+1+n}{2}=\frac{k^2+k}{2}\\k+1+n=k^2+k\\n+1=k^2$$ That proves the first half, that I can always find an solution if $n+1$ is a square, but I didn't find the way to prove the "only if" part. I guess we need to show that the previous example is the only one, but I haven't find such proof jet.

Thanks in advance for any help.

up vote 6 down vote accepted

Let's say for given $n$ there's a $k$ such that the task is possible. Denote the sum of the numbers you choose by $S_k$ then we have $$\frac{n^2+n}{2}-S_k=S_k(n-k)$$ Or $2S_k=\dfrac{n^2+n}{n-k+1}\ge k^2+k$, which is equivalent to $(n-k)(n+1-k^2)\ge 0$
Because $n-k>0$ so $n+1\ge k^2$, thus we can set $n+1=k^2+t\ (t\ge 0)$.
Since $n-k+1\mid n^2+n$ and $n-k+1\mid n^2-k^2+n+k$, which gives us $$k^2-k+t\mid k^2-k\Rightarrow k^2-k\ge k^2-k+t$$ So $t$ must be $0$, or $n+1=k^2$ and our proof is complete

  • What's the meaning of $k$ here? What I am missing is the condition that at least 2 elements from ${1, ..., n}$ must be chosen. This is a crucial condition because else $n \mod 2 = 1$ would be sufficient. As an example, if $n = 7$, just pick $4$ from the set. The average of the remaining elements remains $4$. But if you must choose at least 2 elements, you won't find them. Don't take me wrong, I don't say your proof isn't correct, I just don't fully understand it. – Ronald Aug 10 at 11:19
  • Thanks for the answer. There is one thing I didn't get jet; $n-k+1\mid n^2-k^2+n+k$ why is that true? – 76david76 Aug 10 at 11:47
  • $k$ is just the number of numbers you have to pick to complete the task (the smallest number if you want to be exact). The only if clause states that if $n$ satisfies that condition, then $n+1=x^2$ for some $x$. It just happens to be that $x=k$, if $x=k+1$ or $\lfloor \sqrt{k}\rfloor$ it'll still be fine. Yes, there are no $k$ for $n=7$, but also we don't consider it in our proof cause it doesn't satisfy the condition in the first place. – cortek Aug 10 at 11:50
  • 2
    Just expand $(n+k)(n-k+1)$ – cortek Aug 10 at 11:51
  • Thank you. That helps. But in case $n = 7$, $k = 1$ (choose 4) would work. In case $k = 1$ both $n - k + 1 \mid n^2 + n$ and $n - k + 1 \mid n^2 - k^2 + n + k$ are satisfied for all $n$. Your conclusion that $t = 0$ is valid, but I personally would explicitly exclude the case $k = 1$ because $k \geq 2$ is given. +1 – Ronald Aug 10 at 12:19

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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