Pigeonhole Principle

Pigeonhole Principle
Field: Other
Image Created By: mathilluminated
Website: mathilluminated

Pigeonhole Principle

A pigeon is looking for a spot in the grid, but each box or pigeonhole is occupied. Where should the poor pigeon on the outside go? No matter which box he chooses, he must share with another pigeon. Therefore, if we want all of the pigeons to fit into the grid, there is definitely a pigeonhole that contains more than one pigeon. This concept is commonly known as the pigeonhole principle. The pigeonhole principle itself may seem simple but it is a powerful tool in mathematics.

Basic Description

If more than $n$ pigeons are put into $n$ pigeonholes, then at least one pigeonhole must contain more than one pigeon. This is the famous pigeonhole principle.

A more general version of pigeonhole principle is that for any non-empty finite setIn mathematics, a set is a collection of distinct objects and a finite set is a set that has a finite number of elements. For example, $\{2,4,6,8,10\}$ is a finite set with five elements. of real numbers, the maximum value is at least the average value.

Consider the main image of putting pigeons into pigeonholes instead. We have only $n$ pigeonholes but more than $n$ pigeons; the average value of pigeons per pigeonhole, $\frac{pigeons}{pigeonholes}$, is greater than one. Thus, the maximum value of the number of pigeons in a pigeonhole should be greater than one as well, which means that there must be at least two pigeons in a pigeonhole. Now we know that the two versions are actually talking about the same mathematical principle.

The pigeonhole principle is also called the Dirichlet principle, named after a German mathematician Johann Dirichlet. Dirichlet was the first person who formalized this idea in 1834. At that time, Dirichlet named it Schubfachprinzip (drawer principle or shelf principle in English), so Dirichlet's box principle, Dirichlet's drawer principle also refer to pigeonhole principle.

Pigeonhole principle can solve lots of seemingly unbelievable statements. Even though some statements seem out of order, they are actually connected inside and sometimes we need the pigeonhole principle to find the hidden connections.

Interesting Applications

Here are 6 real world applications to give you a better grasp of this famous principle.

1. Birthday

Two or more people in a college have the same birthday (the particular year is not considered).

As we know, there are 366 possible days in a year (including leap year) and a college usually has more than 367 students.

In the most extreme condition when each of the first 366 students have their birthdays on different days from January 1st to December 31th, the birthday of the 367th person must be a repeat of one of those days. Thus, there are definitely two of the students who have their birthday falling on the same day.

In fact, we can view this problem as there are at least 367 pigeons (students in a college) but 366 pigeon holes (the most days during a year). According to the pigeonhole principle, at least two pigeons share the same pigeonhole (at least two people share the same birthday).

---

2. A Pair of Socks

Assume you have 10 orange socks and 10 blue socks and you want to find a matching pair of socks from a random pick. You will only need to pick three socks.

Translate the statement like this: you have 2 holes (2 kinds of color) but 3 pigeons (3 socks). By the pigeonhole principle, at least two pigeons have the same pigeonhole or at least two socks must be of the same color.

You can also think of it step by step. If the second sock you pick matches the first, you find the matching pair. If not, then one sock must be blue and the other one orange. You pick the third sock and it is either blue or orange. Whichever it is, you can always find a matching pair.

---

3. A Suit of Cards

Pick 5 cards from a standard deck of 52 cards, and at least two cards will be of the same suit.

Each of the five cards can belong to one of the four suits. So we have five pigeons (five cards) here but four pigeonholes (four suits). By the pigeonhole principle, if four of the cards each belongs to the four suits, then the fifth card has to belong to the same suit as one of the four cards.

There is a more mathematical way to think about this statement. The average value = $\frac{5}{4}$ so the maximum must be at least that, and since we can't pick a fraction of a card, there must be at least two cards of the same suit.

---

4. Hair

At any given time in New York City there live at least two people who have the same amount of hairs on their head.

A human has a maximum of about 500,000 hairs. In comparison, there are millions of people in New York, which outnumbers the number of hairs a human normally has. By pigeonhole principle, at least two of them must have the same number of hairs.

More mathematically, the average value = $\frac{\mbox{the number of people}}{\mbox{the amount of hairs}}$ is bigger than one, and since we cannot find a fraction of a person, there must be at least 2 people have the same amount of hairs.

This example may sound impossible to believe, but the seemingly obvious pigeonhole principle tells us it must be true.

---

5. Chairs

If 9 people are seated in a row of 12 chairs, then some consecutive set of 3 chairs are filled with people.

[Click to show proof]

As is shown in the figure below, there are 9 people who want to sit on the chairs. We have 9 people and 12 chairs, which leaves us with 3 empty chairs. [...]

[Click to hide proof]

As is shown in the figure below, there are 9 people who want to sit on the chairs. We have 9 people and 12 chairs, which leaves us with 3 empty chairs.

Wherever the 3 empty chairs are, they will always partition the 9 filled chairs into 4 groups of consecutive filled chairs. The first two examples below show two ways of partitioning the chairs without two empty chairs next to each other..

• 

  Example 1 - how the 3 empty chairs separate the 9 filled chairs into 4 groups

• 

  Example 2 - how the 3 empty chairs separate the 9 filled chairs into 4 groups

Note that if two empty chairs are next to each other, we can consider there to be a group of filled chairs in between; it's just that this group has 0 filled chairs (Example 3). If the empty chair is at one of the two ends of this row, we also say that there exists a group with 0 filled chairs at that end (Example 4). No matter how you place the 3 empty chairs even if they are side by side, the filled chairs will be split into four groups.

• 

  Example 3 - how the 3 empty chairs separate the 9 filled chairs into 4 groups

• 

  Example 4 - how the 3 empty chairs separate the 9 filled chairs into 4 groups

So, we want to put 9 people in four groups. The average value of the number of peoples per group, $\frac{people}{groups}$, is $\frac{9}{4}$. Recall that the maximum value is at least the average value for any non-empty finite set of real numbers. Because $3 > \frac{9}{4} > 2$, one of the four groups must have at least 3 filled chairs.

---

6. Strangers or Friends

In a room with six people in it, there will always be either 3 people who know each other or 3 people who don't know each other.

[Click to show proof]

This seems to be a chaotic problem but we need to find order in this mess. Note that these people are randomly chosen, so there will probably be a jumb [...]

[Click to hide proof]

We can use a diagram to help us show that this statement is true. Note that these people are randomly chosen, so there will probably be a jumble of friends and strangers in the room. To make the explanation clear, denote the six people as six points of a hexagon. Draw lines joining every pair of two points, and color the lines pink if the two are friends, green if they are strangers. Then it make look like this:

What the statement graphically means is that we can always find a pink triangle (3 mutual friends) or a green triangle (3 mutual strangers) in this hexagon. For instance, there is a pink triangle ADE and a green triangle BFE.

Since there are over 32,000 possible colorings, we could not draw and check every one of the situations. Then let's take a look at a smart and efficient way.

Consider any point of the six: it can connect to five other points with five lines coming out of it. The lines are either pink or green, so we have 2 pigeonholes (2 colors) and 5 pigeons (5 lines). By the pigeonhole principle, the average value is $\frac{\mbox{lines}}{\mbox{colors}} = \frac{5}{2} = 2.5$, so the maximum value is at least 3. In other words, at least 3 lines must have the same color and let's suppose the color is pink (it doesn't matter which color has more lines, the result will be the same). To sum up, we suppose that there are at least 3 pink lines coming out of a single point (Figure 1.1).

• 

  Figure 1.1

• 

  Figure 1.2

We will have four points connected by the three pink lines (Figure 1.2). This generates three potential triangles, each with two pink lines already. What about the third line of the three triangles? If we color any of the three remaining lines pink, then we have a pink triangle, which means that there are three people who are friends and know each other (Figure 2.1, Figure 2.2, Figure 2.3). Otherwise, the three third lines make a green triangle (Figure 3). Either way, we get a triangle with three sides the same color, which means that we can always find three people in a group of six who either know each other or don't know each other at all.

• 

  Figure 2.1 - pink triangle

• 

  Figure 2.2 - pink triangle

• 

  Figure 2.3 - pink triangle

• 

  Figure 3 - green triangle

A More Mathematical Explanation

Note: understanding of this explanation requires: *Combinatorics

[Click to view A More Mathematical Explanation]

More Mathematical Examples

1. Choose 51 numbers from integers between 1 and 100 inclusiv [...]

[Click to hide A More Mathematical Explanation]

More Mathematical Examples

1. Choose 51 numbers from integers between 1 and 100 inclusively. Then there must be two consecutive numbers of among the chosen integers.

We divide the 100 integers in pairs,

$(1, 2), (3, 4), (5, 6), (7, 8), (9, 10), \cdots, (97, 98), (99, 100).$

There are 50 pigeonholes (pairs) and 51 pigeons (chosen numbers). By the pigeonhole principle, the average value = $\frac{pigeons}{pigeonholes}= \frac{51}{50}$, so the maximum value is at least 2. There are definitely two pigeons share the same hole. Therefore, we can definitely find two numbers that are a pair of consecutive numbers among the 51 chosen numbers.

2. If you pick 5 integers from 1 to 8, you will definitely find two of them must add up to 9.

No matter which integer you choose, you can always pair it with another integer from 1 to 8 to sum to 9. Thus, there are four such pairs overall:

$\left \{1, 8\right \}, \left \{2, 7\right \}, \left \{3, 6\right \}, \left \{4, 5\right \} .$

We are going to stuff five pigeons (chosen integers) into four pigeonholes (pairs). By the pigeonhole principle, the average value = $\frac{pigeons}{pigeonholes} = \frac{5}{4}$, so the maximum value is at least 2. Two of the integers must be from the same pair, which sums to 9.

3. Given any $n$ positive integers, there must exist two integers whose difference can be exactly divided by $n - 1$.

Denote the $n$ numbers as $a_1, a_2, a_3, \cdots, a_n$. Let $r_n$ be the remainder that results from dividing $a_n$ by $n-1,~~$ where $0 \leq r_n \leq n-2$. Because of the bounds ($0$ and $n - 2$), there are $n-1$ possible values (pigeonholes) for each $r_n$, but there are $n ~~ r_n$'s (pigeons). Thus, by the pigeonhole principle, the average value = $\frac{pigeons}{pigeonholes} = \frac{n}{n-1}$, so the maximum value is at least 2. There must be two of the $r_n$'s that are the same such that

$r_i = r_j$

for some positive integers $i$ and $j$.

Thus, their corresponding $a_i$ and $a_j$

$a_i = q_i (n - 1) + r_i$ (where $q_i$ is the quotient; it's an integer)

$a_j = q_j (n - 1) + r_i$ (where $q_j$ is the quotient; it's an integer)

have the same remainder when divided by $n-1$, and so the difference $a_i - a_j$ is divisible by $n -1$.

$a_i - a_j = \left ( q_i (n - 1) + r_i \right ) - \left ( q_j (n - 1) + r_i \right )$

$a_i - a_j = q_i (n - 1) + r_i - q_j (n - 1) - r_i$

$a_i - a_j = q_i (n - 1 ) - q_j (n - 1) + r_i - r_i = (q_i - q_j) (n -1)$ ($q_i - q_j$ is an integer)

Therefore, among $n$ given integers, we definitely will find two integers whose difference can be exactly divided by $n-1$.

[Show A More Concrete Example][Hide A More Concrete Example]

Given 10 positive integers $1, 2, 5, 7, 8, 12, 13, 24, 35, 45$, there must exist two integers whose difference can be exactly divided by 9.

Proof:

Denote the 10 numbers as:

$a_1 = 1, ~a_2 = 2, ~a_3 = 5, ~a_4 =7, ~a_5 = 8, ~a_6 = 12,~ a_7 = 13, ~a_8 = 24,~ a_9 =35,~ a_{10} = 45.$.

Divide each number by 9 and get the remainder.

$r_1 = 1, ~r_2 = 2, ~r_3 = 5,~ r_4 = 7,~ {\color{Blue}r_5 = 8},~ r_6 = 3,~ r_7 = 4, ~r_8 = 6, ~{\color{Blue}r_9 = 8}, ~r_{10} = 0.$

The remainders range from 0 to 8. There are 10 remainders above but only 9 possible values for each remainder. By pigeonhole principle, there must be two of the remainders that are the same such that $r_5 = r_9 =8$. Thus, their corresponding $a_5 = 8, a_9 = 35$ have the same remainder when divided by 9, and so the difference $a_9 - a_5 = 27$ is divisible by 9.

How to Construct Pigeonholes

Sometimes, "pigeons" and "pigeonholes" are abstract and not so easy to find. In order to find the clues, we can draw a diagram for the problem. The examples below will show you how pigeonholes can be constructed.

Examples

1. We are given a $9 \times 3$ rectangle divided into 27 squares as shown below. If we paint all of the smaller squares either blue or red, we will always find a rectangle whose four corners are of the same color no matter how we paint these squares.

• 

  Figure 4 - a rectangle divided into 27 squares

• 

  Figure 5 - a random example. Do you find a rectangle with corners of the same color? See the solution by clicking the hidden proof.

[Click to show proof]

Try to color the rectangles to see how it always works. If you paint them randomly, you will find that there are always two columns that are the sam [...]

[Click to hide proof]

Try to color the rectangles to see how it always works. If you paint them randomly, you will find that there are always two columns that are the same. This is our solution.

[Show Solution to Figure 5][Hide Solution to Figure 5]

Figure 6 - eight possible ways to color a column

Since we have to deal with $27$ squares, let's narrow it down. If we look at the big rectangles by columns, we only have $8$ possible ways to paint a column as Figure 6 shows. This is because each column has three small squares and each square can be painted two possible colors. Thus, $2^3 = 8$.

There are $8$ ways to paint a column (pigeonholes) but $9$ columns (pigeons). By the pigeonhole principle, the average value = $\frac{pigeons}{pigeonholes} = \frac{9}{8}$, so the maximum value has to be at least 2. There are at least two columns painted exactly the same.

In each of the two identical columns, we have three squares (pigeons) and two colors (pigeonholes) that we can use. Apply the pigeonhole principle again and we will find that there must be two squares in each column painted the same color. Therefore, the two squares in the same color in each of the identical columns could form the desired rectangle.

2. There are 18 students in a school and they have to choose 4 courses from among 15 different courses. Then two students will find that they take two of the same courses together.

[Click to show proof]

Since the conclusion is about two common courses, we treat the two courses as a whole to avoid working on two courses. This will make it easier to defi [...]

[Click to hide proof]

Since the conclusion is about two common courses, we treat the two courses as a whole (a course pair) to avoid working on two courses separately. This would make it easier to define pigeonholes.

Then, let's figure out what are the pigeons and what are the pigeonholes. Because this problem is about course choosing, the pigeonholes are course pairs available to choose and pigeons are course pairs chosen by all of the students. In this case, if a student picks one kind of combination, then he or she puts a pigeon into this pigeonhole.

• Pick $2$ courses from $15$ available ones, and we can find $C^{15}_2 = \frac{15!}{2!~13!} = \frac{15\times 14}{2 \times 1} = 105$ combinations of course pairs. In other words, we can find 105 pigeonholes.

[Show More about Combinations][Hide More about Combinations]

The combination notation, $C^{n}_r$, represents the number of possible combinations of $r$ objects from a collection of $n$ objects.

$C^{n}_r = \frac{n!}{r! (n -r)!} = \frac{n \cdot (n -1) \cdot (n -2) \cdots (n - r + 1)}{r!}$

Example: $C^{11}_4 = \frac{11!}{4!~7!} = \frac{11 \times 10 \times 9 \times 8}{4 \times 3 \times 2 \times 1}.$

• Pair up the $4$ courses each student chooses and we can know that each student has $C^4_2 =\frac{4!}{2! ~ 2!} = \frac{4\times3}{2\times 1} = 6$ combinations of course pairs. Overall there are $6 \times 18 = 108$ total course pairs chosen by all of the students (that is, there are $108$ pigeons).

To sum up, the students have $108$ pigeons and they put them into $105$ pigeonholes. According to the pigeonhole principle, the average value = $\frac{pigeons}{pigeonholes} = \frac{108}{105} < 2$, so the maximum is at least 2. There must be two pigeons in one pigeonhole, which means that two students choose the same pigeonhole (the same two courses).

3. Choose 51 numbers from integers from 1 to 100. Then there are definitely two distinct chosen integers such that one is a multiple of the other.

[Click to show proof]

To apply the pigeonhole principle, we need to divide the 100 integers into groups, constructing pigeonholes with certain amount. If we put integers wit [...]

[Click to hide proof]

To apply the pigeonhole principle, we need to divide the 100 integers into groups. So we need to put integers with the same quality in a group as we did in previous problems. For this problem, we are going to create 50 groups with any two numbers in each group satisfying the condition such that one is a multiple of the other. The problem is: how should we divide them? Since this problem is about multiples, let's put integers with the same common divisor together.

Consider the $50$ odd numbers from $1$ to $99: \left \{1, 3, 5, 7, \cdots, 97, 99\right \}$. For each odd number ${n},$ we create a set $\left \{2n, 4n, 8n, \cdots, 2^i n\right \}$ (where $i$ represents positive integers starting at 1 and stopping when $2^i n$ becomes greater than 100 ). Thus, we get

For $n = 1,$ we have $\left \{1, 2, 4, 8, \cdots, 64\right \}$. The set stops at 64 because the next one is going to be $2^7 \times 1= 128 > 100$.

For $n = 3,$ we have $\left \{3, 6, 12, 24, \cdots, 96\right \}$. It stops at 96 because the next one is going to be $2^6 \times 3 = 64 \times 3 = 192 > 100$.

For $n = 5,$ we have $\left \{5, 10, 20, 40, \cdots, 80\right \}$. It stops at 80 because the next one is going to be $2^5 \times 5 = 32 \times 5 = 160 > 100.$

$\cdots ~ \cdots$

For $n = 97,$ we have $\left \{97\right \}$. There is only 97 itself because the next one is going to be $2^1 \times 97 = 194 > 100$.

For $n = 99,$ we have $\left \{99\right \}$. There is only 99 itself because the next one is going to be $2^1 \times 99 = 198 > 100$.

In this way, we divide the 100 integers into 50 disjoint groups where numbers of each group are multiples of each other. Because each group represents a pigeonhole, we have 50 pigeonholes but 51 pigeons (chosen integers) to put into the pigeonholes. By the pigeonhole principle, the average value = $\frac{pigeons}{pigeonholes} = \frac{51}{50}$, so the maximum value is at least 2. Two of the chosen integers must be in the same group. In other words, the larger number is a multiple of the smaller one.

Summary

Based on the examples discussed above, hopefully you have a better understanding of how to construct pigeonholes. Think about how many possible ways you can find in the problem; this is your restriction and also the pigeonholes you are trying to find.

• In the first example, the restriction is 8 because there are only 8 possible ways to color a column consisting of three squares.

• In the second example, if two students choose two common courses, then this pair of courses is definitely one of the 105 combinations. Thus, the restriction is 105.

• In the last example, the restriction ends up being 50 because only 50 distinct groups can be made; there are only 50 odd numbers for integers from 1 to 100.

You can also find inspiration on how to solve the problem from the conclusions in each statement.

• For Example 1, a rectangle with corners the same color suggests you to think of two identical columns because you will definitely find such rectangle with two identical columns.

• For Example 2, two common courses suggest you to treat them as a whole and choose 2 from 15 courses, reminding you to use combinations.

• For Example 3, knowing that one must be a multiple of the other tells you how to divide up the 100 integers.

Therefore, please pay attention to every conclusion because they help a lot!

How to Find the Bounds

So far, we have only been told to prove the statements but one may wonder whether we have reached the lower bound or not. For example, could the $9 \times 3$ rectangle be smaller and still satisfy the condition? This leads to the interesting question of how to find the lower bounds.

Since we want to prove that a number is the best lower bound, the basic idea is to show that a smaller number leads to a contradiction or an error.

Examples

1. In a room with 6 people in it, there will always be three people who either know each other or don't know each other.

[Click to show proof]

We've proved that the statement is true. Now think about this question: at least how many people do we need to make sure that there are three mutual fr [...]

[Click to hide proof]

We've proved that the statement is true. Now think about this question: at least how many people do we need to make sure that there are three mutual friends or three mutual strangers? This kind of question is related to Ramsey Number. The minimum number of people needed to insure three mutual friends or mutual strangers is denoted as $R (3, 3)$. We know that 6 works, so let's think about 5. It turns out that 5 is impossible because of the image below:

This counterexample tells us that 5 people doesn't always work. So since it can't be less than six people, $R (3, 3) = 6$.

Why It's Interesting

There are more real world applications of the pigeonhole principle.

---

Shaking Hands

There are $n$ people in a party and $n$ is more than 1 so they can shake hands with one another at will. You will always find two people who shake hands with the same number of people.

In this case, the pigeonhole is hands shaken and pigeons are people. Because you can never shake hands with yourself, you only could shake $n -1$ other people's hands, for a total of at most $n -1$ handshakes. So there are $n-1$ possible numbers of handshakes for a given person, and $n$ possible people: more pigeons than pigeonholes. According to the pigeonhole principle, the average value $\frac{pigeons}{pigeonholes} = \frac{n}{n - 1}$ is greater than 1 but smaller than 2, so the maximum must be at least 2. At least two people have the same handshake numbers.

$\blacktriangleright$ Please note that if you shake hands with a person, this person is also shaking hands with you. Handshaking is mutual.

$\blacktriangleright$ This is not an easy example to understand. To solve hard problems like this, we need to know how to construct "pigeons" and "pigeonholes." (See section How to Construct Pigeonholes)

---

Taking Medicine

A person is told to take at least one aspirin a day and $m$ aspirin in all over a $n$ day period. Then there definitely will be a period of consecutive days where he takes exactly $m-n-1$ aspirin in total. (Assume that $3n>2m-1 > 2n$.)

Denote $a_r$ as the cumulative number of aspirin taken by day $n$. $a_r$ is increasing every day because he takes at lest one aspirin every day. And since the total number of aspirin is $m$, we have

$1 \leqslant a_1 < a_2 < \cdots < a_{n} = m$.

In order to prove there is a period of consecutive days where the person takes $m - n - 1$ aspirin in total, we have to prove that the equation $a_i + (m - n - 1) = a_j$ is true for some $i < j$. So we first add $m - n - 1$ to every term in the inequality above:

$(m - n) \leqslant a_1 + (m - n - 1) < a_2 + (m - n - 1) < \cdots < a_{n} + (m - n - 1) = (2m - n - 1)$

From the two inequalities above we can find $2n$ integers overall: $n$ from the first inequality $a_1, ~a_2, ~a_3, ~\cdots, ~a_{n},$ and $n$ from the second inequality $~ \Big(a_1 + (m - n - 1)\Big), ~ \Big(a_2 + (m - n - 1)\Big), ~ \Big(a_3 + (m - n - 1)\Big), ~\cdots, ~\Big((a_{n} + (m - n - 1)\Big)$.

We also know that the $2n$ integers have non-decreasing values from 1 to $2m - n - 1$. Hence, there are $2n$ numbers (pigeons) with $2m - n - 1$ possible values (pigeonholes) to assign to.

According to the pigeonhole principle, the average value = $\frac{pigeons}{pigeonholes} = \frac{2n}{2m - n -1}$. This average value is smaller than 2 but greater than 1, since we assumed that $3n>2m-1> 2n$, which is equivalent to saying that $2n > 2m-n-1 > n$. Thus, the maximum value should be at least 2 and two of the integers must be the same.

Which two numbers? Can any two of the $2n$ integers be the same?

The answer is no. Because the person takes at least one aspirin everyday, the sequence in the first inequality is increasing. So those first $n$ terms cannot be equal and it is the same for those in the second inequality. Therefore, we must have one value from the first group $~a_1, ~a_2,~ a_3, ~\cdots, ~a_{n}$ equal to one of the values from the second group $\Big(a_1 + (m - n - 1)\Big), ~\Big(a_2 + (m - n - 1)\Big), ~\Big(a_3 + (m - n - 1)\Big), ~\cdots, ~\Big(a_{n} + (m - n - 1)\Big)$. Therefore, $a_i + (m - n - 1) = a_j$ for some $i<j$, which is what we wanted to prove.

---

Dominoes on a Chess Board

Assume we remove two of the diagonally opposite corners of a chess board. Then it is impossible to cover the chess board with dominoes whose size is two board squares each.

The two opposite squares on the diagonal of a chess board have the same color. Thus, there are two more squares of one color than that of another color after the corners are removed (See the figure below).

However, each domino piece covers two squares of exactly two different colors. Every time you put a domino piece (a pigeon) on the chess board, you cover 1 white square and 1 black square. But we don't have the same amount of white and black squares (pigeonholes) on the board. Some squares will be left. By the pigeonhole principle, we can never cover the whole board with dominoes whose size is two board squares each.

---

Do I Know You?

In a room with $n$ people in it, there must be at least two people who know the same number of people.

For a single person, he or she could know from $0$ to $n-1$people (can't include himself or herself), so there are $n$ possible numbers. Thus, if we want everyone to have different numbers of acquaintances, one has to have $n-1$ and one $0$ acquaintances. This is a contradiction. If one knows $n-1$ people, then the person knows everyone in the room. Since acquaintanceship is a symmetric non-reflexive relationship, the other people must know at least one person. Hence, there couldn't be a person who has $0$ acquaintances if there is one who knows $n-1$ people.

Teaching Materials

There are currently no teaching materials for this page. Add teaching materials.

References

[1] Dijkstra, Edsger W. The Strange Case of The Pigeon-hole Principle. Retrieved from http://www.cs.utexas.edu/users/EWD/transcriptions/EWD09xx/EWD980.html.

[2] Ramsey Theory. Retrieved from http://www.learner.org/courses/mathilluminated/units/2/textbook/06.php.

[3] Talwalkar, Presh. 16 fun applications of the pigeonhole principle. Retrieved from http://mindyourdecisions.com/blog/2008/11/25/16-fun-applications-of-the-pigeonhole-principle/.

[4] Bogomolny, Alexander. Pigeonhole Principle. Retrieved from http://www.cut-the-knot.org/do_you_know/pigeon.shtml.

[5] Leader, Imre. Friends and strangers. Retrieved from http://plus.maths.org/content/friends-and-strangers.

[6] The Pigeon Hole Principle. Retrieved from http://zimmer.csufresno.edu/~larryc/proofs/proofs.pigeonhole.html.

[7] Bautista. The Pigeonhole Principle. Retrieved from http://www.math.admu.edu.ph/~banjo/ajss/Pigeonhole.pdf.

[8] Pigeonhole Principle. Retrieved from http://www.mathdb.org/notes_download/elementary/combinatorics/de_D4.pdf.

Future Directions for this Page

1. There is a helper page linked to this page, Ramsey Number. It is not fully done, so please pick it up and investigate more! Thanks.
   

---

If you are able, please consider adding to or editing this page!

Have questions about the image or the explanations on this page?
Leave a message on the discussion page by clicking the 'discussion' tab at the top of this image page.