From my book Discrete Mathematics by Rosen, I can't understand the conclusion of the proof.
THE GENERALIZED PIGEONHOLE PRINCIPLE: If N objects are placed into k boxes, then there is at least one box containing at least ⌈N/k⌉ objects.
Proof by contradiction:
Suppose that none of the boxes contains more than ⌈N/k⌉ objects. Then, the total number of objects is at most ⌈N/k⌉-1 objects.
$$⌈N/k⌉ < (N/k) + 1$$
$$k(⌈N/k⌉ – 1) < k[(⌈N/k⌉+1)-1] = N$$
This is a contradiction because there are a total of N objects.
I don't understand how that inequality shows it's a contradiction, how did they get that the inequality shows less than N objects?
Best Answer
The claim is that at least one of the $k$ boxes contain at least $\lceil N/k\rceil$ objects.
The proof goes by contradiction: Suppose the claim is false, then each box must have strictly less than $\lceil N/k\rceil$ objects, i.e., at most $\lceil N/k\rceil-1$ objects (the greatest integer strictly less than $n$ is $n-1$)
Now, then since there are $k$ boxes and each box has objects $\leq\lceil N/k\rceil-1$, the total number of objects from all the boxes is $\leq k(\lceil N/k\rceil-1)\lt k\cdot N/k=N$ (we use $\lceil x\rceil-1\lt x$) which gives us a contradiction since the total number of objects from all the boxes cannot be strictly less than $N$ (since $N$ is the total number of objects from all the boxes).
Notice the one single $\lt$ in the chain of inequalities in the penultimate step which makes the overall inequality strict, i.e, gives us $N\lt N$
Here's an informal (intuitive) way to interpret the theorem:
We usually look at the worst case scenario. If we want to keep the number of objects in each box as less as possible when putting the objects in the boxes, we can do this by putting one object in each box and then going over to the next box and not fill a previous box unless all the boxes have the same number of objects. We put an object in the 1st box, then one in the 2nd,.. and so on till the $k$th box until all the boxes have one object and then we repeat the above.
If $N$ is a multiple of $k$, then we'd have $N/k$ objects in each box at the end.
Otherwise, we'll have the first $x$ boxes with $\lceil N/k\rceil$ objects where $x$ is the remainder when $N$ is divided by $k$ and the rest of the boxes will have exactly one less object than the first $x$ boxes.