IMO/1981 - Combinatorics

Question

IMO/1981

Let $1\le p \le n$ and consider all of the subsets of $p$ elements of the set $\{1, 2, 3,..., n\}$. Each of these subsets has a minimum element. Let $F(n, p)$ be the arithmetic average of these minimum elements. Prove that $F(n, p) = \frac {n+1}{p+1}$

My attempt:

So i initialy tried to think about how many subsets can you have given a minimum value $k_m$, such that $k_m \in \{1, 2,..., n\}$ obviously, but also such that $k \le n - p$, because otherwise that would mean the set can't have a minimum value of $k_m$ and $p$ elements, because that would mean you have less options to construct the set from ( $n - k_m - 1$) than you are needed ($p-1$). So i figured that if i fix a $k_m$ i have ${n - k_m - 1} \choose{p - 1}$ different sets in which this fixed element is the minimum, so the arithmetic average asked in the question is equal to:

$$F(n, p)=\frac{\sum_{k=1}^{n-p} k \binom{n - k - 1}{p - 1}}{\sum_{k=1}^{n-p} \binom{n - k - 1}{p - 1}}$$

So i need to prove that:

$$\frac{\sum_{k=1}^{n-p} k \binom{n - k - 1}{p - 1}}{\sum_{k=1}^{n-p} \binom{n - k - 1}{p - 1}}=\frac{n+1}{p+1}$$

But i'm struggling to effectively attack this proof simply because this sum is unlike any other one i've proven before, so i'd like to know:

If my reasoning has been correct so far (and if not, why not?) , and also some ideas on how to prove that huge sum.

Answer 1

If $k$ is the minimum of $p$ items chosen from $n$ items then there are ${n-k \choose p-1}$ equally probable ways of choosing the other items, so you are looking for

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

and clearly $\sum_{k=1}^{n+1-p} \binom{n - k}{p - 1} = \binom{n}{p }$, the total number of ways to choose $p$ items chosen from $n$ items.

If $k+1$ is the second lowest of $p+1$ items chosen from $n+1$ items then there are $k$ ways of choosing the smallest item and ${n-k \choose p-1}$ ways of choosing the other items, so $\sum_{k=1}^{n+1-p} k\binom{n - k}{p - 1} = \binom{n+1}{p+1}$

This makes $$F(n, p)=\frac{\binom{n+1}{p+1 }}{\binom{n}{p }}=\frac{n+1}{p+1}$$

Answer 2

First there will be $\binom {n-1}{p-1}$ sets having the element 1 which will be minimum of all the elements in this set. Similarly there will be $\binom {n-2}{p-1}$ sets having $2$ as its minimum element.

Using this intuition we need to find $$\frac {\sum_{k=1}^{n-p+1} k\binom {n-k}{p-1}}{\sum_{k=1}^{n-p+1} \binom {n-k}{p-1}}$$

Now using hockey stick identity the above summation turns out to be $$\frac {\binom {n+1}{p+1}}{\binom {n}{p}}= \frac {n+1}{p+1}$$

Q. E. D

Answer 3

Task 1: Enumeration of Subsets

Given $n$ and $r$ as per the constraints, arrange the numbers $1, 2, 3, \ldots, n$ in ascending order in a horizontal line. The number of subsets having $k$ as the minimum element is $\binom{n - k}{r - 1}$. Why? Because the numbers to the left of $k$ cannot be in the subset, as $k$ would no longer be the smallest element. Hence, the numbers to the right are the only eligible members from which we need to choose $r - 1$ elements.

Task 2: Summation format

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

Task 3 : Final derivation of required result

The denominator is nothing but the coefficient of $x^{r - 1}$ in $(1+x) + (1+x)^2 + \ldots + (1+x)^{n - r + 1}.$

Similarly, consider $S = (1+x) + 2(1+x)^2 + \ldots + (n + r - 1)(1 + x)^{n + r - 1}.$

The numerator is the coefficient of $x^{r - 1}$ in $S.$

On evaluating the above results and canceling, we get our required result.