0
$\begingroup$

I'm working my way through Discrete Mathematics by Levin and tried to prove the "Pigeonhole Principle" on my own, as the proof in the book is entirely in words. I'm still new to proofs so I would really appreciate as much feedback and guidance as possible. I'm also still learning about this site so sorry for any formatting issues.

From the text: The Pigeonhole Principle: If more than n pigeons fly into n pigeon holes, then at least one pigeon hole will contain at least two pigeons. Prove this!

My attempt to a proof:

Let $x>n$, $x\in\mathbb{Z}^+$. Then the number of pigeons per hole is $x/n$. Since $x>n$, $x/n>1$ and $x\,\operatorname{mod}\, n\geq 1$, it follows that at least one hole has at least 2 pigeons.

Thank you!

$\endgroup$
6
  • 3
    $\begingroup$ How exactly does “One hole has at least 2 pigeons” follow from the previous statements? $\endgroup$
    – Martin R
    Jun 8 at 8:15
  • 1
    $\begingroup$ Also $x \bmod n \ge 1$ may not hold (4 pigeons in two holes: $4 \bmod 2 = 0$). $\endgroup$
    – Martin R
    Jun 8 at 8:17
  • $\begingroup$ @martin-r Those are good points. Is there a better way to guide the logic to one hole having more than one pigeon? for the second one, could I say something like "the remainder is always >= 1 or x/n > 1? $\endgroup$
    – Sendagaijin
    Jun 8 at 8:23
  • $\begingroup$ See Are there rigorous formulation and proof of the pigeonhole principle? $\endgroup$
    – Martin R
    Jun 8 at 8:28
  • $\begingroup$ @Lorago: No need for \operatorname{mod}, there is \bmod :) $\endgroup$
    – Martin R
    Jun 8 at 8:53

1 Answer 1

Reset to default
1
$\begingroup$

1. Proof by contraposition

The easiest way to prove this statement (in my opinion) uses the contrapositive of the statement. Namely, consider: "if each hole contains at most one pigeon, then there must be at most $n$ pigeons". Since this statement is trivial, you got your proof.

2. Proof by induction

Alternatively, you could prove this by induction. Your base case is when $n=1$, so that you consider only a single hole and at least two pigeons. Trivially, since there are more pigeons than holes, the single hole will contain all the pigeons, which is more than one.

For the inductive step, assume the statement is true for some $n\geq 2$. Then, you wish to prove that if at least $n+2$ pigeons fly into $n+1$ holes, at least one of them will have to contain more than one pigeon.

To this end, let $x\geq n+2$ be the number of pigeons. You can assign a single pigeon into single hole and consider the remaining $x-1$ pigeons. Since one hole is already non-empty, you can use your inductive hypothesis to show that at least one of the holes will contain more than one pigeon. This concludes the induction.

$\endgroup$

Not the answer you're looking for? Browse other questions tagged or ask your own question.