PIGEONHOLE PRINCIPLE
18052023
INTRODUCTION:
Suppose there are 10 pigeons need to be arrange in 9 pigeonholes. here there are 10 pigeons but
only 9 pigeonholes. Then atleast one of these pigeonholes must have atleast two pigeons in it.
This is what Pigeonhole principle is. It states that if there are more pigeons than pigeonholes
then there must be atleast one pigeonhole with atleast two pigeons in it. This principle is used
in Probability, Geometry, Number theory etc.
Generalised Pigeon Hole Principle:-
STATEMENT:
If N objects are placed into k boxes, where k ∈ Z+ , then there is atleast one box containing
N
atleast ⌈ k ⌉ objects.
PROOF:
let us suppose that each box must have strictly less than ⌈ Nk ⌉ N
objects i.e,⌈ k ⌉−1 objects.
Now there are k boxes and each box has objects ≤ ⌈ Nk ⌉ − 1
N
=⇒ total no.of objects ≤ k ⌈ k
⌉ − 1
=⇒ N ≤ k ⌈ Nk ⌉ − 1
=⇒ N ≤ k ⌈ Nk ⌉ − 1 < k. Nk [∵ ⌈x⌉ − 1 < x] =
N
=⇒ N < N which is contradiction.
∴ atleast one of box containing atleast ⌈ Nk ⌉ objects.
PROBLEMS:
Q1: What is the minimum no. of people need to ensure that two people share the same
birthday (in leap year)?
A: No.of days in a leap year (k)= 366
let minimum no.of people need be N.
N
Given that two people share the same birthday i.e, ⌈ 366 ⌉ = 2
−1
=⇒ N366 = (2 − 1)
=⇒ N − 1 = 366
=⇒ N = 366 + 1 = 367
∴ The minimum no. of people needed to ensure that two people share the same birthday
is 367
Q2: What is the minimum no. of words need(using English Language) to ensure that two
words start with the same letter?
A: No.of letters in English language (k)= 26
let minimum no.of words needed be N.
N
Given that two words start with same letter i.e, ⌈ 26 ⌉ = 2
N −1
=⇒ = (2 − 1)
26
=⇒ N − 1 = 26
=⇒ N = 26 + 1 = 27
∴ The minimum no. of words needed to ensure that two words start with the same letter
is 27
18052023
INTRODUCTION:
Suppose there are 10 pigeons need to be arrange in 9 pigeonholes. here there are 10 pigeons but
only 9 pigeonholes. Then atleast one of these pigeonholes must have atleast two pigeons in it.
This is what Pigeonhole principle is. It states that if there are more pigeons than pigeonholes
then there must be atleast one pigeonhole with atleast two pigeons in it. This principle is used
in Probability, Geometry, Number theory etc.
Generalised Pigeon Hole Principle:-
STATEMENT:
If N objects are placed into k boxes, where k ∈ Z+ , then there is atleast one box containing
N
atleast ⌈ k ⌉ objects.
PROOF:
let us suppose that each box must have strictly less than ⌈ Nk ⌉ N
objects i.e,⌈ k ⌉−1 objects.
Now there are k boxes and each box has objects ≤ ⌈ Nk ⌉ − 1
N
=⇒ total no.of objects ≤ k ⌈ k
⌉ − 1
=⇒ N ≤ k ⌈ Nk ⌉ − 1
=⇒ N ≤ k ⌈ Nk ⌉ − 1 < k. Nk [∵ ⌈x⌉ − 1 < x] =
N
=⇒ N < N which is contradiction.
∴ atleast one of box containing atleast ⌈ Nk ⌉ objects.
PROBLEMS:
Q1: What is the minimum no. of people need to ensure that two people share the same
birthday (in leap year)?
A: No.of days in a leap year (k)= 366
let minimum no.of people need be N.
N
Given that two people share the same birthday i.e, ⌈ 366 ⌉ = 2
−1
=⇒ N366 = (2 − 1)
=⇒ N − 1 = 366
=⇒ N = 366 + 1 = 367
∴ The minimum no. of people needed to ensure that two people share the same birthday
is 367
Q2: What is the minimum no. of words need(using English Language) to ensure that two
words start with the same letter?
A: No.of letters in English language (k)= 26
let minimum no.of words needed be N.
N
Given that two words start with same letter i.e, ⌈ 26 ⌉ = 2
N −1
=⇒ = (2 − 1)
26
=⇒ N − 1 = 26
=⇒ N = 26 + 1 = 27
∴ The minimum no. of words needed to ensure that two words start with the same letter
is 27
