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).
Best Answer
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
The maximum number in $m$ boxes is therefore
Now use the inequality you are given so that $\left \lceil \dfrac{n}{m} \right \rceil\lt \dfrac nm+1$ which gives
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$.