Subset It Up. Topic: Sets/Combinatorics. Level: Olympiad.

Problem: (1981 IMO - #2) Take $r$ such that $1\le r\le n$, and consider all subsets of r elements of the set $\{1,2,\ldots,n\}$. Each subset has a smallest element. Let $F(n,r)$ be the arithmetic mean of these smallest elements. Prove that:

$F(n,r)=\frac{n+1}{r+1}$.

Solution: So we first find out how many of these subsets there are. Well that's easy, just choose $r$ elements from $n$, or $nCr$.

So how many have smallest element $1$? Well, assume $1$ is in the set. Then we have to pick the other $r-1$ elements from the remaining $n-1$ elements. So we have $(n-1)C(r-1)$.

And $2$? By the same argument, we have $(n-2)C(r-1)$ (choosing $r-1$ elements from the numbers above $2$).

So for any $k$, we have $(n-k)C(r-1)$ ways to choose a subset of size $r$ that has minimum element $k$.

Since we are taking an arithmetic mean, we want the sum of ALL the minimum elements, meaning we take $k \cdot (n-k)C(r-1)$, added up to be

$ \displaystyle \sum_{i=1}^{n-r+1} [i \cdot (n-i)C(r-1)] = 1\cdot (n-1)C(r-1)+2 \cdot (n-2)C(r-1) + \cdots +(n-r+1)\cdot (r-1)C(r-1) $.

But remember by the above argument we have

$ \displaystyle \sum_{i=1}^{n-r+1} (n-i)C(r-1) = (n-1)C(r-1)+(n-2)C(r-1)+\cdots+rC(r-1)+(r-1)C(r-1) = nCr$.

Similarly

$ \displaystyle \sum_{i=2}^{n-r+1} (n-i)C(r-1) =(n-2)C(r-1)+\cdots+(r-1)C(r-1) = (n-1)Cr $.
$ \displaystyle \sum_{i=3}^{n-r+1} (n-i)C(r-1) = (n-3)C(r-1)+\cdots+(r-1)C(r-1) = (n-2)Cr $.
...
$ \displaystyle \sum_{i=n-r}^{n-r+1} (n-i)C(r-1) = rC(r-1)+(r-1)C(r-1) = (r+1)Cr$.
$ \displaystyle \sum_{i=n-r+1}^{n-r+1} (n-i)C(r-1) = (r-1)C(r-1) = rCr$.

Adding up all the equations, we have

$ \displaystyle \sum_{i=1}^{n-r+1} [i \cdot (n-i)C(r-1)] = \displaystyle \sum_{i=0}^{n-r} (n-i)Cr $.

Using again the same argument, we have

$ \displaystyle \sum_{i=0}^{n-r} (n-i)Cr = (n+1)C(r+1) $.

Then we divide by the total number of subsets, which we found earlier to be $nCr$ to get

$ F(n,r) = \frac{(n+1)C(r+1)}{nCr} = \frac{n+1}{r+1} $

as desired. QED.

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

Comment: Yay, first IMO problem posted here. Not a particularly difficult one, though somewhat time consuming to write out. But anyway, hopefully there will be more to come.

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

Practice Problem: (2001 AIME - #2) A finite set $S$ of distinct real numbers has the following properties: the mean of $S\cup\{1\}$ is $13$ less than the mean of $S$, and the mean of $S\cup\{2001\}$ is $27$ more than the mean of $S$. Find the mean of $S$.