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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n+1} integers between 1 and 2n must be multiples of one another

pigeons: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n+1} integers

pigeonholes: odd numbers between 1 and 2n (of which there are Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n} )

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

Definition: odd divisor: Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle m = 2^k p} , where Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle p} is odd.

Example

Any sequence of Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n^2+1} distinct real numbers has an increasing (or decreasing) subsequence of length at least Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle n+1} .

pigeons: numbers Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_1, \ldots, a_{n^2+1}}

for all Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 1 \le i \le n^2+1} we associate an ordered pair:

• Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle I_s \times D_s = I_t \times D_t}

2 cases:

1. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle a_s < a_t}
2. Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \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 Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(30,3) = \frac{30!}{(30-3)!}}

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(n,\, r) = \frac{n!}{(n-r)!}}

Read "permutation of n taken r at a time" Note Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle P(n,n) = n!}

Combinations

Order does not matter

Failed to parse (MathML with SVG or PNG fallback (recommended for modern browsers and accessibility tools): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle 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"