The Pigeonhole Principle Explained
D
D
i
i
s
s
c
c
r
r
e
e
t
t
e
e
M
M
a
a
t
t
h
h
:
:
T
h
e
P
i
g
e
o
n
h
o
l
e
P
r
i
n
c
i
p
l
e
I
n
t
r
o
d
u
c
t
i
o
n
Suppose that a flock of 20 pigeons flies into a set of 19
pigeonholes to roost.
Because there are 20 pigeons but only 19 pigeonholes, a least one
of these 19 pigeonholes must have at least two pigeons in it.
To see why this is true, note that if each pigeonhole had at most
one pigeon in it, at most 19 pigeons, one per hole, could be
accommodated.
This illustrates a general principle called the
pigeonhole principle
,
which states that if there are more pigeons than pigeonholes, then
there must be at least one pigeonhole with at least two pigeons in
it (see Figure 1).
Of course, this principle applies to other objects besides pigeons
and pigeonholes.
T
H
E
P
I
G
E
O
N
H
O
L
E
P
R
I
N
C
I
P
L
E
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.
References
D
i
s
c
r
e
t
e
M
a
t
h
e
m
a
t
i
c
s
a
n
d
I
t
s
A
p
p
l
i
c
a
t
i
o
n
s
,
M
c
G
r
a
w
-
H
i
l
l
;
7
t
h
e
d
i
t
i
o
n
(
J
u
n
e
2
6
,
2
0
0
6
)
.
K
e
n
n
e
t
h
R
o
s
e
n
D
i
s
c
r
e
t
e
M
a
t
h
e
m
a
t
i
c
s
A
n
O
p
e
n
I
n
t
r
o
d
u
c
t
i
o
n
,
2
n
d
e
d
i
t
i
o
n
.
O
s
c
a
r
L
e
v
i
n
A
S
h
o
r
t
C
o
u
r
s
e
i
n
D
i
s
c
r
e
t
e
M
a
t
h
e
m
a
t
i
c
s
,
0
1
D
e
c
2
0
0
4
,
E
d
w
a
r
d
B
e
n
d
e
r
&
S
.
G
i
l
l
W
i
l
l
i
a
m
s
o
n
The Pigeonhole Principle is a fundamental concept in discrete mathematics that asserts if there are more pigeons than pigeonholes, at least one hole must contain multiple pigeons. This principle is applied in various scenarios to analyze combinatorial problems and establish the existence of repetitions or patterns. Understanding this principle is crucial for solving problems related to allocation, distribution, and arrangement of objects in finite sets.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Discrete Math: The Pigeonhole Principle
Introduction Suppose that a flock of 20 pigeons flies into a set of 19 pigeonholes to roost. Because there are 20 pigeons but only 19 pigeonholes, a least one of these 19 pigeonholes must have at least two pigeons in it. To see why this is true, note that if each pigeonhole had at most one pigeon in it, at most 19 pigeons, one per hole, could be accommodated. This illustrates a general principle called the pigeonhole principle, which states that if there are more pigeons than pigeonholes, then there must be at least one pigeonhole with at least two pigeons in it (see Figure 1). Of course, this principle applies to other objects besides pigeons and pigeonholes.
THE PIGEONHOLE PRINCIPLE 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.
References Discrete Mathematics and Its Applications, McGraw-Hill; 7th edition (June 26, 2006). Kenneth Rosen Discrete Mathematics An Open Introduction, 2nd edition. Oscar Levin A Short Course in Discrete Mathematics, 01 Dec 2004, Edward Bender & S. Gill Williamson
