CodingThe Pigeonhole Principle | Mathematics

    The Pigeonhole Principle | Mathematics

    Let us suppose, we have 5 pigeons with us, and 4 pigeonholes, where pigeons can be placed. We want to place all of the 5 pigeons into the available pigeonholes.

    Pigeons – P P P P P

    Pigeonholes – | |    | |    | |    | |

    The arrangement of the pigeons would look something like this,

    |PP| |P| |P| |P|

    As we can observe, there is a pigeonhole with 2 pigeons in it.

    Thus, pigeonhole principle states that, if we have ‘n’ number of objects and ‘n-1’ number of buckets to place those objects, then, there would be at least 1 bucket with 2 or more objects in it.

    Theorem –

    I) If “A” is the average number of pigeons per hole, where A is not an integer then

    • At least one pigeon hole contains ceil[A] (smallest integer greater than or equal to A) pigeons
    • Remaining pigeon holes contains at most floor[A] (largest integer less than or equal to A) pigeons


    II) We can say as, if n + 1 objects are put into n boxes, then at least one box contains two or more objects.
    The abstract formulation of the principle: Let X and Y be finite sets and let [f: A->B] be a function.

    • If X has more elements than Y, then f is not one-to-one.
    • If X and Y have the same number of elements and f is onto, then f is one-to-one.
    • If X and Y have the same number of elements and f is one-to-one, then f is onto.

    Pigeonhole principle is one of the simplest but most useful ideas in mathematics.

    • Example: If (Kn+1) pigeons are kept in n pigeon holes where K is a positive integer, what is the average no. of pigeons per pigeon hole?
    • Solution: average number of pigeons per hole = (Kn+1)/n
      = K + 1/n
      Therefore there will be at least one pigeonhole which will contain at least (K+1) pigeons i.e., ceil[K +1/n] and remaining will contain at most K i.e., floor[k+1/n] pigeons.
      i.e., the minimum number of pigeons required to ensure that at least one pigeon hole contains (K+1) pigeons is (Kn+1).



    Please enter your comment!
    Please enter your name here

    Subscribe Today


    Get unlimited access to our EXCLUSIVE Content and our archive of subscriber stories.

    Exclusive content

    Latest article

    More article