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.

About these ads

Tags: Combinatorics, Putnam Competition

This entry was posted on December 1, 2007 at 12:42 and is filed under Combinatorics, Puzzles. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

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

Lewis S. Says:
December 9, 2007 at 10:29 | Reply
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.
Lewis S. Says:
December 9, 2007 at 11:20 | Reply
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.

Rod Carvalho

Today’s Putnam problem – Dec. 01, 2007

Like this:

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

Leave a Reply Cancel reply

Follow “Rod Carvalho”