The Pigeon Hole Principle — Some notes and examples

Reference: Discrete Mathematics and its Applications by Kenneth H. Rosen, Seventh Edition.

The Pigeonhole Principle 1:

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

Corollary: A function f from a set with k+1 or more elements to a set with k elements is NOT one-to-one.

Example 1:

Among any group of 367 people, there must be at least two with the same birthday because there are only 366 possible birthdays.

Example 2:

In any group of 27 English words, there must be at least two that begin with the same letter because there are 26 letters in the English alphabet.

Example 3:

How many students must be in a class to guarantee that at least two students receive the same score on the final exam, if the exam is graded on a scale from 0 to 100 points?

Solution:

There are 101 possible scores on the final. The pigeon hole principle shows that among any 102 students there must be at least 2 students with the same score.

The pigeonhole principle is a useful tool in many proofs, including proofs of surprising results, such as that given in the example below:

Example 4:

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 4:

Let n be a positive integer. Consider the n+1 integers 1, 11, 111,  \ldots, 11\ldots 1 (where the last integer in this list is the integer with n+1 1’s in its decimal expansion). Note that there are n possible remainders when an integer is divided by n. Because 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 of these integers less the smaller one is a multiple of n, which has a decimal expansion consisting entirely of 0’s and 1’s.

The Generalized Pigeonhole Principle:

The pigeonhole principle states that there must be at least two objects in the same box when there are more objects than boxes. However, even more can be said when the number of objects exceeds a multiple of the number of boxes. For instance, among any set of 21 decimal digits, there must be 3 that are the same. This follows because when 21 objects are distributed into 10 boxes, one box must contain more than 2 objects.

Statement of the Generalized Pigeonhole Principle:

If N objects are placed into k boxes, then there is at least one box containing at least \lceil N/k \rceil objects.

Some comments:

Please see wikipedia for properties of ceiling function. You can prove the above theorem by contradiction. Give it a try!

A common type of problem asks for the minimum number of objects such that at least r of these objects must be in one of the k boxes when these objects are distributed among the boxes. When we have N objects, the generalized pigeonhole principle tells us there must be at least r objects in one of the boxes as long as \lceil N/k \rfloor \geq r. The smallest integer N with N/k > r-1, namely, N=k(r-1)+1, is the smallest integer smallest integer satisfying the inequality \lceil N/k \rfloor\geq r. Could a smaller value of N suffice? The answer is no, because if we have k(r-1) objects, we could put r-1 of them in each of the k boxes and no box would have at least r objects.

When thinking about problems of this type, it is useful to consider how you can avoid having at least r objects in one of the boxes as you add successive objects. To avoid adding a rth object to any box, you eventually end up with r-1 objects in each box. There is no way to add the next object without putting an rth object in that box.

Examples 5-8 illustrate how the generalized pigeonhole principle is applied.

Example 5:

Among 100 people there are at least \lceil 100/12 \rceil = 9 who were born in the same month.

Example 6:

What is the minimum number of students required in a discrete mathematics class to be sure that at least six will receive the same grade, if there are five possible grades A, B, C, D, and F?

Solution 6:

The minimum number of students needed to ensure that at least six students receive the same grade is the smallest integer N such that \lceil N/5 \rceil = 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. Thus, 26 is the minimum number of students needed to ensure that at least six students will receive the same grade.

Example 7:

(a) How many cards must be selected from a standard deck of 52 cards to guarantee that at least three cards of the same suit are chosen?

(b) How many must be selected to guarantee that at least three hearts are selected?

Solution 7:

(a) Suppose there are four boxes, one for each suit, and as cards are selected they are placed in the box reserved for cards of that suit. Using the generalized pigeonhole principle, we see that if N cards are selected, there is at least one box containing at least \lceil N/4 \rceil cards. Consequently, we know that at least three cards of one suit are selected if \lceil N/4 \rceil \geq 3. The smallest integer N such that \lceil N/4 \rceil \geq 3 is N=2.4 +1=9, so nine cards suffice. Note that if eight cards are selected, it is possible to have two cards of each suit, so more than eight cards are needed. Consequently, nine cards must be selected to guarantee that at least three cards  of one suit are chosen. One good way to think about this is to note that after the eighth card is chosen, there is no way to avoid having  third card of some suit.

(b) We do not use the generalized pigeonhole principle to answer this question, because we want to make sure that there are three hearts, not just three cards one sort. Note that in the worst case, we can select all the clubs, diamonds, and spades, 39 cards in all, before we select a single heart. The next three cards will be all hearts, so we may need to select 42 cards to get three hearts.

Example 8:

What is  the least number of area codes needed to guarantee that the 25 million phones in a state can be assigned distinct 10 digit telephone numbers? (Assume that the telephone numbers are of the form NXX-NXX-XXXX, where the first three digits form the area code, N represents a digit from 2 to 9 inclusive, and X represents any digit).

Solution 8:

There are eight million different phone numbers of the form NXX-XXXX. Hence, by the generalized pigeonhole principle, among 25 million telephones , at least \lceil 25000000/8000000\rceil of them must have identical phone numbers. Hence, at least four area codes are required to ensure that all 10-digit numbers are different.

Quiz Question:

Suppose that a computer science lab has 15 workstations and 10 servers. A cable can be used to directly connect a workstation to a server. For each server, only one direct connection to that server can be active at any time. We want to guarantee that at any time any set of 10 or fewer workstations can simultaneously access different servers via direct connections. Although we could do this by connecting every workstation directly to every server (using 150 connections), what is the minimum number of direct connections needed to achieve this goal?

More later,

Nalin Pithwa.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s