MATH 302 Lecture 18

« previous | Monday, October 31, 2011 | next »

Test on Wednesday!

Pigeonhole Principle

If you have $k+1$ pigeons nesting in $k$ pigeon holes, then at least one hole has more than one pigeon.

More abstract way:

For a function $f:A\to B$, if $|A|>|B|$, then $f$ cannot be injective

Example

I have 12 black socks and 12 white socks in a drawer. How many socks will I have to pick to guarantee that I have a matching pair?

Answer: 3 socks.

Harder Example

For a number $n>0$, show there exists some multiple of $n$ whose decimal expansion has only 1s and 0s.

For a number to be a multiple of $n$, it has to have a remainder between 0 and $n-1$. If we take 1, 11, 111, …, 111...1 ($n+1$ ones), then there are two which have the same remainder by the pigeonhole principle. Taking the difference between these numbers results in a number that is divisible by $n$ and contains only 1s and 0s.

This paradigm is more common than one might think: using remainders as the pigeons is very useful for divisibility proofs

Generalized Pigeonhole Principle

$n$ pigeons divided into $k$ holes, then at least one pigeonhole has $\lceil \frac{n}{k}\rceil$ pigeons.

Example

1. How many distinct numbers must be selected from the set (1..6) so that some pair adds to 7 (4)
2. Why? (Picking 3 could result in one number in each "hole", and picking another will give a pair)

Pigeon holes: Pairs that add up to 7: (1,6) (2,5) (3,4)

Review for Test

• 2.4 Sequences and Series
• 5.1-5.4 Induction and Recursion
• 8.1-8.3 Recurrence Relations
• 6.1 Counting Problems

$(\genfrac{}{}{0ex}{}{n}{k})=\frac{n(n-1)\dots (n-k+1)}{k}$ represents the number of subsets of order $k$ that can be picked from a set of order $n$