1
$\begingroup$

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?

$\endgroup$
  • 2
    $\begingroup$ why there's a box with 2 ball? try this: 99 3 1 1 1 .... 1 $\endgroup$ – Exodd Oct 18 '14 at 14:14
  • $\begingroup$ You're right, I'm fixing my proof. $\endgroup$ – sucre Oct 18 '14 at 14:29
  • $\begingroup$ if you'll wait a second, I'll write one for you $\endgroup$ – Exodd Oct 18 '14 at 14:29
  • $\begingroup$ I changed it a little, is it ok now? $\endgroup$ – sucre Oct 18 '14 at 14:32
  • 1
    $\begingroup$ You can only say "if there is a box with 1 ball, then there is no disjoint class of 99 balls". $\endgroup$ – Hagen von Eitzen Oct 18 '14 at 14:33
1
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ From Observation 2: Start taking boxes from smallest to largest, hoping to get exactly $2n$ balls. At the moment your total is at least $2n$ balls, stop. If you have exactly $2n$, you’re done. If not, and you have $2n+k$, the box you just took has at least $k+1$ balls in it, with $k\ge1$. Thus there are at least $k$ boxes with one ball each, which you already took. “Untake” $k$ such boxes, and you’re done. $\endgroup$ – Steve Kass Oct 18 '14 at 17:24
  • $\begingroup$ @SteveKass Nice explicit strategy $\endgroup$ – Hagen von Eitzen Oct 19 '14 at 17:40

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.