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

  • $\begingroup$ There is no reason you should need proof by contradiction for something as finite as this. $\endgroup$ – Tac-Tics Oct 18 '14 at 6:54
  • $\begingroup$ it's for an assignment, so I do need proof by contradiction for this. $\endgroup$ – Wyatt Grant Oct 18 '14 at 6:56

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

  • $\begingroup$ could you please elaborate, I'm still not sure where to go. I think the max items in each box should be ⌈n/m⌉-1 but i'm not really sure $\endgroup$ – Wyatt Grant Oct 18 '14 at 7:21
  • $\begingroup$ @WyattGrant so have some confidence. Can you relate that max number to the inequality you are asked to use (which has a ceiling function in it)? $\endgroup$ – Mark Bennet Oct 18 '14 at 7:30
  • $\begingroup$ I don't know how to do that. this is the first time I've had to do anything like this. could you please show me? I thought maybe you meant to just put that max number in where ⌈x⌉ was. however that doesn't really get me anywhere. $\endgroup$ – Wyatt Grant Oct 18 '14 at 7:44
  • $\begingroup$ @WyattGrant You will need to rearrange things a little to use the inequality for the ceiling function. And if you do it right it does get you somewhere, because the inequality converts the ceiling function to an expression without a ceiling function. And that helps because you can then do ordinary arithmetic rather than a constrained integer version. The loss on the inequality is not large enough to cause a problem. Much better if you think it through for yourself. $\endgroup$ – Mark Bennet Oct 18 '14 at 8:22
  • $\begingroup$ @WyattGrant I've amended the answer to show you the way through. $\endgroup$ – Mark Bennet Oct 18 '14 at 11:26

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.