## Today’s Putnam problem – Dec. 01, 2007

From Harvard’s Math Department webpage, here’s today’s Putnam problem:

Take $r$ such that $1 \leq r \leq 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}$.

For starters, note that there are

$m = \displaystyle\binom{n}{r} = \frac{n!}{(n-r)! r!}$

different subsets of $r$ elements of the set $\{1, 2, \ldots, n\}$; let’s denote these subsets by $S_i$, where $i \in \{1, 2, \ldots, m\}$ and $|S_i| = r$. If the minimum element of subset $S_i$ is given by $\min(S_i)$, we then have

$F(n,r) = \displaystyle\frac{1}{m} \sum_{i=1}^m \min(S_i)$.

This is all very nice, but computing $\min(S_i)$ is not that straightforward. The best way to make sure that one understands the problem at hand is to consider an example, and that’s what I will do now.

Example: $n=4$ and $r=2$

In this case, we have

$m = \displaystyle\binom{4}{2} = \frac{4!}{2! 2!} = 6$

different subsets of the set $\{1, 2, 3, 4\}$. Since $m=6$ is quite small, we can quickly and easily find all the different subsets:

$S_1 = \{1, 2\}$

$S_2 = \{1, 3\}$

$S_3 = \{1, 4\}$

$S_4 = \{2, 3\}$

$S_5 = \{2, 4\}$

$S_6 = \{3, 4\}$

and the smallest element of each subset:

$\min(S_1) = 1$

$\min(S_2) = 1$

$\min(S_3) = 1$

$\min(S_4) = 2$

$\min(S_5) = 2$

$\min(S_6) = 3$.

And finally we have

$F(4,2) = \displaystyle\frac{\left(1 +1 +1 + 2 +2 + 3\right)}{6} = \displaystyle\frac{10}{6} = \displaystyle\frac{5}{3}$.

Note that $F(4,2) = \displaystyle\frac{4+1}{2+1}$.

My Solution:

Let’s start by considering two extreme examples of subsets of $\{1, 2, \ldots, n\}$

$S_1 = \{1, 2, \ldots, r\}$

$S_m = \{n, n-1, \ldots, n - (r-1)\}$,

where $|S_1| = |S_m| = r$. The smallest element of each of these subsets is given by

$\min(S_1) = 1$

$\min(S_m) = n - (r-1) = n - r + 1$

and therefore we have $1 \leq \min(S_i) \leq n -r + 1$ for every $i \in \{1, 2, \ldots, m\}$. While there’s only one subset of $\{1, 2, \ldots, n\}$ whose smallest element is $n - r + 1$, there is more than one subset whose smallest element is $1$. If one can compute the number of subsets whose smallest element is $k \in \{1, 2, \ldots, n - r + 1\}$, then one has solved the problem.

Let’s now consider all subsets (of $r$ elements of set $\{1, 2, \ldots, n\}$) whose smallest elements are $1$. How many are them? If the smallest element of each of these sets is $1$, then the remaining $r-1$ elements of the subset must be elements of set $\{2, 3, \ldots, n\}$, whose cardinality is $n-1$, and therefore we have

$\displaystyle \binom{n-1}{r-1}$

such subsets. If we consider all subsets whose smallest elements are $k$ (where $k \in \{1, 2, \ldots, n-r+1\}$), then the remaning $r-1$ elements of these subsets must be elements of set $\{k+1, k+2, \ldots, n\}$, whose cardinality is $n-k$. Therefore, there are

$\displaystyle \binom{n-k}{r-1}$

subsets whose smallest elements are $k$. Note that if $k = n-r+1$, we have

$\displaystyle \binom{n-(n-r+1)}{r-1} = \binom{r-1}{r-1} = 1$

subset only, as I had mentioned above. Since we now know how many subsets with a specific smallest element there are, we can compute $F(n, r)$ by taking the weighted average

$\displaystyle F(n, r) = \frac{\displaystyle\sum_{k=1}^{n-r+1} k \binom{n-k}{r-1}}{\displaystyle\sum_{k=1}^{n-r+1} \binom{n-k}{r-1}}$.

The denominator should me equal to $m = \binom{n}{r}$, and I have proved that already (I am not going to type the proof here because it’s a bit cumbersome). However, I can’t do much with the numerator. I am stuck. If you have any ideas, let me know.

### 2 Responses to “Today’s Putnam problem – Dec. 01, 2007”

1. Lewis S. Says:

Let choose(n,r) be the number of r-subsets of {1,…,n}. Let G(n,r) be the sum of the smallest elements of the r-subsets of {1,…,n}, for for 1<=r<=n.

Then G(n,1)=choose(n+1,2), and G(n,n)=1=choose(n+1,n+1). If n>r>1, then G(n,r)=G(n-1,r)+G(n-1,r-1).

But choose(n+1,r+1)=choose(n,r+1)+choose(n,r) by counting. Since the recursions are the same, G(n,r)=choose(n+1,r+1) by induction. The latter equals (n+1)/(r+1)*choose(n,r) and the result follows.

2. Lewis S. Says:

Here is a more intuitive proof.

Let V be the set of subsets of {0,1,…,n} of size r+1, and let W be the set of subsets of {1,…,n} of size r.

Let f:V->W delete the smallest element of its argument.

Then the cardinality of the preimage under f of an element of W is the value of the smallest element of that element. Hence, the sum of the smallest elements of the elements of W equals the cardinality of V, and the result follows.