0602 The Pigeonhole Principle

6.2 The Pigeonhole Principle.

Ex: 1-3, 5-7

Theorem 1 - The pigeonhole principle

If k is a positive integer and k+1 or more objects are placed into $k$ boxes, then there is at least one box containing two or more of the objects.

Theorem 2 - Generalized pigeonhole principle

If $N$ object are placed into $k$ boxes, then there is at least one box containing $\lceil N/k \rceil$ objects.

Homework

p426: 2, 6, 9

2. Show that if there are 30 students in a class, then at least two have last names that begin with the same letter.

6. Let $d$ be a positive integer. Show that among any group of $d + 1$ (not necessarily consecutive) integers there are two with exactly the same remainder when they are divided by $d$ .

9. What is the minimum number of students, each of whom comes from one of the 50 states, who must be enrolled in a university to guarantee that there are at least 100 who come from the same state?