1
$\begingroup$

The problem is as follows: let $n_1, n_2,..., n_t$ be positive integers. Prove that if $n_1+n_2+...+n_t-t+1$ objects are placed into $t$ boxes, then for some $i, i=1, 2, ..., t$, the $i$th box contains at least $n_i$ objects.

I'm having difficulty getting started in developing a proof because I have no intuition as to why this should be true or whether or not it actually is. Could someone help get me started?

$\endgroup$
2
$\begingroup$

A way to think about it is to rewrite $n_1+n_2+\cdots n_t - t+1$ as

$$(n_1-1)+(n_2-1)+\cdots+(n_t-1)+1$$

and then think that if you want try to avoid putting $n_i$ balls into the $i$th box, you can put at most $n_1-1$ balls in the first box, $n_2-1$ in the second, etc., which will leave $1$ ball left, which will have to go somewhere.

$\endgroup$
  • $\begingroup$ For $i=1$ I see why this approach works. But why is this true for $i>1$? It seems that for $i>1$, the extra ball could simply be placed in the $i-1$th box. Because there aren't $t$ extra objects, I'm not understanding why this works for some arbitrary $i$. $\endgroup$ – user93189 Sep 5 '13 at 12:39
  • $\begingroup$ @user93189, try thinking through an explicit example with some small numbers, say $t=3$ and $n_1,n_2,n_3=3,4$ and $5$, so that $n_1+n_2+n_3-t+1=10$. If you try to avoid putting $n_i$ balls in the $i$th box, you can only put $2$ balls in the first box, $3$ in the second, and $4$ in the third, so what can you do with the $10$th ball? $\endgroup$ – Barry Cipra Sep 5 '13 at 15:57
2
$\begingroup$

A counterexample would consist of $t$ boxes with $b_i$ balls, $1 \leq i \leq t$, such that $$b_i \leq n_i-1$$ for all $1 \leq i \leq t$. Now find a upper bound on $\sum_{i=1}^t b_i$ using the above inequality.

$\endgroup$
1
$\begingroup$

Suppose, for the sake of contradiction, that the $i$-th box always contains $< n_i$ objects. Then what is the largest the total number of objects could be? (This occurs when the $i$-th box has $n_i - 1$ objects.) But how many objects are there in total?

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