2
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Please revise your title. $\endgroup$ – Alexander Gruber Mar 20 '13 at 22:51
  • $\begingroup$ To say [Solved]? New here. $\endgroup$ – David Mar 20 '13 at 22:54
1
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, I just had that clarified. Again, many thanks. $\endgroup$ – David Mar 20 '13 at 22:51
  • $\begingroup$ @David: You’re welcome. $\endgroup$ – Brian M. Scott Mar 20 '13 at 22:51
1
$\begingroup$

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.

$\endgroup$
0
$\begingroup$

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.

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