Proof of the pigeonhole principle by contradiction 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).
 A: 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$.
A: 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.
