Pigeonhole Principle | Discrete Mathematics

Its states that –

If (N+1) pigeons occupy N holes, then some hole must have at least 2 pigeons.

Thus if 5 pigeons occupy 4 holes, then there must be some hole with at least 2 pigeons. It is easy to see why : otherwise, each hole as at most 1 pigeon and the total number of pigeons couldn’t be more than 4.

The Math Behind the Fact:

The pigeonhole principle has many generalizations. For instance:

  • If you have N pigeons in K holes, and (N/K) is not an integer, then then some hole must have strictly more than (N/K) pigeons. So 16 pigeons occupying 5 holes means some hole has at least 4 pigeons.
  • If you have infinitely many pigeons in finitely many holes, then some hole must have infinitely many pigeons!
  • If you have an uncountable number of pigeons in a countable number of holes, then some hole has an uncountable number of pigeons!

Example :

The minimum number of cards to be dealt from an arbitrarily shuffled deck of 52 cards to guarantee that three cards are from same suit is

  1. 3
  2. 8
  3. 9
  4. 12

Solution :

There are 4 sets of cards. So, up till 8 cards there is a chance that no more than 2 cards are from a given set. But, once we pick the 9th one, it should make  3 cards from any one of the sets. So, (C) is the answer.

Leave a Reply

Your email address will not be published. Required fields are marked *