# Uncertain how to proceed with combinatorics proof

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?

## 3 Answers

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.

• 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$. – user93189 Sep 5 '13 at 12:39
• @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? – Barry Cipra Sep 5 '13 at 15:57

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.

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?