SME
Discrete Mathematics · Problem type
The pigeonhole principle
Use this for “Among 50 people, at least how many share a birth month? How many people force 5 in one month?”
This is an example. Type your own values to start a new problem.
m
=
⌈
N
÷
k
⌉
F
=
k
×
(
m
−
1)
+
1
Formulas
m
=
⌈
N
k
⌉
5
=
⌈
50
12
⌉
F
=
k
×
(
m
−
1)
+
1
49 = 12 × (5 − 1) + 1
Assumptions
•
Every object goes in exactly one box; the boxes may hold any number.
•
If each box held m − 1 or fewer, k boxes would hold at most k × (m − 1) objects.
•
So N objects in k boxes put at least ⌈N ÷ k⌉ in some box.
Step-by-step
WE KNOW
N = 50, k = 12
FIND
fewest in the fullest box (m), objects that force m in one box (F)
Step 1 · Find fewest in the fullest box (m)
Use m = ⌈N ÷ k⌉
Share the objects as evenly as possible: some box must take the rounded-up share.
⌈
50
12
⌉
=
⌈4.1667⌉
=
5
m
=
5
Step 2 · Find objects that force m in one box (F)
Use F = k × (m − 1) + 1
k
boxes
can
hold
m
−
1
each
without
reaching
m
;
one
object
more
forces
m
in
some
box.
F
=
12
×
(5
−
1)
+
1
F
=
12
×
4
+
1
F
=
48
+
1
F
=
49
Check
Put the numbers back in. Both sides should match.
5
=
⌈
50
12
⌉
✓
49 = 12 × (5 − 1) + 1 ✓
Topic check
See what you know: 5 questions on this topic
New questions each time. Pass to mark it complete.
Related lessons
Combinatorics
Main lesson
Identical items into boxes
Use this for “In how many ways can 10 identical balls go into 4 boxes? With at least one in each box?”
Derangements
Use this for “4 letters go into their 4 envelopes at random. In how many ways does no letter reach its own envelope?”
Words with repeated letters
Use this for “How many different words can be made from all 11 letters of MISSISSIPPI?”