MATH 302 Lecture 19

« previous | Monday, November 7, 2011 | next »

Pigeonhole Principle

Find what the pigeons and the pigeonholes are.

Pigeonholes should be such that there are more pigeons, and when two pigeons fall into the same hole, the problem is solved.

Example

show that two of any $n+1$ integers between 1 and 2n must be multiples of one another

pigeons: $n+1$ integers

pigeonholes: odd numbers between 1 and 2n (of which there are $n$)

So if two numbers have the same greatest odd divisor, then one must be a multiple of the other.

Definition: odd divisor: $m=2^{k}p$, where $p$ is odd.

Example

Any sequence of $n^{2}+1$ distinct real numbers has an increasing (or decreasing) subsequence of length at least $n+1$.

pigeons: numbers $a_{1},\ldots ,a_{n^{2}+1}$

for all $1\leq i\leq n^{2}+1$ we associate an ordered pair:

• $I_{i}$ = length of longest increasing sequence beginning with $a_{i}$
• $D_{i}$ = length of longest decreasing sequence beginning with $a_{i}$

Assume contradiction: then $1\leq I_{i},D_{i}\leq n$

Let $q_{i}$ represent $I_{i}\times D_{i}$

By the pigeonhole principle for some $s'<t'$, we have $I_{s}\times D_{s}=I_{t}\times D_{t}$

2 cases:

1. $a_{s}<a_{t}$
2. $a_{s}>a_{t}$

Example

The midpoint of some pair among any three integers is also an integer.

pigeons: the three integers pigeonholes: parity (even or odd)

If x and y (members of the pair) have the same parity, then their average ${\frac {x+y}{2}}$ is also an integer

6.3 Permutations and Combinations

Permutations

"Ordered/labeled subsets": where order of elements chosen matter!

Suppose we have 30 people in a group and we want to select three positions:

Answer is $P(30,3)={\frac {30!}{(30-3)!}}$

$P(n,\,r)={\frac {n!}{(n-r)!}}$

Read "permutation of n taken r at a time" Note $P(n,n)=n!$

Combinations

Order does not matter

$C(n,r)={\frac {P(n,r)}{r!}}={\frac {n!}{(n-r)!r!}}={\binom {n}{r}}$

Read "combination of n taken r at a time" or "n choose r"