$\begingroup$

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?

$\endgroup$ 1

4 Answers

$\begingroup$

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.

$\endgroup$ 1 $\begingroup$

The confusion seems to be in the phrase "the total number of objects is at most..." That's incorrectly stated, because it's clearly false - the total number of objects is exactly $N$. The maximum number of objects in a single box is $⌈N/k⌉−1$. That's because we are operating under the hypothesis that none of the boxes contains at least $⌈N/k⌉$ objects (another mis-statement in your recording of the proof). Notice that this is a proof by contradiction, which means that we are trying to assume the opposite of what we're trying to prove, and derive a contradiction. We're trying to prove that some box has at least $⌈N/k⌉$ objects, the opposite of which is not no box has more than $⌈N/k⌉$ objects, but instead no box has at least $⌈N/k⌉$ objects.

$\endgroup$ 2 $\begingroup$

My first question is how they decided that the total number of objects is at most $⌈N/k⌉-1$. Where did they get the $-1$?

For the sake of contradiction, each box has less than $⌈N/k⌉$ items , i.e at most $⌈N/k⌉-1$ (this is probably what they meant by "the total number of objects is at most $⌈N/k⌉-1$ objects"). In total for all objects in all of $k$ boxes (which we know is $N$) will be at most $k(⌈N/k⌉-1)$ objects, or in other words $N \leq k(⌈N/k⌉-1)$.

I don't understand how from the inequality they got that it's a contradiction because there are a total of $N$ objects?

You seem to have wrong brackets there. We have $⌈N/k⌉ < (N/k) + 1$ (by the definition of ceiling function), and so $$ N \leq k(\color{red}{⌈N/k⌉} - 1) < k(\color{red}{((N/k)+1)}-1) = k(N/k) = N. $$

And so you get $N<N$, a contradiction...

$\endgroup$ $\begingroup$

So you have $k$ boxes and you want to prove that there are more than $r$ in a box. Well the most you can have in all the boxes is $kr$ and if $kr\lt N$ you can't fit all $N$ objects in without having more than $r$ in a box.

So we have the idea: now what do we choose for $r$? We want the largest integer we can find with $kr\lt N$ ie $r\lt \frac Nk$. Now we know that $\lceil \frac Nk\rceil\lt \frac Nk+1$, so we can choose $r=\lceil \frac Nk\rceil-1$ to do the job. We then know that we have to have more than $r$ ie at least $r+1=\lceil \frac Nk\rceil$ in one of the boxes.

So I've reversed the way of thinking about it. But to go forwards now, if we want to show that there are at least $\lceil \frac Nk\rceil$ in one of the boxes, that is our $r+1$ and we need $r=\lceil \frac Nk\rceil-1$.

Then the maximum we can accommodate without going above this is $kr=k(r+1)-k \lt k(\lceil\frac Nk\rceil)-k\lt N+k-k=N$.

$\endgroup$ 3

Your Answer

Sign up or log in

Sign up using Google Sign up using Facebook Sign up using Email and Password Submit

Post as a guest

Post Your Answer Discard

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy