Lecture on the Pigeonhole Principle

Introduction

Definition: The pigeonhole principle states that if you have more items (pigeons) than containers (pigeonholes), at least one container must contain more than one item.
Importance: It's a foundational concept in proofs, especially those using contradiction.

If you have M items and N containers and M > N, there is at least one container with more than one item.
Ceiling Function: Rounds up a number. For example, if you distribute 4 items into 3 containers, \(\frac{4}{3}\ = 1.333\ldots), the ceiling is 2. Therefore, at least one container will have 2 items.

General Distribution:
- 10 items in 4 containers: At least one container will have 3 items.
- Impossible to have less than 3 items in all containers.
Friendship Example:
- In a group of N people, at least two will have the same number of friends.
- Maximum friends one can have is N-1.
- Using pigeonhole principle, assigning people to the number of friends as containers, guarantees at least two people in the same container.
Birthday Example:
- In a group of 366 people, at least two have the same birthday.
Number Pairing Example:
- Set ( S = {1, 2, \ldots, 20} ). Picking 11 numbers guarantees that two numbers sum to 21.
- Containers are pairs of numbers that sum to 21.

Using grids and geometric distributions:
- Example with a grid and 17 dots, proving some are within root 8 cm.
- Discussed minimum number of dots to ensure two dots are within a certain distance.

Used in various mathematical problems such as proving divisors, multiples, and other abstract concepts.

Pigeonhole principle is crucial for understanding proofs, especially in combinatorics and discrete mathematics.
Upcoming lectures will cover division in number theory.

Encouraged to practice with different examples to understand the concept fully.
Recommended to explore further readings or courses in elementary number theory for deeper understanding.