PIGEONHOLE  PRINCIPLE

Theorem 1 :  If  n  pigeons are assigned to m  pigeonholes, and  m  < n , then at least one pigeonhole contains two or more pigeons.

     Proof by contradiction : Suppose each pigeonhole contains at most 1 pigeon. Then at most m pigeons have been assigned. But since m  <  n ,  not all pigeons have been assigned pigeonholes. This is a contradiction. At least one pigeonhole contains two or more pigeon. 

     Example 1 :           

            If 8 people are chosen from a group, at least two of them have been born on the same day of the week. Each person ( pigeon ) is assigned to the day of the week ( pigeonhole) in which he or she was born. Since there are eight people and only 7 days, the pigeonhole principle tells us that at least two people must be assigned to the same day of the week.

            Note that the pigeonhole principle provides an existence proof, there must be an object or objects with a certain characteristics. In the example, this characteristic is having been born on the same day. The pigeonhole principle guarantees that there are at least two people with this characteristics but gives no information on identifying this people.  In contrast, a constructive proof guarantees the existence of an object or objects with a certain characteristic by actually constructing such an object or objects. For example, we could prove that given two rational numbers p and q, there is a rational number between them by showing that  ( p + q ) / 2  is between p and q. 

                                                                                                                                                                                                                                                                                                                                                                                                                                

            In order to use the pigeonhole principle we must identify pigeons ( objects ) and pigeonholes ( categories of the desired characteristic ) and be able to count the number of pigeons and the number of pigeonholes.

Example 2 :  Show that if any five numbers from  1  to  8  are chosen, then  2 of them will add to 9.

    Solution :   Construct four different sets, each containing two numbers that add up to 9. 

                 Let   A₁ = { 1 ,  8 },    A₂ = { 2 ,  7 },    A₃ = { 3 ,  6 },    A₄ = { 4 ,  5 }.  Each of the five numbers chosen must belong to one of these sets. Since there are only four sets,  the  pigeonhole  principle  tells us  that  two of  the chosen numbers belong to the same set and these numbers add up to 9.   

Example 3 : Show that if any 11 numbers are chosen from the set  { 1 ,  2 ,  . . . , 20 }, then one of them 

                 will be a multiplier of another.

        Solution :  Create 10 or fewer pigeonhole in such a way that each number chosen can be assigned to only one pigeonhole, and when x and y are assigned to the same pigeonhole we are guaranteed that  either  x | y  or  y | x. Factors are a natural feature to explore. There are 8 prime numbers between 1 and 20, but knowing that x and y are multiples of the same prime will not guarantee that  either x | y  or  y | x.  There  are 10  prime  numbers  between 1 and  20.  Every positive integer  n  can be written as   n = 2 ^k m,  where  m  is odd and  k  ³  0.  This can be seen by

simply factoring all powers of 2 ( if any ) out of n. In this case, call m  the odd part of n. If  11 numbers are chosen from the set  { 1 , 2 , . . . , 20 }, then two of them must have the same odd part. This follows from the pigeonhole principle since there are 11 numbers ( pigeons ), but only 10 odd numbers between  1  and  20 ( pigeonholes ) that can be odd parts of these numbers.

     Let  n₁ and  n₂ be two chosen numbers with the same odd part,  then  n₁ = 2 ^k1 m  and n₂ = 2 ^k2 m,  for some k ₁ and k ₂.  If   k ₁  ³  k ₂ , then  n ₁  is a multiple  of  n ₂ ;  otherwise,  n ₂  is a multiple of n ₁.   

                                                          

Consider the region as shown. It is bounded by a regular hexagon whose sides are of length 1 unit. Show that if any seven points are chosen in this region, then two of them must be no farther apart than 1 unit.

Solution :

      Divide the region into six equilateral triangles as shown. If seven points are chosen in the region we can assign each of them to a triangle that contains it. If the point belongs to several triangles, arbitrarily assign it to one of them. Then the seven points are assigned to six triangular regions, so by the pigeonhole principle, at least two points must belong to the same region. These two cannot be more than one unit apart 

THE EXTENDED PIGEONHOLE PRINCIPLE

            If there are m pigeonholes and more than 2m pigeons, three or more pigeons will have to be assigned to ate least one of the pigeonholes. In general, if the number of pigeons is much larger than the number of pigeonholes, Theorem 1 can be restated to give a stronger conclusion.

            First a word about notation. If n and m are positive integers, then   ën / m û  stands for the largest integer less than or equal to the rational number  n /m. Thus  |_3 / 2 _|  is 1,  |_ 9 / 4 _|  is 2, and |_6 / 3 _| is 2.     

Theorem 2 : The extended pigeonhole principle.

            If  n pigeons are assigned  to m pigeonholes, then one of the pigeonholes must contain at least  

  ë ( n – 1 ) / m û  +  1  pigeons.

        Proof by contradiction :

                 If each pigeonhole contains no more than  ë ( n – 1 ) / m û  pigeons, then there are at most  m ×           

  ë ( n – 1 ) / m û  ≤ m × ( n – 1 ) / m  =  n – 1 pigeons in all. This contradicts our hypothesis, so one of the  

  pigeon holes must contain at least  ë ( n – 1 ) / m û  + 1  pigeons.

           This proof by contradiction uses the fact that there are two ways to count the total number of pigeons, the original count n and as the product of the number of pigeonholes times the number of pigeons per pigeonhole.

 Ex.  From an extension of example 1, Show that if any 30 people are selected, then one may choose a subset of five so that all five were born on the same day of the week.            

      Solution :

            Assign each person to the day of the week on which he or she was born. Then the 30 pigeons are being assigned to 7 pigeonholes. By the extended pigeonhole principle with  n = 30  and  m = 7, at least  ë ( 30 – 1 ) / 7 û  + 1  or  5 of the people must have been born on the same day of the week.

Ex.  Show that if 30 dictionaries in a library contain a total of  61 327 pages, then one of the dictionaries must have at least  2 045 pages.

    Solution :

            Let the pages be the pigeons and the dictionaries the pigeonholes. Assign each page to the

dictionary in which it appears. Then by the extended pigeonhole principle, one dictionary must contain at least   |_ 61326 / 30 _|   + 1  or  2045 pages.

 Exercises :

  1.  If thirteen people are assembled in a room, show that at least two of them must have their birthday in the same month.  

  2.  Show that if eight colors are used to paint 65 bicycles, at least nine bicycles will be the same color.   

  3.  Six friends discover that they have a total of  P  210.61  with them on their way to the canteen. Show  that one or more of them have at least  P  36.10.  

  4.  How many friends must you have to guarantee that at least four of them will have birthdays in the same month ?