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