Proof of the pigeonhole principle by contradiction

Question

I'm trying to prove this pigeonhole problem:

Given that $\lceil x \rceil < x + 1$, give a proof by contradiction that if $n$ items are placed in $m$ boxes then at least one box must contain at least $\left \lceil \dfrac{n}{m} \right \rceil$ items.

Now, I understand what the question is saying. However I don't know how to prove it by contradiction (also called indirect proof).

Answer 1

Proof by contradiction involves assuming a suitable statement is true and deriving a contradiction. From this you conclude that the original statement is false.

Here, you are trying to prove that one box must contain at least $\left \lceil \dfrac{n}{m} \right \rceil$ items. So the normal route would be to assume that this is false and that none of the boxes contain this many items.

As a hint on how to proceed - what is the maximum number of items in each box if none contain at least $\left \lceil \dfrac{n}{m} \right \rceil$? Can you relate that to the fact you are supposed to use?

---

Let $L$ be the total number of items you can place without having $\left \lceil \dfrac{n}{m} \right \rceil$ or more in any of the $m$ boxes.

Assume that $L\ge n$ so that you can fit $n$ items into the boxes.

The maximum number you can place into any one box is

$\left \lceil \dfrac{n}{m} \right \rceil-1$.

The maximum number in $m$ boxes is therefore

$L=m\cdot\left \lceil \dfrac{n}{m} \right \rceil-m$.

Now use the inequality you are given so that $\left \lceil \dfrac{n}{m} \right \rceil\lt \dfrac nm+1$ which gives

$L\lt m\cdot\left (\dfrac nm+1\right)-m$ which reduces to $L\lt n$

Now we assumed at the beginning that $L\ge n$, so this is a contradiction. Since we can't have $L\ge n$ we must have $L\lt n$.

Answer 2

Suppose for the purpose of contradiction that we can place the $n$ items in the boxes such that the maximum number of items in any one box is $\left\lceil\frac nm \right\rceil-1 = \left\lceil\frac nm -1\right \rceil$.

Then using $n'$ to count up total number of items placed in boxes we see $n'\leq m\cdot\left\lceil\frac nm -1\right \rceil$ and from the given inequality we have $n'< m\cdot\left(\frac nm -1 +1\right) = m\cdot\frac nm =n$ and $n'<n$ is a contradiction, since we assumed all $n$ items were placed.

Thus the number of items in some box must be greater than the assumption, that is $\left\lceil\frac nm \right\rceil$ as required.