The Pigeonhole Principle

The Pigeonhole Principle

The Pigeonhole Principle

It states that if there are more pigeons (objects) than the pigeonholes (boxes), then some pigeonhole (box) must contain two or more pigeons (objects). The pigeohole principle is also called the Dirichlet drawer principle or Shoe box principle.

The pigeonhole principle itself is trivial but when applied cleverly, it can yield non trivial results. The pigeonhole principle is sometime useful in counting methods.

To apply the principle one has to decide objects (pigeons) and categories of the desired characteristic (pigeonholes) and be able to count the number of objects and the number of pigeonholes. Ofcourse, this principle also applies to other objects besides pigeons and pigeonholes.

Note that the pigeonhole. principle tells us nothing about how to locate the pigeonhole that contains two or more pigeons. It only asserts the existence of a pigeonhole containing two or more pigeons.

Theorem The pigeonhole principle       [A.U N/D 2012]

If k is a positive integer and k + 1 or more objects are placed into k boxes, then there is atleast one box containing two or more of the objects.

Proof : We prove this principle by the method of contradiction. Suppose that none of the k boxes contains more than one object. Hence. the total number of objects would be atmost k. This is a contradiction, since there are atleast k + 1 objects.

Corollary

A function ƒ from a set with k + 1 or more elements to a set with k elements is not one-to-one.

Proof: Suppose each element y in the codomain of f we have a box that contains all elements x of the domain of f such that f(x)=y. Since the domain contain k + 1 or more elements and the co-domain contains only k elements, by the pigeonhole principle one of these boxes contains two or more elements x of the domain. This means that f cannot be one-to-one.

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

Proof : We will prove this principle using a proof by contradiction. Suppose each pigeonhole contains atmost one pigeon. Then atmost m pigeons have been assigned. But since m <n, not all pigeons have been assigned pigeonholes. This is a contradiction.

Atleast one pigeonhole contains two or more pigeons.

Theorem: The generalization / extension of the pigeonhole principle.

If k pigeons are assigned to n pigeonholes, then one of the pigeonholes must contain atleast [k-1/n] + 1 pigeons.

Proof: If possible, suppose that none of the pigeonholes contains more than [k-1/n]pigeons. Then there will be atmost

n[k-1/n] ≤ n k-1/n = k - 1 pigeons.

This is a contradiction to the assumption that there are n pigeons.

Theorem: If n objects are placed into k boxes, then there is atleast one box containing atleast n/k objects.

Proof: Assume that none of the boxes contains more than [n/k] - 1 objects.

The total number of objects is atmost.

k[(n/k) – 1] < k [(n/k + 1) – 1] = n, where the inequality [n/k] < [n/k] + 1 has been used. This is a contradiction, because there are a total of n objects.

Example 1: Give two examples based on pigeonhole principle.

Solution :

1. Among any group of 367 people, there must be atleast two with the same birthday, because there are only 366 maximum possible birth days.

2. In any group of 27 English words, there must be atleast two that starts with the same letter, since there are 26 letters in English alphabet.

Example 2: Show that among 13 children, there are atleast two children who were born in the same month.

Solution: Let us assume that 13 children as pigeons and the 12 months (January, ... December) as the pigeonholes then by the pigeonhole principle there will be atleast two children who were born in the same month.

Example 3 Show that if any four numbers from 1 to 6 are chosen, then two of them will add to 7.

Solution: Let us form 3 sets containing two numbers whose sum is 7.

A = {1, 6}, B = {2, 5}, C = {3, 4}.

The four numbers that will be chosen to the set that contains it.

As there are only 3 sets, two numbers that there chosen is from the set whose sum is 7.

Example 4: Show that among any group of five (not necessarily consecutive) integers, there are two with the same remainder when divided by 4.

Solution: Take any group of five integers. When these are divided by 4 each have some remainder. Since there are five integers and four possible remainders when an integer is divided by 4, the pigeonhole principle implies that given five integers, atleast two have the same remainder.

Example 5: A bag contains 12 pairs of socks (each pair is in different color). If a person draws the socks one by one at random, determine atmost how many draws are required to get atleast one pair of matched socks.

Solution: Let n denote the number of the draw. For n ≤ 12, it is possible that the socks drawn are of different colors, since there are 12 colors. For n 13, all socks cannot have different colors atleast two must have the same color. Here 13 as the number of pigeons and 12 colors as 12 pigeonholes. Thus, atmost 13 draws are required to have atleast one pair of socks of the same color.

Example 6: Show that for every integer n there is a multiple of n that has only 0 s and 1 s in its decimal expansion.

Solution: Let n be a positive integer.

Consider the n + 1 integers 1, 11, 111, …. . There are n possible

remainders when an integer is divided by n. Since there are n+1 integers in this list, by the pigeonhole principle there must be two with the same remainder when divided by n.

The larger number of these integers less the smaller one is a multiple of n, which has a decimal expansion consisting entirely of 0s and 1s.

Example 7: Prove the statement : If m = k_n+1 pigeons (where k ≥ 1) occupy n pigeonholes then atleast one pigeonhole must contain k+ 1 or more pigeons.

Solution: Let us assume that the conclusion of the given statement is false.

Then every pigeonhole contains k or less number of pigeons. Then, the total number of pigeons would be nk. This is a contradiction. Hence, the assumption made is wrong, and the given statement is true.

Example 8: Let n₁, n₂ … n_t be possible integes. Show that if n₁ + n₂ + … + n_t – t + 1 objects are placed int t boxes, then for some i, i = 1, 2, ... t the i^th box contains atleast n_j objects.

Solution: Assume that the conclusion part of the given statement is false. Here n₁, n₂,… are pigeons t boxes are pigeonholes. Then every hole contains n_j-1 or less number of pigeons, j = 1, 2, ... n. Then the total number of pigeons would be less than or equal to

(n₁-1) + (n₂-1) + ... + (n_t − 1) = (n₁ + n₂ + ... + n_t − t)

= m - 1

This is a contradiction. Since the number of pigeons is equal to m. Hence the assumption made is wrong, and the given statement is true.

Example 9: Show that if seven colors are used to paint 50 cars, atleast eight cars will have the same colour.

Solution: Assume that 50 cars (pigeons) are assign 7 colors (pigeonholes). Hence, by the generalised pigeonhole principle, atleast [50-1/7] + 1 = 8 cars will have the same colour.

Example 10: Show that among any n + 1 positive integers not exceeding 2n there must be an integer that divides one of the other integers.

Solution: Let the (n + 1) integers be a₁, a₂, … a_n+1 as power of 2 times an odd integer. Let a_j = 2^kj q_j for j =1, 2, … n + 1, where k_j is a non-negative integer and q_j is odd. The integers q₁, q₂, .... q_n+1 are all odd positive integers less than 2n. Since there are only n odd positive integers less than 2n. From the pigeonhole principle that two of the integers q₁, q₂, ... q_n+1 must be equal.

There are integers i and j such that q_j = q_j. Let q be common value of q_i and q_j. Then, a_i = 2^ki q and a_j =2^kj q.

From this k₁ < k_j, then a_j divides a_j ; while if k₁ > k_j, then a_j divides a_i.

Example 11: Seven members of a family have total Rs. 2,886 in their pockets. Show that atleast one of them must have atleast Rs. 416 in his pocket.

Solution: Let us assume

members - → pigeonholes

Rupees - → pigeons

Now 2886 pigeons are to be assigned to 7 pigeonholes.

Using the extended pigeonhole principle

(i.e.,) k-1/n + 1 where k = 2886, n = 7

2886-1 /7 +1 = 416

Hence, there are 416 rupees in one member's pocket.

Example 12: If 9 books are to be kept in 4 shelves, there must be atleast one shelf which contain atleast 3 books.

Solution : Let us assume

books - → pigeons

shelves - → pigeonholes

Now 9 pigeons are to be assigned to 4 pigeonholes.

Using the extended pigeonhole principle

k-1/n + 1 when k = 9, n = 4

9-1/4 + 1 = 8/4 +1 = 3

Hence there are 3 books in one shelf atleast.

Example 13: How many people must you have to guarantee that atleast 9 of them will have birthdays in the same day of the week.

Solution: Let us assume that

the days week - → pigeonholes

people - → pigeons

Now 7 pigeonholes and we have to find pigeons.

Using the extended pigeonhole principle,

k-1/n + 1 where n = 7, to find k.

k-1/7 + 1 = 9

k-1+7/7 = 9

k+6 = 63

k = 63-6 = 57

Thus, there must be 57 people to guarantee that atleast 9 of them will have birthdays in the same day of the week.

Example 14: Show that if 30 dictionaries in a library contain a total of 61327 pages, then one of the dictionaries must have atleast 2045 pages.

Solution : Let us assume that

pages - → pigeons

dictionaries - → pigeonholes

Assign each page to the dictionary in which it appears. Then by extended pigeonhole principle, one dictionary must contain atleast 

k-1/n + 1 pages, when k = 61327, n = 30

= 61327–1/30 + 1 = 2045 pages.

Example 15: ABC is an equilateral triangle whose sides are of length 1 cm each. If we select 5 points inside the triangle, prove that atleast two of these points are such that the distance between them is less than 1/2 cm.

Solution: Consider the triangle DEF formed by the mid-points of the sides BC, CA and AB of the given triangle ABC. Then the triangle ABC is partitioned into four small equilateral triangles (portions), each of which has sides equal to 1/2 cm.

Considering each of these four portions as a pigeonhole and five points chosen inside the triangle as pigeons, we find by using the pigeonhole principle that atleast one portion must contain two or more points. Clearly, the distance between such points is less than 1/2 cm.

Example 16: What is the maximum number of students required in a mathematics class to be sure that atleast six will receive the same grade, if there are five possible grades. A, B, C, D and F?       [A.U N/D 2012]

Solution: The minimum number of students wanted to ensure that atleast six students receive the same grade is the smaller integer N such that [N/5] = 6. The smallest such integer is N = 5.5+1 = 26. If you have only 25 students, it is possible for there to be five who have received each grade so that no six students have received the same grade.

226 is the minimum number of students needed to ensure that atleast six students will receive the same grade.

Example 17: How many persons must be chosen in order that atleast five of them will have birth days in the same calendar month?

Solution: Let n be the required number of persons. Because the number of months over which the birthdays are distributed is 12, the least number of persons who have their birthdays in the same month, is by the generalized pigeonhole principle, equal to [ (n-1)/12] + 1.

This number is 5, if [(n − 1)/12] + 1 5, or n = 49.

Thus, the number of persons is 49 (at the least).

Example 18: Find the least number of ways of choosing three different numbers from 1 to 10 so that all choices have the same sum

Solution: From the numbers from 1 to 10, we can choose three different numbers in C (10, 3) = 120 ways.

The smallest possible sum that we get from a choice is 1+2+3=6 and the largest sum is 8+ 9+ 10 = 27. Thus, the sums vary from 6 to 27 (both inclusive), and these sums are 22 in number.

Accordingly, here ther are 120 choices (pigeons) and 22 sums (pigeonholes). Therefore the least number of choices assigned to the same sum is by the generalized pigeonhole principle.

[120 – 1/ 22] + 1 = (6.4) ≈ 6.

Example 19: Show that if any 5 numbers from 1 ot 8 are chosen, then two of them will have their sum equal to 9.

Solution: Let us consider the following sets :

A₁ = {1, 8}, A₂ = {2, 7}, A₃ = {3, 6}, A₄ = {4, 5}

These are the only sets containing two numbers from 1 to 8, whose sum is 9.

Because every number from 1 to 8 belongs to one of the above sets, each of the 5 numbers chose must belong to one of the sets.

Since there are only 4 sets, two of the 5 chosen numbers have to belong to the same set (by the pigeonhole principle).

These two numbers have their sum equal to 9.

EXERCISE 2.4

1. Show that in any eight positive integers are chosen two of them will have same remainder when divided by 7.

2. Show that atleast two people must have their birthday in the same month if 13 people are assembled in a room.

3. What is the minimum number of students, each of whom comes from one of the 50 states, who must be enrolled in a university to guarantee that there are atleast 100 who come from the same state ?    [Ans. 4951]

4. A drawer contains a dozen brown socks and a dozen black socks, all unmatched. A man takes socks out at random in the dark.

(a) How many socks must he take out to be sure that he has atleast two socks of the same color?

(b) How many socks must he take out to be sure that he has atleast two black socks ?    [Ans. (a) 3, (b) 14]

5. How many numbers must be selected from the set {1, 2, 3, 4, 5, 6} to guarantee that atleast one pair of these numbers add up to 7?    [Ans. 4]

6. There are 38 different time periods during which classes at a university can be scheduled. If there are 677 different classes, how many different rooms will be needed?   [Ans. 18]

7. Construct a sequence of 16 positive integers that has no increasing or decreasing sub sequence of five terms.

[Ans. 4, 3, 2, 1, 8, 7, 6, 5, 12, 11, 10, 9, 16, 15, 14, 13]

8. Show that in a group of 10 people (where any two people are either friends or enemies), there are either three mutual friends or four mutual enemies, and there are either three mutual enemies or four mutual friends.

9. Show that if five integers are selected from the first eight positive integers, there must be a pair of these integers with a sum equal to 9. Is the conclusion true if four integers are selected rather than five?

10. A company stores products in a warehouse. Storage bins in this warehouse are specified by their aisle, location in the aisle, and shelf. There are 50 aisles, 85 horizontal locations in each aisle, and 5 shelves throughout the warehouse. What is the least number of products the company can have so that atleast two products must be stored in the same bin? [Ans. 21, 251]

11. Show that if any five numbers from 1 to 8 are chosen, then two of them will have their sum equal to 9.

12. Prove that every set of 37 positive integers contains atleast two integers that leave the same remainder upon division by 36.

13. Show that if 9 colors are used to paint 100 houses atleast 12 houses will be of the same color.

14. Fiind the minimum number of students in a class to be sure that four out of them born in the same month.

15. Show that in any set of eleven integers, there are two whose difference is divisible by 15.

16. A drawer contains ten black and ten white socks. What is the least number of socks one must pull out to be sure to get a matched pair?

17. Let A be some fixed 10 element subset of {1, 2, 3, ...50}. Show that A possesses two different 5-element subset, the sums of whose element are equal.

18. In a group of 13 children, there must be least two children who were born in the same month.

19. Show that if any five integers from 1 to 8 are chosen, then atleast two of them will have a sum 9.

20. Show that in any room of people who have been doing handshaking there will always be atleast two people who have shaken hands the same number of times.

21. Prove that if any 30 people are selected, then we may choose a subset of 5 so that all 5 were born on the same day of the week.

22. Suppose there are 26 students and 7 cars to transport them. Then atleast one car must have 4 or more passengers.