Maths Olympiad Prep

Library / /104 of 520

Combinatorics Difficulty 5.7 AIME, harder Prove it

8. (FRG) IMO2{ }^{\mathrm{IMO} 2} Let f(n,r)f(n, r) be the arithmetic mean of the minima of all rr-element subsets of the set {1,2,,n}\{1,2, \ldots, n\}. Prove that f(n,r)=n+1r+1f(n, r)=\frac{n+1}{r+1}.

Solution

8. Since the number k,k=1,2,,nr+1k, k=1,2, \ldots, n-r+1, is the minimum in exactly (nkr1)r\binom{n-k}{r-1} r-element subsets of {1,2,,n}\{1,2, \ldots, n\}, it follows that
f(n,r)=1(nr)k=1nr+1k(nkr1) f(n, r)=\frac{1}{\binom{n}{r}} \sum_{k=1}^{n-r+1} k\binom{n-k}{r-1}
To calculate the sum in the above expression, using the equality (r+jj)=\binom{r+j}{j}= i=0j(r+i1r1)\sum_{i=0}^{j}\binom{r+i-1}{r-1}, we note that
k=1nr+1k(nkr1)=j=0nr(i=0j(r+i1r1))=j=0nr(r+jr)=(n+1r+1)=n+1r+1(nr). \begin{aligned} \sum_{k=1}^{n-r+1} k\binom{n-k}{r-1} & =\sum_{j=0}^{n-r}\left(\sum_{i=0}^{j}\binom{r+i-1}{r-1}\right) \\ & =\sum_{j=0}^{n-r}\binom{r+j}{r}=\binom{n+1}{r+1}=\frac{n+1}{r+1}\binom{n}{r} . \end{aligned}
Therefore f(n,r)=(n+1)/(r+1)f(n, r)=(n+1) /(r+1).

Want a route through all this instead of an archive? The track puts 2,000 problems in a working order, from AMC 10 level to the IMO shortlist.

Source: NuminaMath-1.5, licensed Apache-2.0. Statement and solution reproduced as published; topic and difficulty added by this site.