Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Question: Let $n_1, n_2, \cdots, n_t$ be positive integers. Show that if $n_1 + n_2 + \cdots + n_t - t + 1$ objects are placed into $t$ boxes, then for some $i$, $i = 1, 2, \cdots, t, $the $i$th box contains at least $n_i$ objects.

Attempt: So, before I began attempting to solve this, I decided to see if this was actually true, but I couldn't get what I'm supposed to show to even be correct. Here are the numbers I chose:

$n_1 = 5, n_2 = 3, n_3 = 6, n_4 =8, n_5 = 7, n_6 = 2.$ This implies that $t = 6,$ and we have $i = 1, 2, \cdots, 6$.

So, next step is to do $n_1 + n_2 + \cdots + n_t - t + 1 = 5 + 3 + 6 + 8 + 7 + 2 - 6 + 1 = 26.$ I distribute these 26 objects among my boxes one box at a time, so one time through, each box obtains 1 object, which leaves $26-6 = 20$ objects left to distribute. Follow this pattern and we end with box $1$ containing $5$ objects, box $2$ containing $5$ objects, and boxes $3, 4, 5, 6$ containing $4$ objects each.

According to the question, the $i$th box should hold at least $n_i$ objects, but if you look at the $4$th box, where $i = 4$, then you witness that it only holds $4$ objects, not at least $n_4 = 8$ objects.

Am I misinterpreting the question? I understand that if I stick with variables, I could show the statement holds through contradiction.

For instance, If every box, $i$, contains $n_i - 1$ objects at most, then $\sum_{i=1}^t n_i - 1 = n_1 + n_2 + \cdots + n_t - t < n_1 + n_2 + \cdots + n_t - t + 1$, which is a contradiction, because we have $n_1 + n_2 + \cdots + n_t - t + 1$.

Where am I interpreting this question wrong?

share|improve this question
    
Please revise your title. –  Alexander Gruber Mar 20 '13 at 22:51
    
To say [Solved]? New here. –  David Mar 20 '13 at 22:54

3 Answers 3

up vote 1 down vote accepted

You’ve misunderstood the conclusion of the theorem. It does not say that Box $i$ will contain at least $n_i$ objects for each $i$ from $1$ through $t$: it says that there will be at least one $i$ such that Box $i$ contains at least $n_i$ objects. In your example you actually have three, Boxes $1,2$, and $6$, which is more than the theorem guarantees.

share|improve this answer
    
Thanks, I just had that clarified. Again, many thanks. –  David Mar 20 '13 at 22:51
    
@David: You’re welcome. –  Brian M. Scott Mar 20 '13 at 22:51

It's easier. Suppose that for each $i$, box $i$ contains $\le n_i - 1$ objects. Sum up over all boxes, and you will see that at least one object has remained out.

share|improve this answer

I think what the question asks is to prove that there exists an $i$ such that the $i$-th box contains at least $n_i$ objects.

This can be proved by contradiction. If there does not exists such an $i$, then the total number of objects in $t$ boxed can be at most $\displaystyle\sum_{i=1}^t(n_i-1)$, which contradicts to there are $\displaystyle(\sum_{i=1}^tn_i)-t+1$ objects.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.