[go: up one dir, main page]
Scribd
Upload
230 views32 pages

Pigeonhole Principle

This document provides an introduction to the pigeonhole principle for students in a BSEd-MATH 3-1 class. It defines the pigeonhole principle and generalized pigeonhole principle. Examples are provided to demonstrate how to use the principle to solve problems involving placing objects into boxes and determining the minimum number needed to guarantee duplicates. Formulas are presented for calculating the minimum number of objects. The principle is also discussed in the context of one-to-one functions. Real-life applications are highlighted and students are guided on generalizing and valuing the importance of the principle.

Uploaded by

Mary Maevelyn Maglahus
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
230 views32 pages

Pigeonhole Principle

This document provides an introduction to the pigeonhole principle for students in a BSEd-MATH 3-1 class. It defines the pigeonhole principle and generalized pigeonhole principle. Examples are provided to demonstrate how to use the principle to solve problems involving placing objects into boxes and determining the minimum number needed to guarantee duplicates. Formulas are presented for calculating the minimum number of objects. The principle is also discussed in the context of one-to-one functions. Real-life applications are highlighted and students are guided on generalizing and valuing the importance of the principle.

Uploaded by

Mary Maevelyn Maglahus
Copyright
© © All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
You are on page 1/ 32

WELCOME

BSEd-MATH 3-1!
Prepared by: MS. DAISERY C. GALOS
BSEd- MATHEMATICS 4
M112- NUMBER THEORY
PIGEONHOLE
PRINCIPLE
1 After going through this discussion,
you are expected to:
a. describe the concept of pigeonhole principle and
the generalized pigeonhole principle;

2 b. solve problems involving the pigeonhole


principle; and

c. apply and explain the importance of the


pigeonhole principle in real-life situations.
3
1 PIGEONHOLE PRINCIPLE

The Pigeonhole Principle, also known as


2 Dirichlet’s (Box) Principle, is a very intuitive
statement, which can often be used as a
powerful tool in combinatorics.

3
1 PIGEONHOLE PRINCIPLE

(Pigeonhole Principle). If k is a positive integer


and k+1 objects are placed into k boxes, then at
least one box contains two or more objects.
2 Proof. We use a proof of contradiction. Suppose
none of the k boxes has more than one object.
Then the total number of objects would be at most
k. This contradicts the statement that we have k+1
objects.
3
1 EXAMPLE 1.

What is the minimum number of people I need


to ensure that two people share the same
birthday?
2 Answer:
k= 366
k+1= 366+1= 367
Therefore, the minimum number of people which two of them
share the same birthday is 367.

3
1 EXAMPLE 2.

Bob’s sock drawer has many, many socks in it,


and they come in 4 colors. Unfortunately, the
2 light in his room has burned out, so he cannot
see anything. How many socks should he grab
from the drawer, so that he can be sure at
least two of them are of the same color?

3
1 Example 2. Bob’s sock drawer has many, many socks
in it, and they come in 4 colors. Unfortunately, the
light in his room has burned out, so he cannot see
anything. How many socks should he grab from the
drawer, so that he can be sure at least two of them
are of the same color?
2 Answer:
k= 4
k+1= 4+1= 5
Therefore, he must grab at least 5 socks.

3
1
COROLLARY 1

Corollary 1: A function f from a set with k+1


2 elements to a set with k elements is not one-
to-one.

The corollary is a proposition that follows


from one that is already approved.
3
1 ONE-TO-ONE FUNCTION ONTO FUNCTION

2
A function f: X→Y is said to be a A function f: X→Y is said to be
one-to-one function if the an onto function if every
images of distinct elements of X element of Y is an image of
3 under f are distinct. some element of set X under f.
1 Corollary 1: A function f from a set with k+1 elements
to a set with k elements is not one-to-one.

Proof: Using the pigeonhole principle.


• Create a box for each element y in the codomain
of f.
2 • Put in the box for y all of the elements x from
the domain such that f(x)=y.
• Because there are k+1 elements and only k
boxes, at least one box has two or more
elements.
3 Hence, f can’t be one-to-one.
1
GENERALIZED PIGEONHOLE PRINCIPLE

Generalized Pigeonhole Principle: If


2 N objects are placed into k boxes,
where N > k, then there is at least
one box containing ⌈N/k ⌉ objects.

3
1 In mathematics and computer
programming there are two types of
functions that are commonly used. One is
the floor function, and the other is
2 the ceiling function.

EXAMPLE: 3.3
⌈3.3⌉= 4 (ceiling function)
⌊3.3⌋= 3 (floor function)
3
Given:5 pigeons
4 boxes
Let: N- pigeons
k- boxes
Since, N > k, then there exists at
least one box containing ⌈N/k ⌉
objects.

Solution: ⌈N/k ⌉= ⌈5/4 ⌉= ⌈1.25 ⌉ = 2


Solution: ⌈N/k ⌉= ⌈5/4 ⌉= ⌈1.25 ⌉ = 2
TRY TO ANSWER THE FOLLOWING:
1. Among 50 people, what is the number of people that must be
born in the same month?
2. A bowl contains 10 red and 10 yellow balls. How many balls
must be selected to ensure 3 balls of the same color?
3. How many cards must be selected from a standard deck of 52
cards to guarantee that at least three cards of the same suit are
chosen?
4. Show that if you pick five numbers from the integers 1 to 8, then
two of them must add up to nine.
5. In a group of 10 people, some people are friends with each
other. What is the minimum number of people you need to ask
about their number of friends to ensure that at least two people
have the same number of friends?
1
Example 3. Among 50 people, what is the
number of people that must be born in
the same month?
2 Answer:
Let N= 50 and k=12
⌈N/k ⌉= ⌈50/12 ⌉= ⌈4.1667⌉ = 5
Therefore, the number of people that must be
born in the same month is 5.

3
1 Example 4. A bowl contains 10 red and 10
yellow balls. How many balls must be selected
to ensure 3 balls of the same color?
Answer:
Let k=2 and ⌈N/k ⌉=3
2 𝑁−1
=⌈N/k ⌉-1
𝑘
𝑁−1 • Therefore, there
2
=3-1 must be 5 balls to
N-1=2(2) ensure 3 balls of
N=4+1= 5 the same color.
3
1 Example 5. How many cards must be selected from
a standard deck of 52 cards to guarantee that at least
three cards of the same suit are chosen?
Answer:
Let k=4 and ⌈N/k ⌉=3
2 𝑁−1
=⌈N/k ⌉-1
𝑘
𝑁−1 • Therefore, there must be
4
=3-1 9 cards to guarantee that
N-1=2(4) at least 3 cards of the
N=8+1= 9 same suit are chosen.
3
1 Example 6. Show that if you pick five numbers
from the integers 1 to 8, then two of them must
add up to nine.
Answer:
2 In the range of integers 1 to 8, there are four pairs of
numbers that add up to 9: (1, 8), (2, 7), (3, 6), and (4, 5).
When you pick five numbers from this range, by the
Pigeonhole Principle, you must have selected at least
one pair among these four pairs. Therefore, two of the
five numbers you pick must add up to nine.

3
1 Example 7. In a group of 10 people, some people are friends
with each other. What is the minimum number of people you
need to ask about their number of friends to ensure that at
least two people have the same number of friends?

Answer:
2 You need to ask about the number of friends of at least
9 people to ensure that at least two people have the
same number of friends. This is because the number of
friends each person has can range from 0 to 9. With 10
people and only 10 possible values for the number of
friends, by the Pigeonhole Principle, at least two people
must have the same number of friends.

3
1
FORMULA TO LOOK OF THE NUMBER OF
OBJECTS NEEDED

2 𝑵−𝟏
=⌈N/k ⌉-1
𝒌

3
1 APPLICATION
1. Ten people are swimming in the lake. Prove that at least two
of them were born on the same day of the week.

2 2. Seventeen children are in an elevator. Prove that at least


three of them were born on the same day of the week.

3. What’s the minimum number of students, each of whom


comes from one of the 50 states must be enrolled in a
university to guarantee that there are at least 100 who come
3 from the same state?
1
VALUING

• Apply the concept of the Pigeonhole


2 Principle to real-life situations and
reflect on its importance.

3
GENERALIZATION
Guide Questions:
• What is the Pigeonhole Principle?
• Is the pigeonhole principle a one-to-one
function or not and why?
1 FORMULAS:

• k+1- in finding the minimum number


• ⌈N/k⌉- in finding the number of
2 objects contain in at least one box
𝑵−𝟏
• =⌈N/k⌉-1: looking for the numbers
𝒌
of objects needed
3
EVALUATION
THANK YOU
BSED MATH 3-1
REFERENCES:
• 16 fun applications of the pigeonhole principle – Mind Your Decisions. (2008, November 25).
https://mindyourdecisions.com/blog/2008/11/25/16-fun-applications-of-the-pigeonhole-
principle/
• Byju’s. (2022). What is pigeonhole principle- - BYJU-S QnA. byjus.com.
https://byjus.com/question-answer/what-is-pigeonhole-principle/
• Calcworkshop. (2021, February 15). Pigeonhole Principle (Defined w/ 11 Step-by-Step Examples!).
https://calcworkshop.com/combinatorics/pigeonhole-principle/
• GeeksforGeeks. (2023). Pigeonhole principle. GeeksforGeeks.
https://www.geeksforgeeks.org/discrete-mathematics-the-pigeonhole-principle/
• Josef. (2014, July 18). PPT - The Pigeonhole Principle PowerPoint Presentation, free download -
ID:1929271. SlideServe. https://www.slideserve.com/josef/the-pigeonhole-principle
• Kimberly Brehm. (2022, March 30). Discrete Math II - 6.2.1 The Pigeonhole Principle [Video].
YouTube. https://www.youtube.com/watch?v=xEuPd4k_IPo
• Libretexts. (2021). 9.2: the pigeonhole principle. Mathematics LibreTexts.
https://math.libretexts.org/Bookshelves/Mathematical_Logic_and_Proof/Proofs_and_Conc
epts_The_Fundamentals_of_Abstract_Mathematics_(Morris_and_Morris)/09%3A_Cardinali
ty/9.02%3A_The_pigeonhole_principle

You might also like