somewhere near the beginning.

First Putnam problem

Filed under: Mathematics — Alex @ 9:37 am 1/19/2005

I’ve made a deal with another guy hear at UH to help me study for the Putnam competition: we’ll be working on the A problems from the 85-90 competitions. Luckily, I bought a book with all the problems and solutions from 85-2000 this summer, so I’m set. Here’s the first one I’m working on:

A1 (1985). Determine, with proof, the number of ordered triples (A_1, A_2, A_3) of sets which have the property that

  1. A_1 \cup A_2 \cup A_3 = \{1,2,3,4,5,6,7,8,9,10\}, and
  2. A_1 \cap A_2 \cap A_3 = \emptyset

where \emptyset denotes the empty set. Express the answer in the form 2^a3^b5^c7^d, where a,b,c, and d are nonnegative integers.

I’ll post my solution when I get one. Feel free to let me know yours :)

First Attempt: Let i+j+k=10 and i\neq 0 \neq j \neq 0 \neq k, then what we’re looking for is Q = \sum_{i,j,k} \binom{10}{i}\binom{10-i}{j}\binom{10-i-j}{k} = \sum_{i,j,k} \binom{10}{i}\binom{10-i}{j}. That is, Q = \sum_{i=1}^8 \sum_{j=1}^{9-i} \binom{10}{i} \binom{10-i}{j} = \sum_{i=1}^8 \binom{10}{i} \sum_{j=1}^{9-i} \binom{10-i}{j}. Let m=10-i, then \displaystyle Q = \sum_{i=1}^8 \binom{10}{i} \sum_{j=1}^{m-1} \binom{m}{j} = \sum_{i=1}^8 \binom{10}{i} \left( \sum_{j=0}^m \binom{m}{j} - \binom{m}{0} - \binom{m}{m} \right) . Substituting back, Q = \sum_{i=1}^8 \binom{10}{i} (2^{10-i}-2) . Doesn’t seem quite right, some how, but I’m going to continue on, and see if I can factor it when I’m done.

Hmmm, thanks to Ronald’s comment, it seems that I’ve been doing the problem all wrong— the intersection of all three sets is empty— I was working as though the sets were mutually independent.

Possibly relevant posts:

3 Comments »

RSS feed for comments on this post. TrackBack URL

Leave a comment