I find my self struggling to understand this proof given by Richard A. Brauldi in his book on "Introductory Combinatorics". It is required to show that If $q_1 + q_2 + \dots + q_n – n + 1$ objects be distributed into $n$ boxes, then for some $i = 1,2, \dots, n$, the $i$th box contains at least $q_i$ objects.
He starts out:
Suppose that we distribute $q_1 + q_2 + \dots + q_n - n + 1$ objects among $n$ boxes. If for each $i = 1,2, \dots , n $ the $i$th box contains fewer than $q_i$ objects, then the total number of objects in all boxes does not exceed $(q_1 – 1) + (q_2 – 1) + \dots + (q_n – 1) = q_1 + q_2 + \dots + q_n – n$.
I do not see how this follows. It would be dearly requested for someone to elucidate the reasoning more clearly.
He then continues:
Since this number is one less than the number of objects distributed, we conclude that for some $i = 1,2, \dots ,n$ the $i$th box contains at least $q_i$ objects.
I don't seem to see what proof method he is following. He starts out with an assumption, then deduces something (and I fail to see how) within that assumption; and, also, I fail to see how he claims the deduction without the assumption. Perhaps, I might be missing something fairly obvious. It would be much appreciated if someone could point that out. Thank you in advance.
The goal is to show that for some $i$, the $i$th box contains at least $q_i$ objects. The only way this can fail is if for every $i$, the $i$th box receives at most $q_i - 1$ objects. Let's make this last sentence into a formal statement and give it a name $(F)$ for "failure" $$ (F):\text{for each $i=1,\dots,n$, the $i$th box receives at most $q_i-1$ objects.} $$ Now we can cast the author's argument as an argument by contradiction. The goal is to prove the negation of $(F)$, as we already said, so we start by distributing all the objects and assuming $(F)$. Since $(F)$ holds, by adding up across $i$, we can count the number of objects distributed amongst all the boxes: suppose the $i$th box receives $N_i$ objects, which as we have assumed is $\le q_i-1$. Then the total number of objects that have been distributed is by definition $\sum_{i=1}^n N_i$. On the one hand, $$ \sum_{i=1}^n N_i = q_1 + \dots + q_n - n + 1, $$ because that's how many objects we distributed at the start, but on the other hand $$ \sum_{i=1}^n N_i \le \sum_{i=1}^n (q_i-1) = q_1 + \dots + q_n - n, $$ because we are assuming $(F)$. Since $$ q_1 + \dots + q_n - n < q_1 + \dots + q_n - n + 1 $$ and both sides of the inequality count the total number of objects distributed, we reached a contradiction. Therefore, the negation of $(F)$ must hold, and we have achieved the goal.