VISVESVARAYA TECHNOLOGICAL UNIVERSITY
Jnana Sangama, Belagavi – 590 010
REPORT ON
The Pigeon Hole Principle
Submitted in partial fulfillment for the requirements for the 4th semester CIE
for the subject
Discrete Mathematical Structures (BCS405A)
BACHELOR OF ENGINEERING
IN
INFORMATION SCIENCE AND ENGINEERING
For the Academic Year 2023 – 2024
Submitted by:
SHUBHAM DEEP 1MV22IS103
Under the guidance of:
Dr. S.K UMA
Professor and Head
Department of Mathematics
SIR M. VISVESVARAYA INSTITUTE OF TECHNOLOGY
DEPARTMENT OF INFORMATION SCIENCE AND ENGINEERING
SIR M. VISVESVARAYA INSTITUTE OF TECHNOLOGY
Hunasamaranahalli, Bengaluru – 562157
SIR M. VISVESVARAYA INSTITUTE OF TECHNOLOGY
BENGALURU – 562 157
DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING
CERTIFICATE
This is to certify that the report entitled “The Pigeon Hole Principle” carried
out by SHUBHAM DEEP (1MV22IS103) bonafide Student of Sir M Visvesvaraya
Institute of Technology in partial fulfilment for the 4 semester Discrete Mathematical
th
Structures (BCS405A) for the award of the Degree of Bachelor of Engineering in
Information Science and Engineering of the Visvesvaraya Technological University,
Belagavi during the academic year 2023-2024.It is certified that all corrections and
suggestions indicated for Internal Assessment have been incorporated in the report deposited
in the department library. The project report has been approved as it satisfies the academic
requirements in respect of project work prescribed for the course of Bachelor of Engineering.
1.
DECLARATION
We hereby declare that the entire project work embodied in this dissertation
has been carried out by us and no part has been submitted for any degree or
diploma of any institution previously.
Place: Bengaluru
Date:
Signature of Student
SHUBHAM DEEP
1MV22IS103
THILAK V
1MV22IS11
INTRODUCTION
The Pigeonhole Principle, also known as Dirichlet's box principle, is a fundamental concept in
mathematics, particularly in combinatorics. Named after the German mathematician Peter
Gustav Lejeune Dirichlet, this principle provides a straightforward yet powerful method of
proving the inevitability of certain outcomes. In simple terms, it states that if you have more
pigeons than pigeonholes and each pigeon is to be put into a pigeonhole, then at least one
pigeonhole must contain more than one pigeon. This report delves into the Pigeonhole
Principle, its applications, and step-by-step problem-solving methods.
Understanding the Pigeonhole Principle
Basic Definition
The Pigeonhole Principle can be formally stated as follows: "If n+1n+1n+1 objects are placed
into nnn boxes, then at least one box contains two or more objects."
This principle is deceptively simple but has far-reaching implications in various fields of
mathematics and computer science. It emphasizes the inevitability of collisions, repetitions,
or regroupings in sufficiently large sets.
Everyday Examples
1. Birthdays: If there are 32 teachers in a college and only 12 months in a year, by the
Pigeonhole Principle, at least three teachers must share the same birth month.
2. Emails: Sending 101 emails to 100 different addresses guarantees that at least one address
will receive more than one email.
3. Tickets: During a sale, if 501 tickets are issued for 500 available items, at least one person
will be ticketless.
1
Mathematical Examples
1. Sock Drawer: If you have 10 pairs of socks in different colors, and you randomly pick
11 socks, at least one color will have more than one sock.
2. Points in a Plane: If 5 points are placed inside a square of side length 2 units, at least
one pair of points will be at most 2\sqrt{2}2 units apart.
Applications of the Pigeonhole Principle
The Pigeonhole Principle is used in various fields such as network theory, computer science,
optimization problems, and more.
Network Theory
In a network where each node represents a device and links between nodes represent
connections, the principle can be used to prove that in a sufficiently large network, there
will always be at least two devices sharing the same number of connections. This conclusion
helps in load balancing and network design, ensuring that no single node gets
overburdened.
Computer Science
In hashing algorithms, the Pigeonhole Principle is used to show that collisions are inevitable
when more items are hashed than there are available hash slots. This helps in designing
efficient collision resolution strategies.
Optimization Problems
Optimization problems often involve scenarios where the Pigeonhole Principle is applied to
deduce minimum or maximum conditions. For example, in scheduling problems, it can be
used to prove that at least one time slot must be shared by multiple tasks if the number of
tasks exceeds the available time slots.
2
Step-by-Step Guide to Solving Pigeonhole Principle Problems
Solving problems using the Pigeonhole Principle requires a methodical approach. Here’s a
step-by-step guide to navigate through these challenges:
Step 1: Identify the Pigeons and Pigeonholes
Determine what the pigeons (objects) and pigeonholes (categories or compartments) are in
the problem.
Step 2: Count the Pigeons and Pigeonholes
Calculate or establish the number of pigeons and pigeonholes. If the number of pigeons
exceeds the number of pigeonholes, the principle applies.
Step 3: Apply the Principle
Use the principle to assert that at least one pigeonhole must contain more than one pigeon.
This often requires proving that a specific scenario must exist.
Step 4: Generalize the Findings
Extend the conclusion to make general statements about the problem, corroborating the
presence of patterns or conditions that are guaranteed to occur.
Examples of Problem Solving
Example 1: Sock Drawer Problem
Problem: You have 10 pairs of socks in different colors, and you randomly pick 11 socks.
Prove that at least one color will have more than one sock.
Solution:
3
1. Pigeons: 11 socks
2. Pigeonholes: 10 colors
3. Application: Since 11 socks (pigeons) are distributed among 10 colors (pigeonholes), by the
Pigeonhole Principle, at least one color must have more than one sock.
Example 2: Handshake Problem
Problem: In a party of 10 people, prove that at least two people have shaken hands with the
same number of people.
Solution:
1. Pigeons: 10 people
2. Pigeonholes: Possible handshake counts (0 to 9)
3. Application: Since each person can shake hands with 0 to 9 others, there are 10 possible
handshake counts. However, if one person has shaken hands with 0 people, another person
must have shaken hands with all 9 others. Hence, the counts range from 1 to 8, leading to
only 9 possible handshake counts for the remaining people. By the Pigeonhole Principle, at
least two people must share the same number of handshakes.
Conclusion
The Pigeonhole Principle is a simple yet powerful tool in mathematics that helps prove the
inevitability of certain outcomes. Its applications are vast, ranging from everyday scenarios
to complex mathematical and computer science problems. By understanding and applying
this principle, one can easily navigate through problems involving collisions, repetitions, and
regroupings. The Pigeonhole Principle not only provides a method for proving existence but
also helps in optimizing and designing efficient solutions in various fields.
