3
$\begingroup$

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.

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

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

$\endgroup$
  • $\begingroup$ 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 $\endgroup$ – Mateus Buarque Feb 19 '18 at 17:05
  • $\begingroup$ @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. $\endgroup$ – darij grinberg Feb 19 '18 at 17:28
2
$\begingroup$

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.