# 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.

• What is the distinction between $k_m$ and $k$? – Henry Feb 19 '18 at 8:57
• $k_m$ denotes some minimum value , and $k$ is the variable that i choose in the sum to represent it – Mateus Buarque Feb 19 '18 at 9:05

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

• Why did your sum go from $k = 1$ to $n - p + 1$? I thought that if $k = n - p + 1$ the set couldn't exist – Mateus Buarque Feb 19 '18 at 17:05
• @MateusBuarque: No, for $k = n-p+1$ the set can exist (there is exactly one such set in this case: $\left\{n-p+1,n-p+2,\ldots,n\right\}$). Only for $k > n-p+1$ do such sets cease to exist. You might have made a fencepost error. – darij grinberg Feb 19 '18 at 17:28

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}$$

• Should the upper limit of summation be $n+1-p?$ – saulspatz Feb 19 '18 at 10:00
• @saulspatz - yes it should - thank you – Henry Feb 19 '18 at 10:28