Pigeonhole Principle Theorem

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.
• The remaining pigeon holes contain at most floor[A] (largest integer less than or equal to A) pigeons.

Or II) We can say that, 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.

The pigeonhole principle is one of the simplest but most useful ideas in mathematics. We will see more applications that proof of this theorem.

Example 1: 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).

Example 2: A bag contains 10 red marbles, 10 white marbles, and 10 blue marbles. What is the minimum no. of marbles you have to choose randomly from the bag to ensure that we get 4 marbles of same color?

Solution:

Apply pigeonhole principle. No. of colors (pigeonholes) n = 3 No. of marbles (pigeons) K+1 = 4 Therefore the minimum no. of marbles required = Kn+1 By simplifying we get Kn+1 = 10. Verification: ceil[Average] is [Kn+1/n] = 4 [Kn+1/3] = 4 Kn+1 = 10 i.e., 3 red + 3 white + 3 blue + 1(red or white or blue) = 10

The Pigeonhole Principle is a fundamental concept in combinatorics and mathematics that states if more items are put into fewer containers than the number of items, at least one container must contain more than one item. This seemingly simple principle has profound implications and applications in various fields, including mathematics, computer science, and engineering.

This article explores the Pigeonhole Principle, its mathematical formulation, examples, and applications.