# A question to be solved via the Pidgeonhole Principle [SOLVED]

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?

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

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