Pigeonhole principle

This chapter introduces the Pigeonhole Principle, a fundamental combinatorial technique for proving existence by mapping elements to categories. Mastering its basic and strong forms, along with advanced applications in extremal counting, is crucial for solving a wide range of problems frequently encountered in CMI examinations.

---

Chapter Contents

| Topic |

|---|-------| | 1 | Basic pigeonhole | | 2 | Strong pigeonhole | | 3 | Extremal counting applications |

---

We begin with Basic pigeonhole.

Part 1: Basic pigeonhole

Basic Pigeonhole

Overview

The pigeonhole principle is one of the simplest ideas in combinatorics, but in serious problems it appears in disguised forms: repeated values, repeated remainders, repeated states of a process, equal subset sums, and bounded trajectories. In CMI-style questions, the difficulty is usually not the statement of the principle, but identifying what the objects are and what the boxes are. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

Apply the basic and generalized pigeonhole principles correctly.

Detect hidden pigeonholes such as residues, intervals, and bounded states.

Use repeated-value arguments in sequences and processes.

Convert a counting problem into an object-box framework.

Build subset-sum and equal-value conclusions using pigeonhole reasoning.

---

Core Idea

📖 Basic Pigeonhole Principle

If more than $n$ objects are placed into $n$ boxes, then at least one box contains at least two objects.

📐 Generalized Pigeonhole Principle

If $N$ objects are placed into $m$ boxes, then at least one box contains at least

$\qquad \left\lceil \dfrac{N}{m} \right\rceil$

objects.

This is the version used in most exam problems. ---

The Real Skill

❗ What Counts as an Object and What Counts as a Box?

In many problems, the objects are not physical objects. They can be:

numbers

remainders

subset sums

positions in a process

values of a sequence

intervals

colors

The boxes can also be disguised:

possible residues modulo $m$

a bounded set of states

possible birthdays, months, or labels

possible sums in a restricted range

---

Standard Forms

📐 Most Common Pigeonhole Patterns

Repeated remainder

- Among

n+1

integers, two have the same remainder modulo

n

Repeated value in a bounded set

- If a sequence takes more values than the number of allowed states, some value repeats.

At least one large box

- If

N

objects are distributed among

m

boxes, some box gets at least

\left\lceil N/m \right\rceil

objects.

Equal subset sums

- If more subsets are formed than the number of possible sums, two distinct subsets must have the same sum.

---

Minimal Worked Examples

Example 1 Among

13

people, prove that at least two are born in the same month. There are

13

people and only

12

months. So there are more objects than boxes. Hence at least two people are born in the same month. --- Example 2 If

17

balls are placed into

4

boxes, prove that some box contains at least

5

balls. By the generalized pigeonhole principle,

\qquad \left\lceil \dfrac{17}{4} \right\rceil = \left\lceil 4.25 \right\rceil = 5

So some box contains at least

5

balls. ---

Repeated Remainders

📐 Residue-Class Version

When integers are divided by $m$ , there are only $m$ possible remainders:

$\qquad 0,1,2,\dots,m-1$

So if you have more than $m$ integers, at least two must have the same remainder modulo $m$ .

This is one of the most useful disguised forms of pigeonhole. ---

Bounded-State Version

❗ A Key CMI Theme

Suppose a sequence or process can only take values from a finite set of size $M$ .

If the process produces more than $M$ terms, then at least two of those terms must be equal.

This is exactly the hidden structure in many olympiad- and CMI-style sequence problems.

If the possible values are integers from

-n+1

k

, then the total number of possible values is

\qquad k-(-n+1)+1 = n+k

So any sequence with more than

n+k

terms must repeat a value. ---

Prefix-Sum and Equal-Sum Method

📐 Equal Sums from Equal Prefix Values

Suppose a sequence of numbers gives rise to cumulative sums

$\qquad s_0,s_1,s_2,\dots,s_r$

If two of these are equal, say $s_i=s_j$ with $i<j$ , then

$\qquad s_j-s_i=0$

which means the sum of the terms from step $i+1$ to step $j$ is zero.

This is a very common way pigeonhole creates nonempty subsets with equal total or zero total.

This is especially relevant when:

sums stay within a bounded interval

there are more prefix sums than available values

equal states imply equal partial totals

---

Subset-Sum Pigeonhole

❗ Another Powerful Pattern

If many different subsets are formed but only few possible sums are available, then two distinct subsets must have the same sum.

This often leads to:

equal subset sums

a zero-sum difference of two subsets

existence of nonempty subsets with prescribed total

---

PYQ-Relevant Insight

💡 What the Given PYQ Is Really Testing

The PYQ you gave uses pigeonhole in a deeper way:

First show the process values $t_j$ lie in a bounded interval.

Then count how many distinct values are possible.

If the sequence has more terms than available values, some value repeats.

Equal repeated values then produce equal sums from two different parts of the process.

So the problem is not just “more objects than boxes”; it is:

objects = sequence positions or prefix states

boxes = allowed integer values of the state

---

Common Mistakes

⚠️ Avoid These Errors

❌ Saying “by pigeonhole” without identifying objects and boxes

❌ Forgetting to count the number of boxes correctly

❌ Using $\dfrac{N}{m}$ instead of $\left\lceil \dfrac{N}{m} \right\rceil$

❌ Treating repeated values as useless, instead of converting them into equal-sum information

❌ Ignoring the possibility of hidden pigeonholes such as residues or state values

---

CMI Strategy

💡 How to Attack Pigeonhole Problems

Ask: what are the objects?

Ask: what are the boxes?

Count the boxes carefully.

If the problem involves a process, bound the possible states.

If two states repeat, subtract them to extract structural information.

If subsets are involved, compare the number of subsets to the number of possible sums.

---

Practice Questions

:::question type="MCQ" question="If

19

objects are placed into

6

boxes, then some box must contain at least" options=["

3

","

4

","

5

","

6

"] answer="B" hint="Use the generalized pigeonhole principle." solution="We compute

\qquad \left\lceil \dfrac{19}{6} \right\rceil = \left\lceil 3.166\ldots \right\rceil = 4

So some box contains at least

4

objects. Hence the correct option is

\boxed{B}

." ::: :::question type="NAT" question="Among

11

integers, what is the minimum number that must have the same remainder when divided by

5

?" answer="3" hint="There are only

5

possible remainders." solution="The possible remainders modulo

5

are

\qquad 0,1,2,3,4

so there are

5

boxes. If

11

integers are distributed among these

5

remainder classes, then some class contains at least

\qquad \left\lceil \dfrac{11}{5} \right\rceil = 3

integers. Therefore the answer is

\boxed{3}

." ::: :::question type="MSQ" question="Which of the following are standard uses of the pigeonhole principle?" options=["Proving two numbers have the same remainder modulo

m

","Proving a bounded-state sequence repeats a value","Showing some quantity strictly decreases each step","Showing two distinct subsets can have the same sum if the number of subsets is too large"] answer="A,B,D" hint="Pigeonhole needs more objects than boxes." solution="1. True. Remainders give boxes.

True. Finite possible states act as boxes.

False. That is a monovariant idea, not pigeonhole.

True. If there are more subsets than possible sums, two subsets must share a sum.

Hence the correct answer is

\boxed{A,B,D}

." ::: :::question type="SUB" question="Prove that among any

n+1

integers, there exist two whose difference is divisible by

n

." answer="True by equal remainders modulo

n

" hint="Classify the integers by their remainders modulo

n

." solution="When an integer is divided by

n

, the possible remainders are

\qquad 0,1,2,\dots,n-1

so there are exactly

n

remainder classes. Now consider any

n+1

integers. These are

n+1

objects placed into

n

boxes, where the boxes are the possible remainder classes modulo

n

. By the pigeonhole principle, two of these integers must have the same remainder modulo

n

. If two integers have the same remainder modulo

n

, then their difference is divisible by

n

. Hence among any

n+1

integers, there exist two whose difference is divisible by

n

. Therefore the answer is

\boxed{\text{True by equal remainders modulo } n}

." ::: ---

Summary

❗ Key Takeaways for CMI

The pigeonhole principle is about forcing repetition when possibilities are too few.

The hardest step is identifying the right objects and boxes.

Remainders, bounded states, and subset sums are common hidden pigeonholes.

Repeated values often lead to equal-sum or equal-difference conclusions.

Generalized pigeonhole uses the ceiling value $\left\lceil \dfrac{N}{m} \right\rceil$ .

---

💡 Next Up

Proceeding to Strong pigeonhole.

---

Part 2: Strong pigeonhole

Strong Pigeonhole

Overview

The strong pigeonhole principle is the sharpened form of the basic pigeonhole idea. It does not merely guarantee that some box gets two objects; it gives a precise lower bound on how many objects must lie in one box. In olympiad and CMI-style problems, this topic appears in counting, divisibility, remainders, birthday-type questions, and extremal reasoning. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

State and use the strong pigeonhole principle correctly.

Convert “at least one box has many objects” into a sharp threshold formula.

Solve minimum-number guarantee questions.

Recognize disguised pigeonholes such as remainders, parity classes, or intervals.

Use ceiling-form and contrapositive-form reasoning confidently.

---

Core Statement

📖 Strong Pigeonhole Principle

If $N$ objects are placed into $k$ boxes, then at least one box contains at least

$\qquad \left\lceil \dfrac{N}{k} \right\rceil$

objects.

📐 Equivalent Threshold Form

To guarantee that some box contains at least $m$ objects, it is enough and necessary to have

$\qquad (m-1)k+1$

objects distributed among $k$ boxes.

Reason: If every box had at most

m-1

objects, then the total number of objects would be at most

\qquad k(m-1)

So with one more object, some box must have at least

m

. ---

Most Important Forms

📐 Three Standard Forms

Ceiling form

\qquad \text{some box has at least } \left\lceil \dfrac{N}{k} \right\rceil

Threshold form

\qquad (m-1)k+1 \Rightarrow \text{some box has at least } m

Contrapositive form

If every box has at most

m-1

objects, then total objects

\le k(m-1)

---

How to Spot the Pigeonholes

💡 Common Hidden Boxes

The “boxes” are often not physical boxes. They may be:

months of the year

weekdays

residue classes mod $n$

parity classes

intervals

colors

possible sums or remainders

categories in a partition of a set

The first real step is always: What are the boxes? What are the objects? ---

Standard Consequences

📐 Very Useful Consequences

Among $N$ integers, two have the same remainder modulo $k$ if $N \ge k+1$

Among $N$ people, two have birthdays in the same month if $N \ge 13$

To force at least $m$ objects in one of $k$ classes, you need $(m-1)k+1$ objects

If $N$ objects are split among $k$ groups, one group has size at least $\lceil N/k \rceil$

---

Minimal Worked Examples

Example 1 What is the minimum number of students needed to guarantee that at least

4

students were born in the same month? There are

12

months, so

k=12

boxes. To force at least

4

in one box, we need

\qquad (4-1)\cdot 12 + 1 = 37

So the answer is

\boxed{37}

. --- Example 2 If

41

balls are placed into

8

boxes, then some box contains at least

\qquad \left\lceil \dfrac{41}{8} \right\rceil = \left\lceil 5.125 \right\rceil = 6

balls. So the guaranteed minimum is

\boxed{6}

. ---

Common Traps

⚠️ Avoid These Errors

❌ Using $\dfrac{N}{k}$ instead of $\left\lceil \dfrac{N}{k} \right\rceil$

❌ Forgetting that the result is a guarantee, not the exact distribution

❌ Choosing the wrong pigeonholes

❌ Using $mk$ instead of $(m-1)k+1$ in threshold questions

❌ Confusing “at least one box has $\ge m$ ” with “every box has $\ge m$ ”

---

CMI Strategy

💡 How to Attack Strong Pigeonhole Problems

Identify the objects and the boxes.

Ask whether the problem is a ceiling question or a minimum guarantee question.

For guarantee questions, try the worst-case arrangement first.

If the problem asks for the least number, distribute as evenly as possible without violating the target.

Use the contrapositive form when direct reasoning looks messy.

---

Practice Questions

:::question type="MCQ" question="What is the minimum number of objects needed to guarantee that at least

5

of them lie in the same box when there are

8

boxes?" options=["

32

","

33

","

34

","

40

"] answer="B" hint="Use the threshold formula

(m-1)k+1

." solution="To guarantee at least

5

objects in one of

8

boxes, we use

\qquad (m-1)k+1 = (5-1)\cdot 8 + 1 = 33

Hence the correct option is

\boxed{B}

." ::: :::question type="NAT" question="Among

19

integers, what is the least number you can guarantee have the same parity?" answer="10" hint="There are only two parity classes." solution="Parity gives

2

boxes: even and odd. By the strong pigeonhole principle, among

19

integers, some parity class contains at least

\qquad \left\lceil \dfrac{19}{2} \right\rceil = 10

integers. Hence the answer is

\boxed{10}

." ::: :::question type="MSQ" question="Which of the following statements are true?" options=["If

25

objects are placed in

6

boxes, then some box contains at least

5

objects","To guarantee that some box among

10

boxes contains at least

4

objects,

31

objects are sufficient","If

20

objects are placed in

5

boxes, then some box contains exactly

4

objects","Among

13

integers, two must have the same remainder upon division by

6

"] answer="A,B,D" hint="Use ceiling form, threshold form, and remainder classes." solution="1. True, since

\left\lceil \dfrac{25}{6} \right\rceil = 5

True, because

(4-1)\cdot 10 + 1 = 31

False. Strong pigeonhole guarantees at least

4

, not exactly

4

True. There are only

6

remainder classes modulo

6

, and

13>6

Hence the correct answer is

\boxed{A,B,D}

." ::: :::question type="SUB" question="Prove that if

(m-1)k+1

objects are distributed among

k

boxes, then some box contains at least

m

objects." answer="By contradiction using the maximum possible total if each box has at most

m-1

objects." hint="Assume every box has at most

m-1

objects and count the total." solution="Assume, for contradiction, that no box contains

m

or more objects. Then every box contains at most

m-1

objects. Since there are

k

boxes, the total number of objects is at most

\qquad k(m-1)

But the actual number of objects is

\qquad (m-1)k+1

which is strictly greater than

k(m-1)

. This is impossible. Hence our assumption is false, so at least one box must contain at least

m

objects. Therefore the statement is proved." ::: ---

Summary

❗ Key Takeaways for CMI

The strong pigeonhole principle guarantees a box with at least $\left\lceil \dfrac{N}{k} \right\rceil$ objects.

The minimum number to force at least $m$ objects in one of $k$ boxes is $(m-1)k+1$ .

The hidden difficulty is usually identifying the correct boxes.

Worst-case distribution is the standard way to find minimum guarantees.

Strong pigeonhole gives a lower bound guarantee, not an exact distribution.

---

💡 Next Up

Proceeding to Extremal counting applications.

---

Part 3: Extremal counting applications

Extremal Counting Applications

Overview

Extremal counting problems ask you to focus on the largest, smallest, most crowded, or least crowded object in a counting setup. In many olympiad-style and CMI-style questions, this topic works together with the pigeonhole principle: instead of trying to track every object, we identify an extremal one and force a useful conclusion. ---

Learning Objectives

❗ By the End of This Topic

After studying this topic, you will be able to:

Use the pigeonhole principle in strongest possible form.

Translate words like at least, at most, guaranteed, minimum possible maximum, and maximum possible minimum into counting statements.

Solve distribution problems using extremal reasoning.

Recognise when a problem is asking for a sharp lower bound or upper bound.

Apply partitioning ideas to prove the existence of repeated patterns or close values.

---

Core Idea

📖 Extremal Principle in Counting

The extremal principle means: instead of studying all objects equally, choose one object with an extreme property, such as:

the box with the most objects

the box with the fewest objects

the largest chosen number

the smallest chosen number

the most frequent residue class

the most crowded interval

Then use that extreme choice to force a conclusion.

📖 Strong Pigeonhole Principle

If $N$ objects are distributed among $k$ boxes, then:

some box contains at least $\left\lceil \dfrac{N}{k} \right\rceil$ objects

some box contains at most $\left\lfloor \dfrac{N}{k} \right\rfloor$ objects

This is one of the main tools in extremal counting. ---

The Two Main Extremal Questions

📐 Type 1: Minimum Guaranteed Maximum

If $N$ objects are placed into $k$ boxes, then the minimum number guaranteed in some box is

$\qquad \left\lceil \dfrac{N}{k} \right\rceil$

This is the smallest possible value of the largest occupancy.

📐 Type 2: Maximum Guaranteed Minimum

If $N$ objects are placed into $k$ boxes, then the largest number guaranteed in every box is at most

$\qquad \left\lfloor \dfrac{N}{k} \right\rfloor$

This is the largest possible value of the smallest occupancy.

---

Standard Extremal Patterns

📐 Patterns to Recognise

Same remainder / same parity / same month / same colour

Partition the objects into classes.

Two numbers close together

Partition into short intervals or adjacent pairs.

A repeated sum or difference

Group by residues or complementary pairs.

Crowded box or crowded interval

Use the strongest pigeonhole estimate.

Impossible equal spreading

Show that perfectly even distribution is impossible, so one place must exceed the average.

---

Fast Formulas

📐 Most Used Estimates

If $N > k$ , then some box has at least $2$ objects.

If $N > rk$ , then some box has at least $r+1$ objects.

If $N$ objects are divided into $k$ classes, some class has at least $\left\lceil \dfrac{N}{k} \right\rceil$ objects.

If $N$ objects are divided into $k$ consecutive pairs, choosing more than $k$ objects forces one full pair.

---

Minimal Worked Examples

Example 1 Among

37

students, show that at least

4

have birthdays in the same month. There are

12

months. If each month had at most

3

students, then total students would be at most

\qquad 12 \cdot 3 = 36

But there are

37

students. So some month has at least

4

students. This is also

\qquad \left\lceil \dfrac{37}{12} \right\rceil = 4

--- Example 2 Choose

6

distinct numbers from the set

\{1,2,3,\dots,10\}

. Show that two of them sum to

11

. Partition the set into

5

complementary pairs:

\qquad (1,10),\ (2,9),\ (3,8),\ (4,7),\ (5,6)

Choosing

6

numbers from

5

pairs forces at least one pair to be chosen completely. That pair sums to

11

. ---

How to Build the Boxes

💡 The Most Important Step

In extremal counting, the main difficulty is usually not the formula. It is choosing the right boxes.

Common good choices:

residue classes modulo $m$

parity classes

complementary pairs

short intervals

months, weekdays, colours, digits, positions

---

Sharpness and Best Possible Answers

❗ Why Ceiling Appears

Suppose you want to know the least number guaranteed in the fullest box.

If $N$ objects were spread as evenly as possible among $k$ boxes, the largest box would still have size

$\qquad \left\lceil \dfrac{N}{k} \right\rceil$

So this is not just a bound — it is the exact best possible guarantee.

---

Common Mistakes

⚠️ Avoid These Errors

❌ Using $\dfrac{N}{k}$ directly when the answer must be an integer

✅ Use ceiling or floor carefully

❌ Choosing the wrong classes or boxes

✅ The partition must match the property you want to force

❌ Forgetting that pigeonhole gives an existence statement, not the exact location

✅ It proves some box has the desired property

❌ Confusing “at least one box has...” with “every box has...”

✅ Read the conclusion carefully

---

CMI Strategy

💡 How to Attack Extremal Counting Problems

Ask: what is the thing I want to force?

Partition the objects into classes matching that target.

Count how many classes there are.

Compare the number of chosen objects with the number of classes.

Use the ceiling form when the problem asks for a guaranteed minimum in the most crowded class.

---

Practice Questions

:::question type="MCQ" question="If

29

objects are placed into

7

boxes, then at least one box must contain at least" options=["

3

","

4

","

5

","

6

"] answer="C" hint="Use the strong pigeonhole principle." solution="We compute

\qquad \left\lceil \dfrac{29}{7} \right\rceil = \left\lceil 4+\dfrac{1}{7} \right\rceil = 5

So at least one box must contain at least

\boxed{5}

objects. Hence the correct option is

\boxed{C}

." ::: :::question type="NAT" question="From the set

\{1,2,3,\dots,20\}

, if

11

numbers are chosen, then at least how many of them must have the same parity?" answer="6" hint="There are only two parity classes." solution="There are only two parity classes: even and odd. If each class had at most

5

chosen numbers, then the total number of chosen numbers would be at most

10

. But

11

numbers are chosen. Therefore some parity class must contain at least

\boxed{6}

numbers." ::: :::question type="MSQ" question="Which of the following are true?" options=["If

N

objects are placed into

k

boxes, some box contains at least

\lceil N/k \rceil

objects","If

17

integers are chosen, some two must have the same remainder when divided by

16

","If

8

distinct numbers are chosen from

\{1,2,\dots,14\}

, then some two are consecutive","If

10

objects are placed into

10

boxes, every box must contain exactly one object"] answer="A,B,C" hint="Think in terms of classes and pairs." solution="1. True. This is the strong pigeonhole principle.

True. There are only

16

residue classes modulo

16

True. Pair the numbers as

(1,2),(3,4),\dots,(13,14)

. Choosing

8

numbers from

7

pairs forces one full pair, hence two consecutive numbers.

False. Some boxes may be empty and some may contain more than one object.

Hence the correct answer is

\boxed{A,B,C}

." ::: :::question type="SUB" question="Show that if

2n+1

integers are chosen from the set

\{1,2,3,\dots,4n\}

, then at least two of the chosen integers differ by

1

." answer="Partition into consecutive pairs and apply pigeonhole principle." hint="Group the numbers into

2n

boxes." solution="Partition the set

\{1,2,3,\dots,4n\}

into the

2n

consecutive pairs

\qquad (1,2), (3,4), \dots, (4n-1,4n)

These are our boxes. Now choose

2n+1

integers from the set. Since there are only

2n

boxes, by the pigeonhole principle at least one box contains at least two chosen integers. But each box is a consecutive pair, so the two chosen integers in that box differ by

1

. Hence at least two of the chosen integers differ by

1

. This proves the result." ::: ---

Summary

❗ Key Takeaways for CMI

Extremal counting focuses on the fullest, emptiest, largest, or smallest object.

The strong pigeonhole principle gives the guaranteed extremal occupancy.

The hardest step is often choosing the right boxes.

Ceiling and floor are essential when the average is not an integer.

Many “existence of close/repeated structure” problems are just cleverly disguised extremal counting problems.

Chapter Summary

❗ Pigeonhole principle — Key Points

The Basic Pigeonhole Principle (PHP) states that if $n$ items are put into $m$ containers, with $n > m$ , then at least one container must contain more than one item.
The Generalized Pigeonhole Principle extends this: if $n$ items are put into $m$ containers, then at least one container must contain at least $\lceil n/m \rceil$ items.
Identifying the "pigeons" (items) and "pigeonholes" (containers) is the critical first step in applying PHP. This often requires creative problem rephrasing.
PHP is fundamentally an existence proof technique, guaranteeing the presence of a certain configuration without necessarily providing a constructive method to find it.
Common applications include problems in number theory (e.g., modular arithmetic, divisibility), geometry (e.g., points in regions), graph theory (e.g., degree sequences), and combinatorial arguments.
Extremal counting applications often leverage PHP to establish lower bounds or necessary conditions for certain properties to hold, sometimes leading into areas like Ramsey Theory.
* The principle is surprisingly powerful due to its simplicity, allowing for elegant proofs of non-trivial results in discrete mathematics.

---

Chapter Review Questions

:::question type="MCQ" question="A drawer contains 12 red, 10 blue, and 8 green socks. If you pick socks randomly in the dark, what is the minimum number of socks you must pick to guarantee you have a pair of the same color?" options=["3","4","5","6"] answer="4" hint="Consider the colors as pigeonholes. How many socks must be picked to exceed the number of pigeonholes by one?" solution="Let the colors (red, blue, green) be the pigeonholes. There are 3 pigeonholes. By the Pigeonhole Principle, to guarantee at least two socks of the same color (a pair), you must pick one more sock than the number of colors. So, $3+1=4$ socks. If you pick 3 socks, you could pick one of each color, but the 4th sock must match one of the colors already picked."
:::

:::question type="NAT" question="What is the minimum number of integers that must be chosen from the set $\\{1, 2, \dots, 20\\}$ to guarantee that there are at least two integers whose sum is 21?" answer="11" hint="Form pairs of numbers from the set that sum to 21. Each pair represents a pigeonhole. What happens when you pick more numbers than pigeonholes?" solution="Form pairs of numbers from the set $\\{1, 2, \dots, 20\\}$ that sum to 21: $\$ . There are 10 such pairs. Let each pair be a pigeonhole. If we select one number from each of these 10 pairs, we would have 10 numbers, and no two would sum to 21 (e.g., $\\{1, 2, \dots, 10\\}$ or $\\{11, 12, \dots, 20\\}$ ). However, if we select an 11th number, it must come from one of the existing pairs, thereby guaranteeing that we have both numbers of a pair, and thus two numbers that sum to 21. Therefore, the minimum number is 11."
:::

:::question type="MCQ" question="In a group of 6 people, it is known that either there are 3 mutual friends or 3 mutual strangers. This is a classic result from Ramsey Theory ( $R(3,3)=6$ ), often demonstrated using the Pigeonhole Principle. Consider the problem of finding the minimum number of vertices, $n$ , in a graph such that if each edge is colored either red or blue, there must exist a monochromatic triangle (a triangle with all edges of the same color). What is this minimum number $n$ ?" options=["4","5","6","7"] answer="6" hint="This question directly refers to the definition of the Ramsey number $R(3,3)$ . Think about how the PHP is used to prove this specific value." solution="This is the direct definition and value of the Ramsey number $R(3,3)$ , which is 6. The proof involves picking an arbitrary vertex and considering the edges connected to it. By the Pigeonhole Principle, among the 5 edges connected to this vertex, at least 3 must be of the same color (e.g., red). If these 3 vertices are connected by red edges, they form a monochromatic red triangle. If any two of them are connected by a blue edge, then these two, along with the initial vertex, form a monochromatic blue triangle. Thus, 6 vertices are sufficient to guarantee a monochromatic triangle."
:::

---

What's Next?

💡 Continue Your CMI Journey

The Pigeonhole Principle is a fundamental tool in combinatorial problem-solving and proof techniques. Its applications often serve as an introduction to more advanced topics. As you continue your CMI preparation, consider exploring Ramsey Theory in more depth, which generalizes the concepts seen in extremal counting. The logical reasoning developed here will also be invaluable for understanding graph theory (especially extremal graph theory) and various counting arguments involving generating functions and recurrence relations. Mastery of PHP strengthens your foundation for tackling complex problems in discrete mathematics.

Pigeonhole principle

Pigeonhole principle

Chapter Contents

| Topic |

Part 1: Basic pigeonhole

Basic Pigeonhole

Overview

Learning Objectives

Core Idea

The Real Skill

Standard Forms

Minimal Worked Examples

Repeated Remainders

Bounded-State Version

Prefix-Sum and Equal-Sum Method

Subset-Sum Pigeonhole

PYQ-Relevant Insight

Common Mistakes

CMI Strategy

Practice Questions

Summary

Part 2: Strong pigeonhole

Strong Pigeonhole

Overview

Learning Objectives

Core Statement

Most Important Forms

How to Spot the Pigeonholes

Standard Consequences

Minimal Worked Examples

Common Traps

CMI Strategy

Practice Questions

Summary

Part 3: Extremal counting applications

Extremal Counting Applications

Overview

Learning Objectives

Core Idea

The Two Main Extremal Questions

Standard Extremal Patterns

Fast Formulas

Minimal Worked Examples

How to Build the Boxes

Sharpness and Best Possible Answers

Common Mistakes

CMI Strategy

Practice Questions

Summary

Chapter Summary

Chapter Review Questions

What's Next?

🎯 Key Points to Remember

Related Topics in Combinatorics and Discrete Mathematics

Binomial methods

Recurrence relations

Counting principles

Invariants and monovariants

More Resources

Study Notes

Short Notes

Test Series

Mock Tests

Previous Year Papers

Chapter-wise PYQs

Chapter Practice

Why Choose MastersUp?

AI-Powered Plans

15,000+ Questions

Smart Analytics

Bookmark & Revise