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?
Best Answer
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.