Given $51$ natural numbers whose sum is $100$.
Show that it is possible to split them to $2$ sets such that for each the sum is $50$.
Also, another interesting question is, what happens instead of natural numbers we have integers?
Note: Assumption here that $0$ doesn't count as a natural number.
Best Answer
Claim: If $a_1,\cdots,a_{m+1}$ are natural numbers that add up to $2m$ then we can find a subset that adds up to $m.$
Proof: By induction.
If $m=1$ then we have two natural numbers, $a_1,a_2$ that add up to $2.$ But that can only be $a_1=a_2=1$, and then $a_1=1$ is the subset.
Assume true for $m-1,$ with $m>1.$ Given $a_1,\cdots,a_{m+1}$ natural numbers that add up to $2m,$ we will reduce the question to a case of $m-1.$
We know some $a_i=1,$ since otherwise, $a_i\geq 2$ for all $i,$ and the sum is at least $2(m+1)>2m.$
We also know that some $a_j>1,$ since otherwise, all the values are $1$ and the sum is $m+1<2m,$ since $m>1.$
If $a_i=1$ and $a_j>1,$ then we can remove $a_i$ and replace $a_j$ with $a_j-1.$ This gives us $m=m-1+1$ natural numbers adding up to $2(m-1).$ So, by the induction proposition, it must have a subset adding up to $m-1.$ But then, replacing $a_j-1$ with $a_j$ if it is in the subset, we have a subset adding up to $m-1$ or $m.$ If $m-1,$ we add the $1.$
Your request is the case $m=50.$
We can find $a_1=a_2=\cdots=a_{m-1}=1$ and $a_m=m+1$ to get $m$ numbers that add up to $2m$ without a subset adding to $m.$ If $m$ is odd, you could also choose all $a_i=2$ and not get a sum of $m.$
We can slightly improve this algorithm for larger $a_j.$
Assume $a_j>1.$ Let $u$ be the number of values $i$ with $a_i=1.$ Then:
$$2m=\sum_{i=1}^{m+1} a_i \geq a_j + u + 2(m-u)=a_j+2m-u$$
So $u\geq a_j.$ That means we can remove $a_j-1$ values $a_i=1$ and replace $a_j$ with $1.$ Then you have $m-(a_j-1)+1$ natural numbers adding up to $2m-2(a_j-1).$ You can find a subset of these numbers that add up to $m-(a_j-1).$ If the subset does not contain the index $j,$ take the complement to get a subset containing $j.$ Then that subset works for $m,$ too.