Two hundred balls into one hundred boxes

Question

We have distributed two hundred balls into one hundred boxes with the restrictions that no box got more than one hundred balls, and each box got at least one. Prove that it is possible to find some boxes that together contain exactly one hundred balls.

Assume to the contrary that no class of boxes contains $100$ balls. If there is a box with exactly $2$ balls, there is no class of boxes with $98$ balls, which implies that there is no class of boxes with $96$ balls. Continuing this way we see that there is no class containing $4$ balls, so there is no class containing $2$ other than the initial box with $2$ balls, i.e, this box is unique.

Now, if there is a box with $1$ ball, then there is no class of $99$ balls and continuing this way, there is no class of $2$ balls so no box with $1$ ball other than our initial box with $1$ ball. So again, this box is unique. Thus, in the best scenario we have our balls distributed as $1,2,3,...,3$ but this is more than $200$ balls, contradiction.

What do you think? Is this a valid proof now?

Answer 1

if there's a box with 2 balls, surely there won't be any disjoint class of boxes with 98 balls, but you can't say now that there's no class with 96, since if you add the box with 2 balls, it is not disjoint from itself

Let's prove a more generalized version.

Given $2n$ balls distributed in $n$ boxes, with $n>1$ and even, such that every box is not empty and has at most $n$ balls in it, then there exists a subset of the box whit exactly $n$ balls.

First of all, if all the boxes contains exactly 2 balls, it's easy, so let's assume there's a box with more than 2 balls, and consequentially one with 1 ball.
Order the boxes in decreasing order and start picking them from the first. Continue until the balls count get over $n$. Let's say you've picked the first $k$ boxes, $a$ is the number of balls in them, and $b$ is the number of balls in the $k+1$-th box, with $\;a<n\;$ but $\;a+b>n\;$ (if it's equal to $n$, you've finished).
Surely $b>1$, and if $b=2$, then $a=n-1$, and we can add a box with a ball.
If $b>2$, it's easy to show that there are at least $b-2$ boxes with exactly 1 ball, so if $a+b-2\ge n$, we've finished, by picking the right number of boxes with 1 ball.
The only case left is $a+b-2=n-1$, that is $a+b=n+1$.
If $a\ne 0$, then $k>0$, and so there's surely at least another box with 1 ball (different from the $b-2$ ones), and we're done.
If $a=0$, then $b=n+1$, impossible.

Answer 2

We can show the more general result for $2n$ boxes and $4n$ balls. (Note that the corresponding problem with an odd number of boxes cannot be solved because it might happen that all boxes contain two balls thus making odd sums impossible)

Let the largest boxes contain $u$ and $v$ balls, respectively, with $u\ge v$.

If $u=2$, then all boxes contain two balls and we are done. This means that we may assume wlog. that

Observation 1. At least boxes has only one ball.

If $u>v=2$, there must be exactly $u-2$ boxes with one ball and $2n+1-u$ boxes with two balls. Hence if $u\le n+1$, we can obtain a sum of $2n$ using $n$ of the $2$-boxes only; and if $u>n+1$, we can obtain $2n$ from the $u$-box together with $2n-u< u-2$ of the $1$-boxes.

Assume therefore that at $u\ge v\ge 3$. Then there are at least $u+v-4\ge u-1$ boxes with only one ball. Consequently, we may assume that

Observation 2. If any box contains $w$ balls, there are at least $w-1$ boxes with only one ball.

Assume that $2n$ cannot be obtained. Let $s$ be the best approximation to $2n$ that we can get as a sum of a subset $S$ of the boxes (i.e. we minimize $|s-2n|$). Since the complement set gives us $4n-s$, we may assume wlog. that $s<2n$, say $s=2n-d$ with $d> 0$. Let $a$ be the smallest size of a box $\notin S$. Then $a\ge 2d$ as otherwise adding an $a$-box to $S$ would give us a better approximation. And if any box $\in S$ contains $b<a$ balls, or if there is a subset of $S$ that adds up to $b_1+\ldots +b_r=b<a$, then we conclude $a\ge 2d+b$ as otherwise again we easily find a better approximation by adding $a$ and removing $b_1, \ldots, b_r$. Let $r_1$ be the number of boxes in $S$ with one ball. From $d\ge 1$ we conclude that $a\ge 2$ so that all $1$-boxes belong to $S$, hence by observation 1, $r_1\ge 1$. This allows us to obtain $b=1,2,\ldots , r_1$, hence $a\ge 2d+1, 2d+2,\ldots$ and finally $a \ge 2d+r_1$. By observation 2, we have $r_1\ge a-1$, hence $2d\le 1$, contradiction.

Answer 3

If all the boxes had $2$ balls, we'd be done.

Let $a_i$ be the number of balls in box $i$. We can choose $a_1\neq a_2$, without generality loss.

Look at the set of $100$ numbers: $\lbrace a_1,a_2,a_1+a_2,\dotsc,a_1+a_2+\dotsb+a_{99}\rbrace$. If one of these is $0\mod100$, we'd be done. Else, either there are 2 numbers $i,j$ such that $a_1+\dotsb+a_{i+j} \equiv a_1+\dotsb+a_i \mod 100$, or there exists some $i$ such that $a_1 + \dotsb + a_i \equiv a_2 \mod 100$. This could only mean that either $a_{i+1}+\cdots+a_{i+j}=100$ or $a_1 + a_3 + \dotsb + a_i = 100$.