6
$\begingroup$

Consider all 1000-element subsets of the set $A = \{ 1, 2, 3, ... , 2015 \}$. From each such subset choose the least element. The arithmetic mean of all of these least elements is $\frac{p}{q}$, where $p$ and $q$ are relatively prime positive integers. Find $p + q$.

It will be:

$$\frac{a_1 + a_2 + ... + a_{k}}{k}$$

Obviously, one set is: $\{1, 2, 3, ..., 1000\}$ another could be: $\{1, 3, ... , 1000,1001\}$.

There are $2015 - 1 + 1 = 2015$ elements in set $A$. So:

$\binom{2015}{1000}$ of 1000 element subsets are present.

This problem is very tough for me to solve right now...

HINTS only please! Thank you!!

$\endgroup$
  • $\begingroup$ This could come in handy: proofwiki.org/wiki/Rising_Sum_of_Binomial_Coefficients $\endgroup$ – ajotatxe Jul 19 '15 at 21:05
  • $\begingroup$ Usually, in a problem, if you are asked to find the sum or average, it is often useful to consider each individual term and see how many times it appears. In your case, you should try to check how many times each number has appeared as the least element. $\endgroup$ – rah4927 Jul 19 '15 at 22:02
2
$\begingroup$

A possible hint :

There is

  • $ 2014 \choose 999 $ subsets with 1 as the smallest element
  • $ 2013 \choose 999 $ subsets with 2 as the smallest element
  • $\cdots$
  • $ 2015-k \choose 999 $ subsets with k as the smallest element

So you're looking at

$$\frac{p}{q} = \frac{ \sum_{k=1}^{1016} k {2015-k \choose 999} }{ 2015 \choose 1000} $$

Can you calculate this sum?

$$\sum_{k=1}^{1016} k {2015-k \choose 999} $$

$\endgroup$

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.