Pigeonhole Principle: Theory, Examples, and Problem Solving

There are $12$ zodiac signs that we know. If we choose $12$ students, it is possible that all their zodiac signs are different, but if we choose $\boxed{12+1=13}$ students, it is guaranteed that at least $2$ students will have the same zodiac sign.
(Answer D)

Birth dates begin from $1$ and can go up to the $31$st. If we choose $3 \times 31 = 93$ people, it is possible that each set of $3$ people has the same birth date, but if we add $1$ more person, it is guaranteed that there will be $4$ people who have the same birth date.
Therefore, the required number of people is $\boxed{94}$ people.
(Answer C)

There are $12$ possible months. If each month contains $3$ students with the same birth month, then there will be $36$ students. Based on the pigeonhole principle, add one more student so that it is guaranteed there will be $4$ students who have the same birth month.
Therefore, the minimum number of students is $\boxed{37}$ people.
(Answer D)

Birth dates begin from $1$ and can go up to the $31$st. It is possible that $31$ students have different birth dates. Since there are $38$ students, the remaining $7$ students are assumed to have different birth dates as well, so at least $\boxed{2}$ students have the same birth month.
(Answer B)

There are $3$ grade levels in junior high school, namely grade $7$, grade $8$, and grade $9$. Since $\dfrac{111}{3} = 37$ (without remainder), it can be assumed that there are $37$ students in grade 7, $37$ students in grade 8, and $37$ students in grade $9$. This means that at least $37$ students are in the same grade level.
(Answer C)

There are $12$ birth months in the calendar. Since $\dfrac{119}{12} = 9$ with a remainder of $11,$ there will be at least $\boxed{9+1 = 10}$ children who were born in the same month.
(Answer B)

There are $7$ days in a calendar week. Since $\dfrac{1,000}{7} = 142$ with a remainder of $6$, we only need to assume that these $6$ people have different birth days. As a result, we find at least $\boxed{142+1=143}$ people with the same birth day.
(Answer C)

There are $26$ letters in the alphabet that we use (English alphabet). Since $\dfrac{100}{26} = 3$ with a remainder of $22,$ we only need to assume that these $22$ people have names with different initial letters. As a result, we find at least $\boxed{3+1=4}$ people who have names with the same initial letter.
(Answer B)

Examples of pairs of numbers whose sum is $28$ are $(8, 20),$ $(9, 19),$ $(10, 18),$ and so on, up to $(13, 15).$ Suppose we are in the worst possible condition. Take the numbers $1$ to $14.$ From these $14$ numbers, there is not yet a pair of numbers whose sum is $28.$ Furthermore, if one more number is taken from the choices $15$ to $20,$ there will certainly be a pair of numbers whose sum is $28.$ As an illustration, if the number $16$ is chosen, we obtain $(12, 16)$ as a pair of numbers whose sum is $28.$ Using the pigeonhole principle, the number of integers that must be selected so that there is guaranteed to be a pair of numbers whose sum is $28$ is $\boxed{14+1=15}$
(Answer D)

The pairs of numbers whose sum is $30$ are $(10, 20)$, $(11, 19)$, $(12, 18)$, $(13, 17)$, and $(14, 16)$. The numbers $21$ and so on up to $70$ do not have partners to form a sum of $30$, so we take them first (a total of $70-21+1 = \color{blue}{50}$ numbers). Next, we take the numbers $10$ to $15$ (there are $\color{red}{6}$ numbers, and still no pair summing to $30$ is found.)$ If we take one more number, whatever the number is, we obtain two numbers whose sum is $30$.
Therefore, the number of integers that must be selected is $\boxed{\color{blue}{50}+\color{red}{6}+1=57}.$
(Answer E)

By considering the worst-case condition, we select $n$ numbers from $2n$ numbers so that we do not obtain two numbers whose difference is $70.$
For this case, the value of $n = 70.$
From the numbers $1$ to $123$, choose the numbers $1, 2, \cdots, 70$ (a total of $70$ numbers). If we take any one more number, it is guaranteed that there will be a pair of numbers differing by $70$. Therefore, the minimum number of integers that must be selected is $\boxed{70+1=71}.$
(Answer C)

Assuming that we are in the worst possible condition, we obtain exactly $9$ cards for each number from $1$ to $20.$ Specifically for cards numbered $1$ to $8$, we take all the available cards according to the quantity in the box, while for cards numbered $9, 10, 11, \cdots, 20$ (there are 12 numbers), we take $9$ cards each. Therefore, we obtain
$\begin{aligned} & 1+2+3+\cdots+8+\underbrace{9+9+\cdots+9}_{\text{there are}~12} \\ & = (1+8) \times 4 + 12 \times 9 \\ & = 36 + 108 = 144. \end{aligned}$
Up to this point, we still have not obtained $10$ cards with the same number, but by taking one more card from the box, we are guaranteed to obtain them.
Therefore, at least $\boxed{144+1=145}$ cards must be taken.
(Answer C)

According to the pigeonhole principle, we must place ourselves in the worst-case condition when taking chopsticks. When we randomly take $52$ chopsticks, we obtain $52$ white chopsticks. This means we have already obtained $1$ pair of chopsticks that are not brown. Then, we take another $1$ chopstick and assume that we obtain $1$ brown chopstick. Finally, take $6$ more chopsticks and assume that we obtain $6$ yellow chopsticks.
Note: The case may be reversed. Assume we obtain $1$ yellow chopstick, then obtain $6$ brown chopsticks.
Thus, we have obtained 3 pairs of chopsticks that are not white.
Therefore, at least $\boxed{52+1+6 = 59}$ chopsticks need to be taken.
(Answer C)

First, let us determine the number of different possible answer patterns that students can produce.

1. There are $3$ questions with $2$ answer choices, so the number of different possible answers for the first section is $2^3 = 8.$
2. There are $5$ questions with $5$ answer choices, so the number of different possible answers for the second section is $5^5 = 3.125.$

Therefore, there are $8 \cdot 3.125 = 25.000$ possible different answer patterns. If there are $25.000$ students, it is still possible that no two students have exactly the same answers. According to the pigeonhole principle, one more student must be added to guarantee that there are two students with exactly the same answers. Therefore, the minimum number of students is $\boxed{25.001~\text{students}}.$
(Answer E)

Arrange two groups consisting of 5 girls and 1 boy to be placed in their seating positions around the circular table. Create the groups so that all children are completely covered, resulting in 8 groups consisting of 5 girls and 8 groups consisting of 1 boy (making exactly 48 children in total). Their seating positions will look like the picture.
Their seating positions are intentionally arranged alternately by groups so that there are no 6 girls sitting consecutively. Using the pigeonhole principle, add $1$ more girl so that there will definitely be $6$ girls sitting consecutively. Therefore, the minimum number of girls is $8 \cdot 5 + 1 = 41$ girls, while the rest are boys.
(Answer C)

Suppose we are in the worst possible condition. First, take the numbers that are not positive factors of $100.$ Since the factors of $100$ are $1, 2, 4, 5,$ $10, 20,$ $25, 50,$ and $100$ (there are $9$ of them), take all other numbers, namely $100-9 = 91$ numbers. Next, take the number $10$ because $10$ does not have a partner so that the product is $100.$ Up to this point, $92$ numbers have been selected. Finally, take the numbers $1, 2, 4,$ and $5$ so that the total number of selected integers becomes $92+4=96.$ If any one more number is selected, it can be guaranteed that we will find a pair of numbers whose product is $100.$ Therefore, the minimum number of integers that must be selected so that there is guaranteed to be a pair of numbers whose product is $100$ is $\boxed{96+1=97}.$
(Answer E)

Answer a)
In the worst-case situation, we take $6$ white balls and $5$ black balls, followed by taking one red ball. Therefore, the minimum number of balls that must be taken is $\boxed{6+5+1=12}.$

Answer b)
In the worst-case situation, we take $8$ red balls and $5$ black balls, followed by taking one white ball. Therefore, the minimum number of balls that must be taken is $\boxed{8+5+1=14}.$

Answer c)
In the worst-case situation, we take $8$ red balls and $6$ white balls, followed by taking $2$ black balls. Therefore, the minimum number of balls that must be taken is $\boxed{8+6+2=16}.$

Answer d)
In the worst-case situation, we take $6$ white balls, followed by taking $8$ red balls, and finally $2$ black balls. Therefore, the minimum number of balls that must be taken is $\boxed{6+8+2=16}.$

Answer e)
In the worst-case situation, we are assumed to take as many balls as possible first, namely $8$ red balls, then $6$ white balls, and finally only $1$ black ball. Therefore, the minimum number of balls that must be taken is $\boxed{8+6+1=15}.$

Answer a)
In the worst-case situation, we take $6$ pairs of yellow socks, $4$ pairs of red socks, and $3$ pairs of black socks. Then, only afterward do we take $1$ pair of purple socks.
Therefore, the minimum number of socks that must be taken to obtain a pair of purple socks is $\boxed{2(6)+2(4)+2(3)+2(1) = 28}.$

Answer b)
In the worst-case situation, we take $6$ pairs of yellow socks, $4$ pairs of red socks, and $5$ pairs of purple socks. Then, only afterward do we take $1$ pair of black socks.
Therefore, the minimum number of socks that must be taken to obtain a pair of black socks is $\boxed{2(6)+2(4)+2(5)+2(1) = 32}.$

Answer c)
In the worst-case situation, we take $6$ pairs of yellow socks, $5$ pairs of purple socks, and $3$ pairs of black socks. Then, only afterward do we take $3$ pairs of red socks.
Therefore, the minimum number of socks that must be taken to obtain $3$ pairs of red socks is $\boxed{2(6)+2(5)+2(3)+2(3) = 34}.$

Answer d)
In the worst-case situation, we are assumed to take the largest number of sock pairs first, namely $6$ pairs of yellow socks, then $5$ pairs of purple socks, followed by $4$ pairs of red socks, and finally only $1$ black sock (not a pair).
Therefore, the minimum number of socks that must be taken to obtain $4$ socks with different colors is $\boxed{2(6)+2(5)+2(4)+1 = 31}.$

The pairs of numbers that have a difference of $50$ are $(1, 51)$, $(2, 52)$, $(3, 53)$, $\cdots$, $(49, 99)$, and $(50, 100).$ We find that there are $50$ pairs. If we take exactly $50$ numbers, it is possible that we obtain the numbers $1, 2, 3, \cdots, 49, 50$ so that there is no pair of numbers with a difference of $50$. Based on the pigeonhole principle, take $50+1 =51$ numbers and it is guaranteed that there are $2$ numbers whose difference is $50.$ $\blacksquare$

By considering the worst-case condition, we select $n$ numbers from $2n$ numbers so that we do not obtain two numbers whose difference is $11.$

For this case, the value of $n = 9.$

1. From the numbers $1$ to $22$, the numbers $1, 2, \cdots, 11$ are selected.
2. From the numbers $23$ to $44$, the numbers $23, 24, \cdots, 33$ are selected.
3. From the numbers $45$ to $66$, the numbers $45, 46, \cdots, 55$ are selected.
4. From the numbers $67$ to $88$, the numbers $67, 68, \cdots, 77$ are selected.
5. From the numbers $89$ to $100$, the numbers $89, 90, \cdots, 99$ are selected.

The total number of selected numbers is $11+11+11+11+11=55,$ and no two numbers with a difference of $11$ are found.

By considering the worst-case condition, we select $n$ numbers from $2n$ numbers so that we do not obtain two numbers whose difference is $9.$

For this case, the value of $n = 9.$

1. From the numbers $1$ to $18$, the numbers $1, 2, \cdots, 9$ are selected.
2. From the numbers $19$ to $36$, the numbers $19, 20, \cdots, 27$ are selected.
3. From the numbers $37$ to $54$, the numbers $37, 39, \cdots, 45$ are selected.
4. From the numbers $55$ to $72$, the numbers $55, 56, \cdots, 63$ are selected.
5. From the numbers $73$ to $90$, the numbers $73, 74, \cdots, 81$ are selected.

From the numbers $91$ to $100$, all existing numbers are selected except $100.$ The total number of selected numbers is $9+9+9+9+9+9 =54.$ If one remaining number is randomly selected (whatever its value), it is guaranteed that there will be two numbers whose difference is $9$. Therefore, it is proven that there are at least $2$ numbers whose difference is $9$ when we randomly select $55$ numbers. $\blacksquare$

To obtain a pair of socks with the same color, we must take at least $2$ socks, but it still cannot be guaranteed that we obtain them.

Based on the pigeonhole principle, to guarantee obtaining a pair of socks with the same color, we only need to take at least $2 + 1 = 3$ socks.

If the eight integers are divided by $12$, then the possible remainders are $\{0,1,2,\cdots, 12\}$. Now prepare $7$ “boxes” and label them as follows.
$$\{0\}, \{1,11\}, \{2,10\}, \{3,9\}, \{4,8\}, \{5,7\}, \{6\}$$Then place the eight integers into the “boxes” according to their remainders when divided by $12$. Since there are $7$ boxes and $8$ integers, according to the pigeonhole principle, there is at least one box containing two integers. If that box is labeled $\{0\}$ or $\{6\}$, then the difference between the two integers is a multiple of $12$, for example the integers $6$ and $18$ in the box labeled $\{6\}$ (because their remainders when divided by $12$ are $6$) have a difference of $12$. On the other hand, if the box containing two integers is one of the other boxes, then the sum of those two integers is divisible by $12$, for example the integers $2$ and $22$ in the box labeled $\{2,10\}$ have a sum of $24$, which is a multiple of $12.$ $\blacksquare$

Given the set of numbers $\{1, 2, 3, \cdots, 100\}.$
Answer a)
Suppose we are in the worst possible condition. Take the numbers $50$ through $100.$ Among these $\color{red}{51}$ numbers, there are still no three numbers satisfying $a+b = c.$ This happens because the sum of any two numbers among them definitely exceeds $100.$ Next, if one more number is selected from the numbers $1$ through $49,$ then there will certainly exist three numbers $a, b,$ and $c$ such that $a+b=c.$ For example, if the number $1$ is selected, we obtain the triple $(1, 50, 51).$ If the number $15$ is selected, we obtain the triple $(15, 50, 65).$ Therefore, at least $\boxed{51 + 1 = 52}$ numbers must be selected so that the desired condition is guaranteed to occur.
Answer b)
Suppose we are in the worst possible condition. Take the numbers $33$ through $100.$ Among these $\color{red}{68}$ numbers, there are still no four numbers satisfying $a+b+c=d.$ This happens because the sum of any three numbers among them definitely exceeds $100$ (the smallest possible sum is $33+34+35 = 102 > 100$). Next, if one more number is selected from the numbers $1$ through $32,$ then there will certainly exist four numbers $a, b, c,$ and $d$ such that $a+b+c=d.$ For example, if the number $1$ is selected, we obtain the quadruple $(1, 33, 34, 68).$ If the number $23$ is selected, we obtain the quadruple $(23, 33, 34, 90).$ Therefore, at least $\boxed{68+1=69}$ numbers must be selected so that the desired condition is guaranteed to occur.

Take any positive integer $n.$ We will show that there exists a multiple of $n$ whose digits consist only of $0$ and $1.$
Suppose we have $(n+1)$ positive integers, namely $1, 11, 111, \cdots, \underbrace{111…111}_{\text{there are}~n+1}.$ Observe that when an integer is divided by $n,$ there are $n$ possible remainders, namely $0, 1, 2, 3, \cdots, n-1.$ Since we have $(n+1)$ numbers, according to the pigeonhole principle, there are at least $2$ numbers having the same remainder when divided by $n,$ say $A$ and $B$ with $A > B.$ The number $A-B$ is a multiple of $n$ whose digits consist only of $0$ and $1.$ $\blacksquare$

Illustration: Suppose we want to check whether there exists a multiple of $6$ whose digits consist only of $0$ and $1.$ Construct $7$ numbers, namely $1, 11, 111,$ $1.111, 11.111,$ $111.111,$ and $1.111.111.$ The remainders of these seven numbers when divided by $6$ are respectively $1, 5, 3, 1, 5, 3,$ and $5.$ We simply choose two numbers having the same remainder, for example $1$ and $1.111.$ Observe that their difference, $1.111-1 = 1.110,$ is a multiple of $6$ whose digits consist only of $0$ and $1.$

Every integer $n \ge 1$ can be expressed in the form $n = 2^a \cdot b$ where $b$ is the greatest odd factor. Among the $2n$ numbers in the set, there are $n$ distinct odd numbers. Using the pigeonhole principle, if we choose $(n+1)$ distinct numbers from the set, at least two of them must have the same greatest odd factor. Suppose those two numbers are $n_1 = 2^x \cdot b$ and $n_2 = 2^y \cdot b$ so that clearly $n_1 \mid n_2$ if $n_2 \ge n_1$ or $n_2 \mid n_1$ if $n_1 \ge n_2.$ $\blacksquare$

The idea we use is the fact that every positive integer can be written as the product of a power of $2$ and an odd number (taken as large as possible). Example: $30 = 2 \times 15$ and $40 = 2^3 \times 5.$
Suppose we have $n+1$ positive integers, namely $a_1, a_2, \cdots, a_n, a_{n+1}.$ Express all these numbers in the form $a_j = 2^{k_j} \cdot q_j$ for $j = 1, 2, \cdots, n+1$ where $k_j$ is a nonnegative integer and $q_j$ is an odd integer. The integers $q_1, q_2, \cdots, q_{n+1}$ are positive odd integers whose values are less than $2n.$ However, there are only $n$ distinct positive odd integers less than $2n.$ According to the pigeonhole principle, there are at least two equal odd integers among $q_1, q_2, \cdots, q_{n+1}.$ In other words, there exist distinct integers $i$ and $j$ such that $q_i = q_j.$ Let $q = q_i = q_j$ so that $a_i = 2^{k_i} \cdot q$ and $a_j = 2^{k_j} \cdot q.$ Consequently, if $k_i < k_j,$ then $a_i$ divides $a_j.$ Conversely, if $k_j < k_i,$ then $a_j$ divides $a_i.$
Therefore, it is proven that among $n+1$ positive integers whose values do not exceed $2n$, there is always an integer that divides another integer. $\blacksquare$

Let $a_i$ be the number of sparring sessions completed by the boxer up to week-$i$ for $i = 1,2,3,\cdots, 75$, so that we obtain
$1 \leq a_1 < a_2 < a_3 < \cdots < a_{75} \leq 125$
and by adding $24$ to each side, we obtain
$$25 \leq a_1 + 24 < a_2+24< \cdots < a_{75} + 24 \leq 149.$$Since there are $149$ integers counted from $1$ to $149,$ while $a_1,a_2,\cdots, a_{75}, a_1+24,$ $a_2+24, \cdots, a_{75}+24$ consist of $75+75=150$ numbers, according to the pigeonhole principle, there are at least $2$ equal numbers in the sequence, namely there exist $i$ and $j$ such that $a_i = a_j +24.$
In other words, during weeks $j+1,j+2,\cdots, i$, the boxer has exactly $24$ sparring sessions. $\blacksquare$