Waste less time on Facebook — follow Brilliant.
×

Pigeon Hole Principle

The Pigeon Hole Principle was given by Peter Gustav Lejeune Dirichlet. People who have never heard of the Pigeon Hole Principle may think that it is a joke!

Statement: Here's what the statement says: If we must put \(N+1\) or more pigeons into \(N\) pigeon holes, then some pigeon hole must contain two or more pigeons.

Notice the vagueness of the proposition "some pigeon hole must contain . . . ", "two or more . . . ". This is, in fact, a distinguishing feature of the Pigeon Hole Principle, which sometimes allow us to draw quite unexpected conclusions, even when we don't seem to have enough information.

Proof: The proof of this principle is quite simple, and uses only a trivial count of the pigeons in their pigeon holes. Suppose no more than one pigeon were in each hole. then there would be no more than N pigeons altogether, which contradicts the assumption that we have \(N + 1\) pigeons. This proves the Pigeon Hole Principle, using the method of proof by contradiction.

Note by Akshat Jain
3 years, 3 months ago

No vote yet
1 vote

Comments

Sort by:

Top Newest

The PHP is great when you want to prove that "something exists," or "there is something." For example, here's a good beginner-level PHP problem:

There are \(1000000\) people at a huge party. Prove that there exist \(2\) people who know the same number of people at the party. (Assume that "knowing" is a symmetric relationship; that is, A knows B if and only if B knows A. Also assume that knowing yourself doesn't count.)

Michael Tang · 3 years, 3 months ago

Log in to reply

@Michael Tang very childish question........since a human can know 1.2,3,............................999999...so there are 999999 pigeon holes...(assuming each person in the party to be pigeon)..now let us assume the no two pigeons holes contain more than one pigeon..,but this a contradiction as if it so then the number of people in the party will be equal or less than 999999..but we have 1000000 people..hence there exist 2 people who know the same number of people at the party..(proved) Suvadip Sana · 3 years, 3 months ago

Log in to reply

@Michael Tang Could we think about problems (like the one above) as graphs with each pigeon as a vertex and the number of connections as the edges? Lemma Theorem · 3 years, 3 months ago

Log in to reply

@Michael Tang Hey Tang. Could you please go through one of my latest discussion? Priyansh Sangule · 3 years, 3 months ago

Log in to reply

The Pigeon Hole Principle or the Dirichlet Box Principle is one the fundamental theorems of Combinatorics and is absolutely great. Soham Dibyachintan · 3 years, 3 months ago

Log in to reply

I dont get it?? what is there to be amazed? Saravanan Rajenderan · 3 years, 2 months ago

Log in to reply

I think there are many versions/theorems under PHP . Can you explain them ? Priyansh Sangule · 3 years, 3 months ago

Log in to reply

@Priyansh Sangule Can you be more specific as to which versions are you talking about? By the way, I was trying to be totally basic, not trying to go much in deep. Akshat Jain · 3 years, 3 months ago

Log in to reply

@Akshat Jain Alright . Never mind. Priyansh Sangule · 3 years, 3 months ago

Log in to reply

×

Problem Loading...

Note Loading...

Set Loading...