Saturday, November 26, 2005

Combina-WHAT? Topic: Combinatorics. Level: AMC/AIME.

Problem #1: Prove that $nC0+nC1+\cdots+nCn = 2^n$ ($nCk$ denotes $n$ choose $k$).

Solution: Chances are you've seen this before, and there are many proofs to it (one of my favorites being the number of subsets of an $n$-element set... think about it).

But here's another cool proof, using our very own Binomial Theorem.

Consider $(x+1)^n = (nC0)x^n+(nC1)x^{n-1}+\cdots+(nCn)$.

But upon setting $x = 1$, we immediately have $2^n = nC0+nC1+\cdots+nCn$ as desired. QED.

--------------------

Problem #2: Prove that $nC0-nC1+\cdots+(-1)^n(nCn) = 0$.

Solution: Well if you understood the concept behind the first problem, this one should come very easily.

$(x+1)^n = (nC0)x^n+(nC1)x^{n-1}+\cdots+(nCn)$ so for $x = -1$ we have

$0 = (-1)^n(nC0)+(-1)^{n-1}(nC1)+\cdots+(nCn)$ from which we can just flip the sign (if necessary) to get the desired result. QED.

--------------------

Practice Problem #1: Prove $nC0+nC1+\cdots+nCn = 2^n$ using the subsets argument.

Practice Problem #2: Show that $nCr+nC(r+1) = (n+1)C(r+1)$.

Practice Problem #3: (1983 AIME #8) Find the largest two-digit prime that divides $200C100$.

1. 1. nC0 is the number of subsets of a set of size n of size 0, nC1 is the number of subsets of size 1, ... to nCn the number of subsets of size n. Adding them gives the total number of subsets of a set of size n, which is 2^n because a subset either contains any given element or it does not. (This is assuming the empty set counts as a subset; if it doesn't, subtract nC0 = 1 from both sides.)

2. A cheap sort of proof would be observing that this is equivalent to one method of generating Pascal's triangle. More rigorously:

(x+1)^n = nC0 + nC1 x^1 + ...

Multiply this series by (x+1) and look at the two terms that contribute to the coefficient of (n+1)C(r+1) x^{r+1}; the only two terms that do so are nCr x^r * x and nC(r+1) x^{r+1} * 1, so adding those together gives the desired result.

2. There's another cool subsets argument to #2: nCr is the number of r-element subsets of an n-element set. Suppose you add an element k. We want to find the number of (r+1)-element subsets in an (n+1)-element set. Consider the subsets with k and without k:

with k - nCr (take any r-elemnent subset of the original n-element set and add k - we now have r+1 elements)

without k - nC(r+1) (take any (r+1)-element subset of the original n-element set)

These two cases account for all the (r+1)-element subsets so we have our desired identity - nCr+nC(r+1) = (n+1)C(r+1).

3. #2: It's equivalent to saying that the sum of the two consecutive numbers in Pascal's triangle is equal to the number between them in the next row...

Yeah, I know, not a very good proof, but you get the idea. :D

4. 3. 200C100 = (200*199*198*...*101) / (100*99*...) = (2*199*2*197*...*101), so we want a two-digit prime that divides a three-digit odd number

5. Strange, it cut me off. Anyway, we have to multiply the prime by at least 3 to keep it odd, so the prime is

6. 61. wtf?