8
$\begingroup$

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.

$\endgroup$
  • 3
    $\begingroup$ 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.$ $\endgroup$ – Thomas Andrews Jun 12 at 20:34
  • $\begingroup$ In some sources, $0$ is not counted to be a natural number. Maybe this one is from one of those sources. $\endgroup$ – ArsenBerk Jun 12 at 20:36
  • $\begingroup$ @ThomasAndrews Hi, thanks for your answer. What if $0$ isn't allowed? $\endgroup$ – Ilan Aizelman WS Jun 12 at 20:37
  • 3
    $\begingroup$ 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 $\endgroup$ – Thomas Andrews Jun 12 at 20:37
  • 2
    $\begingroup$ With $50$ numbers, we can choose $51,1,1,1,1,1\cdots.$ to get a counter-example. $\endgroup$ – Thomas Andrews Jun 12 at 20:52
6
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – J_P Jun 13 at 1:11
  • $\begingroup$ 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 $\endgroup$ – Thomas Andrews Jun 13 at 1:29
  • $\begingroup$ 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 $\endgroup$ – Thomas Andrews Jun 13 at 1:32
  • 1
    $\begingroup$ 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. $\endgroup$ – Thomas Andrews Jun 13 at 1:41
  • $\begingroup$ @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 $\endgroup$ – Mike Jun 13 at 3:26
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Very nice, and generalizes to any $N+1$ or more natural numbers adding to $2N.$ $\endgroup$ – Thomas Andrews Jun 13 at 15:41
  • $\begingroup$ 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.$ $\endgroup$ – Thomas Andrews Jun 13 at 15:44
  • 1
    $\begingroup$ 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.$ $\endgroup$ – Thomas Andrews Jun 13 at 15:50
  • $\begingroup$ @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. $\endgroup$ – Mike Jun 13 at 16:11
2
$\begingroup$

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$.

$\endgroup$
1
$\begingroup$

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.

$\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.