More
    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

    Or

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

    Sponsored

    LEAVE A REPLY

    Please enter your comment!
    Please enter your name here

    Subscribe Today

    GET EXCLUSIVE FULL ACCESS TO PREMIUM CONTENT

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

    Exclusive content

    Latest article

    More article