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?

  • $\begingroup$ The principle has several generalizations and can be stated in various ways. In a more quantified version: for natural numbers k and m, if n = km + 1 objects are distributed among m sets, then the pigeonhole principle asserts that at least one of the sets will contain at least k + 1 objects.[3] For arbitrary n and m this generalizes to k + 1 = ⌊(n - 1)/m⌋ + 1, where ⌊...⌋ is the floor function. says wikipedia. You may use floor function as well, in case u find it easier. $\endgroup$ – Shatabdi Sinha Nov 17 '17 at 18:50

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.

  • $\begingroup$ Why the downvote? If it's for the informal version I presented, note that I have mentioned it as looking at the worst case scenario, not a general configuration of the boxes and objects. $\endgroup$ – Prasun Biswas Nov 17 '17 at 19:11

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.

  • $\begingroup$ But how does the final inequality show that contradiction? $\endgroup$ – user3252 Nov 17 '17 at 18:49
  • 1
    $\begingroup$ @user32523850925 Each box has at most $⌈N/k⌉−1$ objects. There are $k$ boxes. Therefore, there are at most $k(⌈N/k⌉−1)$ objects. Since $⌈N/k⌉ < N/k + 1$, we know that $⌈N/k⌉−1 < N/k$. So there are strictly fewer than $k(N/k)$ objects. But $k(N/k) = N$, so we now know that there are strictly fewer than $N$ objects. This contradicts the original information that there were exactly $N$ objects (a number cannot be strictly smaller than itself; for example, $47$ is not strictly smaller than $47$). $\endgroup$ – Reese Nov 17 '17 at 18:59

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

  • $\begingroup$ How come you are flooring? Doesn't the definition of the pigeonhole principle involve the ceiling? $\endgroup$ – user3252 Nov 17 '17 at 18:43
  • $\begingroup$ No it should be the greatest integer function. $\endgroup$ – Shatabdi Sinha Nov 17 '17 at 18:44
  • $\begingroup$ @user32523850925 redid it with ceiling - obviously it is easier with floor. $\endgroup$ – Mark Bennet Nov 17 '17 at 18:53

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


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.