Infer number of terms in sum, given the value of the sum

In preparation for a math contest my little brother's teacher gave him a nice little book full of interesting little math exercises. And whenever my brother got stuck, he asks me for help and we usually figure something out -- mostly it's a neat and painless solution for this book is made for 10/9/8-graders. But today my brother showed me the following task, and told me that he is really stuck:

You have got $335$ different, positive integers whose sum adds up to $100000$.

Q: What is the smallest and highest required number of odd summands?

Any kind of help or advice will be really appreciated.

Solution 1:

The sum of $n$ odd summnds is at least $1+3+5+\ldots +(2n-1)=n^2$ and can be increases in steps of $2$ from that, i.e. to $n^2+2a$ for some $a\in \mathbb N_0$.

The sum of $m$ even numbers is at least $2+4+6+\ldots +2m = m(m+1)$ and can also be increased in steps of $2$, i.e. to $m(m+1)+2b$ for some $b\in\mathbb N_0$.

With a total of $n+m=335$ summands, we can thus obtain any sum $$n^2+(335-n)(336-n)+2(a+b)$$ that is any number $S$ with $$S\ge 2n^2-671n+112560\qquad\text{and}\qquad S\equiv n\pmod 2.$$ For $S=100000$, we thus need $n=2k$ even and $$8k^2-1342k+112560\le 1000000. $$ With the quadratic formula you should find $9.949\ldots<k<157.8007\ldots$, i.e. the minimal $n$ is $n=20$, the maximal is $n=314$.

Solution 2:

If we have $n$ even and $m$ odd numbers, then the sum of the even numbers is at least $2 + 4 + 6 + \ldots + 2n = n \times \frac{2n + 2}{2} = n^2 + n$, the sum of the odd numbers is at least $1 + 3 + ... + (2m - 1) = m \times \frac{2m - 1 + 1}{2} = m^2$.

If we choose $n = 317$, the sum is at least $101130$. If we choose $n = 315$, $m = 20$, the sum is at least $99940$. We can get a sum of $100000$ by taking the $317$ smallest even and the $20$ smallest odd numbers, then increasing the largest of these numbers by $60$. At least $20$ odd summands are needed.

If we take $n = 19$ and $m = 316$, the sum is at least $100236$. If we choose $n = 21$ and $m = 314$, the sum is at least $99058$. We can get a sum of $100000$ by taking the $21$ smallest even and the $314$ smallest odd numbers, then increasing the largest of these numbers by $942$. At most $314$ odd summands are possible.

Solution 3:

I agree this problem doesn't sound very simple, so I'll attempt a longer but simpler walk-through solution.

Arithmetic series

Before we start, we'll need one formula: the sum of all elements in an arithmetic sequence, i.e. a sequence of equally spaced numbers. $$ S_{a_{1}..a_{n}}=\frac{n(a_{1}+a_{n})}{2} $$ Which is a generalized form of the better known formula to get the sum of natural numbers up to a given n. I'm sure you know this one. $$ S_{1..n}=\frac{n(1+n)}{2} $$

Minimum number of odd summands

Among your 335 numbers there will be some even and some odd numbers.

Can we do it without odd numbers?

If you were to choose only the 335 smallest even numbers, you'd find yourself surpassing 100000. This is because you left out a lot of small odd numbers (1, 3, 5, ...) which went replaced by large even numbers (..., 666, 668, 670). The sum of all even numbers from 2 to 670 is indeed (from the formula above) $$ S_{even:2..670} = \frac{335 (2 + 670)}{2} = \frac{335 \cdot 672}{2} = 112560 $$

How do we make sure the sum stays within 100000?

We will proceed by removing the biggest even numbers and adding the smallest odd numbers.
We remove 670 and we add 1, then we remove 668 and we add 3, until we reach 100000 (or less).
After we repeat this n times, our new total will be the first n odd numbers ($1, 3, 5, ..., 2n - 1$) and the first $335-n$ even numbers ($2, 4, 6, ..., 2(335-n)$). The sum, for each n, will be $$ S=\frac{n(1 + 2n - 1)}{2} + \frac{(335-n)[2 + 2(335-n)]}{2}= $$ $$ =\frac{n(2n)}{2} + \frac{(335-n)2(1 + 335-n)}{2}= $$ $$ =n^2 + (335 - n)(336 - n)= $$ $$ =n^2 + n^2 - 335n - 336n +335\cdot336= $$ $$ =2n^2 - 671n + 112560\leq100000 $$ (note that if you put 0 odd numbers, n is 0 and your total is 112560, as above)
If you solve the above inequality, you will get $n\geq20$ (for n being a positive integer).
Precisely, with just 19 steps you would have a total of 100533, and with the 20th you would get to 99940. Add 60 to either your biggest odd or even number (to make sure you don't have duplicates), and you are exactly at 100000.

Maximum number of odd summands

If you actually solved the inequality above, you'd see another number coming out of it. The full (integer) solution is $20 \leq n \leq 315$.
This means that if you keep repeating the step of removing a large even number, and adding the next odd number, you would get to the opposite case of too few even numbers, and your sum would exceed 100000 again. Which gives you the maximum amount of odd numbers is 315.

I'm not convinced yet

If the previous step confuses you somehow, what you can do is instead inverting even and odd numbers above, and repeat the above solution. You must now find the minimum amount of even numbers to introduce into an all-odd sum which would otherwise be too big.
The first n even numbers would be ($2, 4, 6, ..., 2n$) and the first $335-n$ odd numbers would be ($1, 3, 5, ..., 2(335-n)-1$).
The equation would then be $$ S=\frac{n(2 + 2n)}{2} + \frac{(335-n)[1 + 2(335-n)-1]}{2}= $$ $$ =n(1 + n) + (335-n)(335-n)= $$ $$ =2n^2 -669n + 112225\leq100000 $$ Solve the above and you get... $n\geq20$ again. I told you so.
For 19 steps this time you would reach a total of 100236, while at the 20th step you would get to the safe 99645. Add 355 again to one of the biggest numbers, and you would have your 100000. If you must have at least 20 even numbers, you can have at most $335-20=315$ odd numbers.

Summary

If you put too many odd or even numbers, your sum of distinct numbers will be bigger than 100000, because you would simply run out of small enough numbers.
The amount of even and odd numbers can be unbalanced, but even the most unbalanced distributions of numbers (which we just found) would have at least 20 even and 20 odd numbers.