# Given $51$ natural numbers whose sum is $100$, show that it is possible to split them to $2$ sets such that each of them is $50$.

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.

• Well, natural numbers here must mean positive integers. If you allow even $0$ then the $51$ numbers can be $100,0,0,0,0,\cdots$ and no subset equals $50.$ – Thomas Andrews Jun 12 at 20:34
• In some sources, $0$ is not counted to be a natural number. Maybe this one is from one of those sources. – ArsenBerk Jun 12 at 20:36
• @ThomasAndrews Hi, thanks for your answer. What if $0$ isn't allowed? – Ilan Aizelman WS Jun 12 at 20:37
• Oh, I was just clarifying and then answering the question posed later about integers, but yes, the problem definitely must mean the natural numbers do not include zero. @ArsenBerk – Thomas Andrews Jun 12 at 20:37
• With $50$ numbers, we can choose $51,1,1,1,1,1\cdots.$ to get a counter-example. – Thomas Andrews Jun 12 at 20:52

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.

• In the last paragraph, you probably meant "...gives us $m-1$ nat..." instead of $m-1+1$. Also, when you replace $a_j-1$ with $a_j$, why do you distinguish between two cases? Since the subset adds up to $m-1$ before, it will add up to $m$ after, it can't be $m-1$, can it? – J_P Jun 13 at 1:11
• No, I remove the $a_i=1$ and replace $a_j$ with $a_j-1.$ I started with $m+1$ numbers, and now I have a set of $m=m-1+1$ numbers adding up to $2(m-1).$ I wrote $m-1+1$ to suggest the induction - that you are looking at the case $m-1$. @J_P – Thomas Andrews Jun 13 at 1:29
• If the subset didn't contain $a_j-1$ in the $m-1$ case, then it wouldn't contain $a_j$ in the $m$ case, and so the subset would still be $m-1.$ @J_P – Thomas Andrews Jun 13 at 1:32
• For example, if we have the sequence $(3,1,1,1)$ for $m=3,$ then the reduced case is $(2,1,1)$ for $m-1=2.$ If we picked $1+1$ the case of $m-1,$ then you'd get $1+1=2$ in the case $m=3,$ which is not enough. But you have an additional $1$ to add in, so you get $1+1+1=3.$ Of course, since the complement of a solution is also a solution, we could have started with $\{2\}$ as our subset for $m-1$ and then we'd get the subset $\{3\}$ as our sum. – Thomas Andrews Jun 13 at 1:41
• @ThomasAndrews one subset has $a_j-1$; replace this with $a_j$ and its sum goes up by 1. The other subset that does not have $a_j-1$; add to that $a_i=1$ i.e., the 1 that we removed first to be able to apply the inductive hypothesis, and then its sum will go up by 1 too – Mike Jun 13 at 3:26

We will show that the above holds if even we allow there are at least 51 positive integers that sum to 100.

We first observe the following:

Claim 1: Let $$K$$ be the largest number. Then of the 51 $$+m$$ natural numbers; $$m$$ a nonegative integer; that sum to 100, there must be at least $$K$$ 1s.

Indeed, let $$J$$ be the number of 1s in the remaining 50 integers. Then the remaining $$50+m-J$$ numbers must be at least 2 and sum to no more than $$100-K-J$$. Thus we observe the inequality $$2(50+m-J) \le 100-K-J$$ which gives $$J \ge K$$ for all such $$m$$. So Claim 1 follows. $$\surd$$

Then Claim 2 follows almost immediately from Claim 1

Claim 2: The largest number can be no larger than 50.

Indeed, if the largest number is $$Y \ge 51$$ then By Claim 1 there must be at least $$Y-1$$ 1s. But then $$Y$$ plus the $$Y-1$$ 1s sums to over 100 for all such $$Y$$. $$\surd$$

So now sort the numbers from largest to smallest, and let $$\ell$$ be the largest integer such that the the $$\ell$$ largest integers in the list sum to something no greater than 50 i.e., the sum is $$50-L$$ for some nonnegative $$L$$. Then Claim 2 implies that $$\ell>0$$. Then if $$L=0$$ we are done, so we may assume that $$L>0$$.

We may also assume that the $$\ell$$ largest integers do not include any 1s, otherwise all the remaining $$50+L$$ numbers in the list would be 1 and so add $$L$$ of these 1s to the $$\ell$$ largest numbers to get a list that sums to 50 exactly. Thus we may assume that there are no 1s in the $$\ell$$ largest numbers. However, note that $$L \le K$$ and that by Claim 1 there are at least $$K \ge L$$ 1s, and as we just observed, none of these $$\ge K$$ 1s are in the first $$\ell$$ numbers. So add in $$L$$ of the ones to the $$\ell$$ largest numbers and they will sum to exactly 50.

• Very nice, and generalizes to any $N+1$ or more natural numbers adding to $2N.$ – Thomas Andrews Jun 13 at 15:41
• Alternatively if $1$ is in your first $\ell,$ and $L>0,$ then $L$ was not your minimum, since the $\ell'=\ell+1$ has $L'=L-1.$ – Thomas Andrews Jun 13 at 15:44
• Of course, the case when you have $51+m$ natural numbers for $m>0$ can be reduced to the case when $m=0$ simply by replacing $m+1$ numbers by their sum, getting $51$ numbers adding to $100.$ The real key is you can't always do it with $50$ numbers adding to $100,$ since then you can have $100=51+1+1+\cdots+1.$ – Thomas Andrews Jun 13 at 15:50
• @ThomasAndrews wholeheartedly. The sentence in my proof "all the remaining 50+L numbers in the list would be 1" did read awkwardly to me if we assumed that there were **exactly 51 numbers i.e., wouldn't that imply more than 51 numbers in the list to start with too, so I felt the need to say that the proof works for $51+m$, just to avoid that awkwardness. – Mike Jun 13 at 16:11

Try a greedy approach: Let $$a_1\ge a_2\ge\ldots \ge a_{51}\ge 1$$ be the given natural numbers and assume that it is not possible to find a subsequence that sums up to $$50$$. Note that $$a_1\le 50$$ because already $$51+\underbrace{1+1+\cdots+1}_{50}>100.$$ If $$a_1=50$$, we are done, hence $$a_1\le 49.$$ As already $$\underbrace{2+2+\cdots+2}_{51}>100,$$ we see that $$a_{51}=1$$. Let $$r$$ be the numbre of summands that are $$=1$$. As just seen $$r\ge1$$. Let $$m$$ be maximal with $$\tag1\sum_{i=1}^{m} a_i\le 49.$$ From the above, $$1\le m\le 50$$. Then $$\sum_{i=1}^{m+1} a_i\ge 51$$. In particular, $$a_{m+1}\ge2$$. It follows that all numbers $$=1$$ are among $$a_{m+2},\ldots, a_{51}$$. Hence $$49\ge \sum_{i=m+2}^{51}a_i\ge (50-m)\cdot 2-r$$ or equivalently $$\tag2r\ge51-2m .$$ If $$\sum_{i=1}^{m} a_i\ge 50-r$$, we can fill up with summands that are $$=1$$ to reach a sum of $$50$$. Hence $$\sum_{i=1}^{m} a_i\le 49-r$$. We conclude that $$a_{m+1}\ge r+2$$. Then each summand in $$(1)$$ is $$\ge r+2$$ and hence $$\tag3m\le \left\lfloor\frac{49}{r+2}\right\rfloor.$$ Knowing that $$r\ge1$$, $$(3)$$ gives us $$m\le 16$$. Then $$(2)$$ gives us $$r\ge19$$, then $$(3)$$ gives $$m\le 2$$, then $$(2)$$ gives $$r\ge47$$, then $$(3)$$ gives $$m\le 1$$, in the next round we get $$r\ge49$$ and finally $$m\le 0$$, contradicting $$m\ge1$$.

Here's another variation, I'll make use of the statement Mike proved: if $$K$$ is the largest of the numbers and $$J$$ is the number of $$1$$'s, then $$J\geq K$$: the sum of all numbers is at least as big as $$K + J + 2(50-J)$$, so $$K-J+100\leq 100$$.

Suppose now that we have some numbers $$a_1,a_2,...,a_{51}$$ for which the statement "there exists an appropriate split" holds. Thus we can split the $$a_i$$ into sets $$X$$ and $$Y$$ such that the sums over elements of $$X$$ and $$Y$$ are $$50$$. We can construct another group of numbers by adding $$1$$ to one number and subtracting $$1$$ from another: $$a_1,...,a_i+1,...,a_j-1,...,a_{51}$$. Suppose $$a_i$$ and $$a_j$$ both belong to either $$X$$ or $$Y$$. Then the old split is still valid. Otherwise WLOG suppose $$a_i\in X$$ and $$a_j\in Y$$. Then the sum over $$X$$ will be $$51$$ and the sum over $$Y$$ will be $$49$$. Suppose there is at least one $$1$$ in $$X$$. We can move this $$1$$ to $$Y$$ to obtain a valid split. If not, all $$J$$ $$1$$'s are in $$Y$$. Pick any element $$b\in X$$ and move it to $$Y$$. Since $$b\leq K\leq J$$, we can move enough $$1$$'s from $$Y$$ to $$X$$ to obtain a valid split.
In all cases, we've found a valid split so the statement holds for this new group of numbers as well.

The statement obviously holds for the solution $$1,1,...,1,50$$. All other solutions are constructible from this one by the above increment/decrement procedure. Thus the statement holds for all solutions.