Lecture Notes: Pigeonhole Principle

Introduction to Pigeonhole Principle

• Proof Technique: Often used in proof by contradiction.
• Basic Concept: If you have more items (pigeons) than containers (pigeonholes), at least one container must contain more than one item.

Understanding the Principle

• Example:
  • 4 items (pigeons) and 3 containers (pigeonholes) result in at least one container having at least 2 items.
  • Generalized: If M items are distributed into N containers, then at least one container holds ceil(M/N) items.
• Ceiling Function: Rounds a number up to the nearest integer.

Applications of the Pigeonhole Principle

Social Network Example

• Scenario: N people in a group.
• Conclusion: At least two people have the same number of friends.

Birthday Problem

• Scenario: 366 people.
• Conclusion: At least two people have the same birthday.

Numerical Example

• Set S: Numbers 1 through 20.
• Task: Picking 11 numbers guarantees a sum of two picked numbers equals 21.

Advanced Applications

Grid and Distance Problem

• Setup: 8 cm x 8 cm square.
• Task: With 17 dots placed, at least two dots are within the square root of 8 cm distance.
• Explanation: Using the Pigeonhole principle to determine the minimum number of dots required for specific conditions.

Conclusion

• The Pigeonhole Principle is a powerful tool in proofs and problem-solving.
• Next Topic: Division and Elementary Number Theory.
• Reminder: Importance of this principle in discrete mathematics and proofs.